shelterofly

目标

给你一个 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;
            }
        }
    }

}

性能

目标

给你一个 m x n 的网格 grid，其中每个单元格包含以下值之一：0、1 或 2。另给你一个整数 k。

你从左上角 (0, 0) 出发，目标是到达右下角 (m - 1, n - 1)，只能向 右 或 下 移动。

每个单元格根据其值对路径有以下贡献：

• 值为 0 的单元格：分数增加 0，花费 0。
• 值为 1 的单元格：分数增加 1，花费 1。
• 值为 2 的单元格：分数增加 2，花费 1。

返回在总花费不超过 k 的情况下可以获得的 最大分数 ，如果不存在有效路径，则返回 -1。

注意： 如果到达最后一个单元格时总花费超过 k，则该路径无效。

示例 1：

输入： grid = [[0, 1],[2, 0]], k = 1
输出： 2
解释：
最佳路径为：
单元格  grid[i][j] 当前分数 累计分数 当前花费 累计花费
(0, 0)     0         0      0        0       0
(1, 0)     2         2      2        1       1
(1, 1)     0         0      2        0       1
因此，可获得的最大分数为 2。

示例 2：

输入： grid = [[0, 1],[1, 2]], k = 1
输出： -1
解释：
不存在在总花费不超过 k 的情况下到达单元格 (1, 1) 的路径，因此答案是 -1。

说明：

• 1 <= m, n <= 200
• 0 <= k <= 10^3
• grid[0][0] == 0
• 0 <= grid[i][j] <= 2

思路

有一个 m x n 网格 grid，其元素值可取 0、1、2，从左上角 (0, 0) 移动到 (m - 1, n - )，每次移动只能向右或向下，移动的代价为 grid[i][j] == 0 ? 0 : 1。求总代价不超过 k 的条件下，从左上移动到右下的最大得分，如果不存在有效路径返回 -1。

定义 dp[i + 1][j + 1][c] 表示到达坐标 (i, j) 且代价不超过 c - 1 的最大得分。状态转移方程为 dp[i + 1][j + 1][c] = Math.max(dp[i][j + 1][c + cost], dp[i + 1][j][c + cost]) + grid[i][j]，其中 cost = grid[i][j] == 0 ? 0 : -1。

可以进行空间优化，直接将第一个维度去掉，内层倒序遍历即可。

代码

/**
 * @date 2026-04-30 8:57
 */
public class MaxPathScore3742 {

    public int maxPathScore_v2(int[][] grid, int k) {
        int n = grid[0].length;
        int[][] dp = new int[n + 1][k + 2];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        Arrays.fill(dp[1], 1, k + 2, 0);
        for (int[] row : grid) {
            for (int j = 0; j < n; j++) {
                int cost = row[j] == 0 ? 0 : -1;
                for (int c = k + 1; c >=1; c--) {
                    dp[j + 1][c] = Math.max(dp[j + 1][c + cost], dp[j][c + cost]) + row[j];
                }
            }
        }
        return dp[n][k + 1] < 0 ? -1 : dp[n][k + 1];
    }

}

性能

目标

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。

单值网格 是全部元素都相等的网格。

返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。

示例 1：

输入：grid = [[2,4],[6,8]], x = 2
输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 
- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
共计 4 次操作。

示例 2：

输入：grid = [[1,5],[2,3]], x = 1
输出：5
解释：可以使所有元素都等于 3 。

示例 3：

输入：grid = [[1,2],[3,4]], x = 2
输出：-1
解释：无法使所有元素相等。

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• 1 <= x, grid[i][j] <= 10^4

思路

有一个 m x n 矩阵，每次操作可以将矩阵中的任意元素 +x 或者 -x，求使得矩阵所有元素相等所需的最小操作，如果不能返回 -1。

所有元素对 x 取模余数相同才有解，因为操作无法改变这个余数，而目标是将元素变成同一个数。

如果有解，可以将共同的余数减去，将每个元素都除以 x，然后令 x = 1，问题变成找到一个值，使得所有元素到这个值的距离之和最小。

这是一个 L1 优化问题，它的解是中位数，可以先排序，再取中间的元素即可。

代码

/**
 * @date 2026-04-28 9:35
 */
public class MinOperations2033 {

    public int minOperations(int[][] grid, int x) {
        int m = grid.length;
        int n = grid[0].length;
        int[] arr = new int[m * n];
        int rem = grid[0][0] % x;
        int k = 0;
        for (int[] row : grid) {
            for (int e : row) {
                if (e % x != rem) {
                    return -1;
                }
                arr[k++] = e / x;
            }
        }
        Arrays.sort(arr);
        int median = arr[arr.length / 2];
        int res = 0;
        for (int num : arr) {
            res += Math.abs(num - median);
        }
        return res;
    }
}

性能