月度归档： 2026 年 5 月

目标

给你一个 m x n 的字符矩阵 boxGrid ，它表示一个箱子的侧视图。箱子的每一个格子可能为：

• '#' 表示石头
• '*' 表示固定的障碍物
• '.' 表示空位置

这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力 不会 影响障碍物的位置，同时箱子旋转不会产生惯性 ，也就是说石头的水平位置不会发生改变。

题目保证初始时 boxGrid 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。

请你返回一个 n x m 的矩阵，表示按照上述旋转后，箱子内的结果。

示例 1：

输入：box = [["#",".","#"]]
输出：[["."],
      ["#"],
      ["#"]]

示例 2：

输入：box = [["#",".","*","."],
            ["#","#","*","."]]
输出：[["#","."],
      ["#","#"],
      ["*","*"],
      [".","."]]

示例 3：

输入：box = [["#","#","*",".","*","."],
            ["#","#","#","*",".","."],
            ["#","#","#",".","#","."]]
输出：[[".","#","#"],
      [".","#","#"],
      ["#","#","*"],
      ["#","*","."],
      ["#",".","*"],
      ["#",".","."]]

说明：

• m == boxGrid.length
• n == boxGrid[i].length
• 1 <= m, n <= 500
• boxGrid[i][j] 只可能是 '#' ，'*' 或者 '.' 。

思路

有一个 m x n 矩阵，. 表示空位，# 表示石头，* 表示障碍物。将矩阵顺时针旋转 90°，石头遇到障碍物或者底部会停止下落，返回最终的结果。

根据题意模拟，旋转矩阵，然后分别处理每一列，将石头加入栈中，并将当前格子置空，如果遇到障碍物或者底部则向上填充石头。

代码

/**
 * @date 2026-05-06 9:42
 */
public class RotateTheBox1861 {

    public char[][] rotateTheBox(char[][] boxGrid) {
        boxGrid = rotate(boxGrid);
        int m = boxGrid.length;
        int n = boxGrid[0].length;
        for (int j = 0; j < n; j++) {
            Deque<Character> q = new ArrayDeque<>();
            for (int i = 0; i < m; i++) {
                char c = boxGrid[i][j];
                if (c == '#') {
                    q.push(c);
                    boxGrid[i][j] = '.';
                } else if (c == '*') {
                    int k = i - 1;
                    while (!q.isEmpty()){
                        boxGrid[k--][j] = q.pop();
                    }
                }
            }
            int i = m - 1;
            while (!q.isEmpty()){
                boxGrid[i--][j] = q.pop();
            }
        }
        return boxGrid;
    }

    public char[][] rotate(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        char[][] rotated = new char[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j][m - 1 - i] = grid[i][j];
            }
        }
        return rotated;
    }
}

性能

目标

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

说明：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

思路

将链表的每个节点右移 k 个位置，即将链表最后 k % list.size() 个元素放到列表头。

可以使用快慢指针，slow 指向最后 k 个节点的前面一个节点，slow 指针移到到 fast 指针需要移动 k + 1 次，即后面 k 个节点和 null。先让 fast 移动 k + 1 次，再让 slow 与 fast 同时移动。

代码

/**
 * @date 2024-11-24 16:15
 */
public class RotateRight61 {

    public ListNode rotateRight_v1(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int length = 1;
        ListNode last = head;
        while (last.next != null) {
            last = last.next;
            length++;
        }
        k = k % length + 1;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            k--;
            if (k < 0) {
                slow = slow.next;
            }
        }
        last.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }

}

性能

目标

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

说明：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

思路

将 n x n 矩阵顺时针 原地 旋转 90°。

顺时针旋转 90° 的规律：交换行列坐标，将列坐标变为 n - 1 - ?。

i, j -> j, n - 1 - i
     -> n - 1 - i, n - 1 - j
     -> n - 1 - j, i,
     -> i, j

代码

/**
 * @date 2025-01-26 22:02
 */
public class Rotate48 {

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                int tmp = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = matrix[i][j];
                matrix[i][j] = tmp;
            }
        }
    }

}

性能