标签： 模拟

目标

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。

A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

请你返回 A 和 B 的 前缀公共数组 。

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。

示例 1：

输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。

示例 2：

输入：A = [2,3,1], B = [3,1,2]
输出：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。

说明：

• 1 <= A.length == B.length == n <= 50
• 1 <= A[i], B[i] <= n
• 题目保证 A 和 B 两个数组都是 n 个元素的排列。

思路

有两个长度为 n 的整数排列 A 和 B，整数 1 ~ n 恰好出现一次，C[i] 表示 A[0, i] 和 B[0, i] 中的公共元素个数（注意不是公共前缀长度），返回 C。

直接依题意模拟，使用哈希表（或者数组计数），A 中元素 +1， B 中元素 -1，然后累加出现次数为 0 的元素个数即可。注意元素相同时避免重复累加，并且当前位置公共元素的个数应该以前一个位置公共元素的个数为基础再加上新增公共元素的个数。

网友题解使用的是位运算，注意到 n <= 50，可以使用两个 long 型变量来记录元素是否出现，将这两个变量相与然后 bitcount 就是公共元素个数。

代码

/**
 * @date 2026-05-20 8:58
 */
public class FindThePrefixCommonArray2657 {

    public int[] findThePrefixCommonArray_v1(int[] A, int[] B) {
        int n = A.length;
        int[] cnt = new int[n + 1];
        int[] C = new int[n];
        cnt[A[0]]++;
        cnt[B[0]]--;
        if (A[0] == B[0]) {
            C[0] = 1;
        }
        for (int i = 1; i < n; i++) {
            cnt[A[i]]++;
            cnt[B[i]]--;
            C[i] = C[i - 1];
            if (cnt[A[i]] == 0) {
                C[i]++;
            }
            if (A[i] != B[i] && cnt[B[i]] == 0) {
                C[i]++;
            }
        }
        return C;
    }

}

性能

目标

给你一个大小为 m x n 的整数矩阵 grid ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。

矩阵由若干层组成，如下图所示，每种颜色代表一层：

矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。轮转示例如下：

返回执行 k 次循环轮转操作后的矩阵。

示例 1：

输入：grid = [[40,10],[30,20]], k = 1
输出：[[10,20],[40,30]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

示例 2：

输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

说明：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• m 和 n 都是 偶数
• 1 <= grid[i][j] <= 5000
• 1 <= k <= 10^9

思路

有一个 m x n 矩阵 grid，m 与 n 都是偶数，矩阵里外分层，每次轮转用元素取代对应层逆时针方向的下一个元素，求轮转 k 次之后的矩阵。

m x n 矩阵有 Math.min(m/2, n/2) 层，最外层有 2 * (m + n) - 4 个元素，下一层用 m - 2， n - 2 代入，得到比上一层少 8 个元素，以此类推。

将每一层映射到一维进行轮转，然后再赋值回去即可。可以使用方向向量来赋值，碰到边界就转向。

参考 874.模拟行走机器人 2069.模拟行走机器人II 59.螺旋矩阵II

代码

/**
 * @date 2026-05-09 9:26
 */
public class RotateGrid1914 {

    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int layer = Math.min(m / 2, n / 2);
        int[][] arr = new int[layer][];
        int length = 2 * (m + n) - 4;
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0, x = 0, y = 0, d = 0; i < layer; i++, x++, y++) {
            arr[i] = new int[length];
            int a = x, b = y;
            for (int j = 0; j < length; j++) {
                arr[i][j] = grid[a][b];
                while (a + directions[d][0] < x || a + directions[d][0] > m - 1 - x
                        || b + directions[d][1] < y || b + directions[d][1] > n - 1 - y) {
                    d = (d + 1) % 4;
                }
                a += directions[d][0];
                b += directions[d][1];
            }
            int offset = k % length;
            a = x;
            b = y;
            d = 0;
            for (int j = offset; j < offset + length; j++) {
                grid[a][b] = arr[i][j % length];
                while (a + directions[d][0] < x || a + directions[d][0] > m - 1 - x
                        || b + directions[d][1] < y || b + directions[d][1] > n - 1 - y) {
                    d = (d + 1) % 4;
                }
                a += directions[d][0];
                b += directions[d][1];
            }
            length -= 8;
        }
        return grid;
    }

}

性能

目标

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

性能

目标

给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。

对于每个查询，按以下步骤执行操作：

• 设定 idx = li。
• 当 idx <= ri 时：
  • 更新：nums[idx] = (nums[idx] * vi) % (10^9 + 7)
  • 将 idx += ki。

在处理完所有查询后，返回数组 nums 中所有元素的 按位异或 结果。

示例 1：

输入： nums = [1,1,1], queries = [[0,2,1,4]]
输出： 4
解释：
唯一的查询 [0, 2, 1, 4] 将下标 0 到下标 2 的每个元素乘以 4。
数组从 [1, 1, 1] 变为 [4, 4, 4]。
所有元素的异或为 4 ^ 4 ^ 4 = 4。

示例 2：

输入： nums = [2,3,1,5,4], queries = [[1,4,2,3],[0,2,1,2]]
输出： 31
解释：
第一个查询 [1, 4, 2, 3] 将下标 1 和 3 的元素乘以 3，数组变为 [2, 9, 1, 15, 4]。
第二个查询 [0, 2, 1, 2] 将下标 0、1 和 2 的元素乘以 2，数组变为 [4, 18, 2, 15, 4]。
所有元素的异或为 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31。

说明：

• 1 <= n == nums.length <= 10^3
• 1 <= nums[i] <= 10^9
• 1 <= q == queries.length <= 10^3
• queries[i] = [li, ri, ki, vi]
• 0 <= li <= ri < n
• 1 <= ki <= n
• 1 <= vi <= 10^5

思路

有一个长度为 n 的数组，对该数组执行 n 次查询，每次查询从 li 开始，对相距 ki 个位置上的元素执行 nums[idx] = (nums[idx] * vi) % (10^9 + 7) 直到下标 idx > ri。求处理完所有查询后 nums 中所有元素的 按位异或 结果。

查询次数最大为 10^3，每次查询区间也是 [0, 10^3 - 1]，步长 ki ∈ [1, 10^3]。

可以直接模拟。

代码

/**
 * @date 2026-04-08 8:56
 */
public class XorAfterQueries3653 {

    public int xorAfterQueries(int[] nums, int[][] queries) {
        int mod = 1000000007;
        for (int[] query : queries) {
            int li = query[0], ri = query[1], ki = query[2], vi = query[3];
            while (li <= ri) {
                nums[li] = (int) ((long) nums[li] * vi % mod);
                li += ki;
            }
        }
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }

}

性能

目标

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。

机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。

1. 沿着当前方向尝试 往前一步 。
2. 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。

如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。

请你实现 Robot 类：

• Robot(int width, int height) 初始化一个 width x height 的网格图，机器人初始在 (0, 0) ，方向朝 "East" 。
• void step(int num) 给机器人下达前进 num 步的指令。
• int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [x, y] 表示。
• String getDir() 返回当前机器人的朝向，为 "North" ，"East" ，"South" 或者 "West" 。

示例 1：

输入：
["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.step(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.step(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.step(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"

说明：

• 2 <= width, height <= 100
• 1 <= num <= 10^5
• step ，getPos 和 getDir 总共 调用次数不超过 10^4 次。

思路

有一个 w x h 的网格图，左下格子的坐标为 (0, 0)，初始时机器人朝向东方，机器人可以根据指令沿着当前朝向移动指定的步数，如果下一步到达了网格边界，则逆时针旋转 90° 继续尝试。实现 Robot 类，可以执行移动，以及获取机器人当前的位置、朝向。

暴力解法是模拟走每一步，如果越界则转向，直到剩余步数为 0。但是由于 step 调用次数最大为 10^4，所走步数是 int 类型，模拟走每一步会超时。

注意到机器人只能沿着网格的最外层绕圈，对周长 (w - 1 + h - 1)* 2 取模，只需模拟最后一圈即可。有一个出错点是回到原点的朝向，初始时朝向东方，回到原点时，朝向南方，需要特殊处理。

代码

/**
 * @date 2026-04-07 8:57
 */
public class Robot2069 {

    static class Robot {

        int[][] grid;
        int[][] directions = new int[][]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
        String[] res = new String[]{"South", "East", "North", "West"};
        int d = 1;
        int m;
        int n;
        int[] pos;

        public Robot(int width, int height) {
            m = height;
            n = width;
            grid = new int[m][n];
            pos = new int[]{0, 0};
        }

        public void step(int num) {
            int step = num % (m + n + m + n - 4);
            // 当位于原点，方向朝东时，再走 k 圈的方向应该朝南，如果不在原点的话，方向还是朝东
            if (step == 0 && d == 1 && pos[0] == 0 && pos[1] == 0) {
                d = 0;
            }
            while (step > 0) {
                while (pos[0] + directions[d][0] < 0
                        || pos[0] + directions[d][0] == n
                        || pos[1] + directions[d][1] < 0
                        || pos[1] + directions[d][1] == m
                ) {
                    d = ++d % 4;
                }
                pos[0] += directions[d][0];
                pos[1] += directions[d][1];
                step--;
            }
        }

        public int[] getPos() {
            return pos;
        }

        public String getDir() {
            return res[d];
        }
    }

}
/**
 * Your Robot object will be instantiated and called as such:
 * Robot obj = new Robot(width, height);
 * obj.step(num);
 * int[] param_2 = obj.getPos();
 * String param_3 = obj.getDir();
 */

性能

目标

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：

• -2 ：向左转 90 度
• -1 ：向右转 90 度
• 1 <= x <= 9 ：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

返回机器人距离原点的 最大欧式距离 的 平方 。（即，如果距离为 5 ，则返回 25 ）

注意：

• 北方表示 +Y 方向。
• 东方表示 +X 方向。
• 南方表示 -Y 方向。
• 西方表示 -X 方向。
• 原点 [0,0] 可能会有障碍物。

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 3^2 + 4^2 = 25

示例 2：

输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解释：机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8) ，距离为 1^2 + 8^2 = 65

示例 3：

输入：commands = [6,-1,-1,6], obstacles = []
输出：36
解释：机器人开始位于 (0, 0):
1. 向北移动 6 个单位，到达 (0, 6).
2. 右转
3. 右转
4. 向南移动 6 个单位，到达 (0, 0).
机器人距离原点最远的点是 (0, 6)，其距离的平方是 6^2 = 36 个单位。

说明：

• 1 <= commands.length <= 10^4
• commands[i] 的值可以取 -2、-1 或者是范围 [1, 9] 内的一个整数。
• 0 <= obstacles.length <= 10^4
• -3 10^4 <= xi, yi <= 3 10^4
• 答案保证小于 2^31

思路

二维平面的原点 (0, 0) 有一个机器人，开始时机器人面向北方。同时平面上还有一些障碍物 obstacles[i] = (xi, yi)。机器人可以根据指令 commands[i] 进行转向（-2 表示左转 90°，-1 表示右转 90°）或者向前移动对应数量的格子，如果碰到障碍物则在障碍物前停止，并继续执行下一条指令，返回机器人距离原点的最大欧式距离，坐标 (x, y) 距离原点的欧式距离为 x^2 + y^2。

由于机器人可能会往回走，最远的欧式距离可能在之前达到。

根据题目的指令描述模拟该过程，按照逆时针方向初始化上左下右四个方向的 (dx, dy)。初始方向 d = 0，左转时 d = (d + 1) % 4，右转时 d = (d + 3) % 4。为了判断下一格子是否有障碍物，可以使用哈希表 (rowi, coli_Set)保存障碍物的坐标。

网友题解是将坐标压缩到一个 int 中保存了，哈希表使用的是 Set<Integer>。由于坐标存在负值，这里还根据题目范围加了一个偏移量。

代码

/**
 * @date 2026-04-07 10:43
 */
public class RobotSim874 {

    public int robotSim(int[] commands, int[][] obstacles) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] o : obstacles) {
            map.putIfAbsent(o[0], new HashSet<>());
            map.get(o[0]).add(o[1]);
        }
        int res = 0;
        int[] pos = new int[]{0, 0};
        int[][] directions = new int[][]{{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
        int d = 0;
        for (int command : commands) {
            if (command == -1) {
                d = (d + 3) % 4;
            } else if (command == -2) {
                d = (d + 1) % 4;
            } else {
                while (command > 0) {
                    Set<Integer> set = map.get(pos[0] + directions[d][0]);
                    if (set != null &&
                            set.contains(pos[1] + directions[d][1])) {
                        break;
                    }
                    pos[0] += directions[d][0];
                    pos[1] += directions[d][1];
                    command--;
                }
                res = Math.max(res, pos[0] * pos[0] + pos[1] * pos[1]);
            }
        }
        return res;
    }

}

性能