标签： 模拟

目标

给你一个字符串 s，它由小写英文字母和特殊字符：*、# 和 % 组成。

请根据以下规则从左到右处理 s 中的字符，构造一个新的字符串 result：

• 如果字符是 小写 英文字母，则将其添加到 result 中。
• 字符 '*' 会 删除 result 中的最后一个字符（如果存在）。
• 字符 '#' 会 复制 当前的 result 并 追加 到其自身后面。
• 字符 '%' 会 反转 当前的 result。

在处理完 s 中的所有字符后，返回最终的字符串 result。

示例 1：

输入： s = "a#b%*"
输出： "ba"
解释：
i s[i] 操作 当前 result
0 'a' 添加 'a' "a"
1 '#' 复制 result "aa"
2 'b' 添加 'b' "aab"
3 '%' 反转 result "baa"
4 '*' 删除最后一个字符 "ba"
因此，最终的 result 是 "ba"。

示例 2：

输入： s = "z*#"
输出： ""
解释：
i s[i] 操作 当前 result
0 'z' 添加 'z' "z"
1 '*' 删除最后一个字符 ""
2 '#' 复制字符串 ""
因此，最终的 result 是 ""。

说明:

• 1 <= s.length <= 20
• s 只包含小写英文字母和特殊字符 *、# 和 %。

思路

根据规则从左到右处理字符串 s，如果时小写字母添加到结果 result，如果是 * 删除 result 的最后一个字符，如果是 # 将 result 追加到自身的后面，如果是 % 则反转当前的 result。

字符串长度最大为 20，可以暴力模拟。

代码

/**
 * @date 2025-07-14 9:15
 */
public class ProcessStrQ1 {

    public String processStr(String s) {
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            switch (c) {
                case '*':
                    if (sb.length() > 0) {
                        sb.deleteCharAt(sb.length() - 1);
                    }
                    break;
                case '#':
                    sb.append(sb);
                    break;
                case '%':
                    sb.reverse();
                    break;
                default:
                    sb.append(c);
            }
        }
        return sb.toString();
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：

• 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
• 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
• 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
  • 更正式的，考虑每一对 pi，pj ，pi 是初始时位置 i 元素的新位置，pj 是初始时位置 j 元素的新位置。如果 i < j 且两个元素 都 小于（或大于）pivot，那么 pi < pj 。

请你返回重新排列 nums 数组后的结果数组。

示例 1：

输入：nums = [9,12,5,10,14,3,10], pivot = 10
输出：[9,5,3,10,10,12,14]
解释：
元素 9 ，5 和 3 小于 pivot ，所以它们在数组的最左边。
元素 12 和 14 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ，它们在结果数组中的相对顺序需要保留。

示例 2：

输入：nums = [-3,4,3,2], pivot = 2
输出：[-3,2,4,3]
解释：
元素 -3 小于 pivot ，所以在数组的最左边。
元素 4 和 3 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ，它们在结果数组中的相对顺序需要保留。

说明：

• 1 <= nums.length <= 10^5
• -10^6 <= nums[i] <= 10^6
• pivot 等于 nums 中的一个元素。

思路

根据给定数字 pivot 划分数组，左边的都小于 pivot，右边的都大于 pivot，中间的等于 pivot，同一边元素的相对位置不能改变。

直接使用两个列表保存 小于 和 大于 pivot 的元素，计算等于 pivot 的元素个数，按顺序回填原数组即可。

代码

/**
 * @date 2026-06-08 9:49
 */
public class PivotArray2161 {

    public int[] pivotArray(int[] nums, int pivot) {
        int n = nums.length;
        Deque<Integer> l = new ArrayDeque<>();
        Deque<Integer> r = new ArrayDeque<>();
        for (int num : nums) {
            if (num < pivot) {
                l.offer(num);
            } else if (num > pivot) {
                r.offer(num);
            }
        }
        int equal = n - l.size() - r.size();
        int i = 0;
        while (!l.isEmpty()) {
            nums[i++] = l.poll();
        }
        while (equal > 0){
            nums[i++] = pivot;
            equal--;
        }
        while (!r.isEmpty()) {
            nums[i++] = r.poll();
        }
        return nums;
    }

}

性能

目标

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

说明：

• 1 <= mass <= 10^5
• 1 <= asteroids.length <= 10^5
• 1 <= asteroids[i] <= 10^5

思路

有一颗行星质量为 mass，还有一些小行星 asteroids，asteroids[i] 表示第 i 颗小行星的质量。可以让小行星以任意顺序碰撞行星，如果行星质量大于等于小行星，那么小行星被摧毁，行星获得其质量，否则行星被摧毁。判断是否所有小行星都可以被摧毁。

使用有序集合，每次获得比行星质量小的所有小行星质量。

代码

/**
 * @date 2026-06-01 10:14
 */
public class AsteroidsDestroyed2126 {

    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        TreeMap<Long, Integer> ts = new TreeMap<>();
        for (int a : asteroids) {
            ts.merge((long) a, 1, Integer::sum);
        }
        long m = mass;
        Long next = ts.floorKey(m);
        while (!ts.isEmpty() && next != null) {
            m += next * ts.get(next);
            ts.remove(next);
            next = ts.floorKey(m);
        }
        return ts.isEmpty();
    }

}

性能

目标

给你两个下标从 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;
    }

}

性能