2553.分割数组中数字的数位

目标

给你一个正整数数组 nums ,请你返回一个数组 answer ,你需要将 nums 中每个整数进行数位分割后,按照 nums 中出现的 相同顺序 放入答案数组中。

对一个整数进行数位分割,指的是将整数各个数位按原本出现的顺序排列成数组。

比方说,整数 10921 ,分割它的各个数位得到 [1,0,9,2,1] 。

示例 1:

输入:nums = [13,25,83,77]
输出:[1,3,2,5,8,3,7,7]
解释:
- 分割 13 得到 [1,3] 。
- 分割 25 得到 [2,5] 。
- 分割 83 得到 [8,3] 。
- 分割 77 得到 [7,7] 。
answer = [1,3,2,5,8,3,7,7] 。answer 中的数字分割结果按照原数字在数组中的相同顺序排列。

示例 2:

输入:nums = [7,1,3,9]
输出:[7,1,3,9]
解释:nums 中每个整数的分割是它自己。
answer = [7,1,3,9] 。

说明:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^5

思路

有一个数组 nums,按顺序将数组中的元素进行数位分割,将结果保存到一个新数组中。

通俗讲就是将数组元素都放在一起从左到右按位取每一个数字即可。

代码


/**
 * @date 2026-05-11 9:04
 */
public class SeparateDigits2553 {

    public int[] separateDigits(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            while (num > 0) {
                list.add(num % 10);
                num /= 10;
            }
        }
        int l = list.size();
        int[] res = new int[l];
        for (Integer num : list) {
            res[--l] = num;
        }
        return res;
    }
}

性能

2770.达到末尾下标所需的最大跳跃次数

目标

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。

你的初始位置在下标 0 。在一步操作中,你可以从下标 i 跳跃到任意满足下述条件的下标 j :

  • 0 <= i < j < n
  • -target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ,返回 -1 。

示例 1:

输入:nums = [1,3,6,4,1,2], target = 2
输出:3
解释:要想以最大跳跃次数从下标 0 到下标 n - 1 ,可以按下述跳跃序列执行操作:
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 5 。 
可以证明,从 0 到 n - 1 的所有方案中,不存在比 3 步更长的跳跃序列。因此,答案是 3 。

示例 2:

输入:nums = [1,3,6,4,1,2], target = 3
输出:5
解释:要想以最大跳跃次数从下标 0 到下标 n - 1 ,可以按下述跳跃序列执行操作:
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 2 。 
- 从下标 2 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 4 。 
- 从下标 4 跳跃到下标 5 。 
可以证明,从 0 到 n - 1 的所有方案中,不存在比 5 步更长的跳跃序列。因此,答案是 5 。

示例 3:

输入:nums = [1,3,6,4,1,2], target = 0
输出:-1
解释:可以证明不存在从 0 到 n - 1 的跳跃序列。因此,答案是 -1 。

提示:

  • 2 <= nums.length == n <= 1000
  • -10^9 <= nums[i] <= 10^9
  • 0 <= target <= 2 * 10^9

思路

有一个数组 nums,对于小标 i 可以跳到 j > i && |nums[j] - nums[i]| <= target,返回从 0 跳到 n - 1 的最大跳跃次数。

定义 dp[i] 表示到达 i 的最大跳跃次数,dp[0] = 0,枚举 j ∈ [i + 1, n - 1] 如果 Math.abs(nums[j] - nums[i]) <= targetdp[j] = Math.max(dp[j], dp[i] + 1),注意:如果 dp[i] == 0, i > 0,说明无法从 0 到达当前下标,直接跳过。

代码


/**
 * @date 2026-05-11 10:07
 */
public class MaximumJumps2770 {

    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && dp[i] == 0) {
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n - 1] == 0 ? -1 : dp[n - 1];
    }

}

性能

时间复杂度 O(n^2),//todo 线段树维护最大值

1914.循环轮转矩阵

目标

给你一个大小为 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 矩阵 gridmn 都是偶数,矩阵里外分层,每次轮转用元素取代对应层逆时针方向的下一个元素,求轮转 k 次之后的矩阵。

m x n 矩阵有 Math.min(m/2, n/2) 层,最外层有 2 * (m + n) - 4 个元素,下一层用 m - 2n - 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;
    }

}

性能

3629.通过质数传送到达终点的最少跳跃次数

目标

给你一个长度为 n 的整数数组 nums。

你从下标 0 开始,目标是到达下标 n - 1。

在任何下标 i 处,你可以执行以下操作之一:

  • 移动到相邻格子:跳到下标 i + 1 或 i - 1,如果该下标在边界内。
  • 质数传送:如果 nums[i] 是一个质数 p,你可以立即跳到任何满足 nums[j] % p == 0 的下标 j 处,且下标 j != i 。

返回到达下标 n - 1 所需的 最少 跳跃次数。

质数 是一个大于 1 的自然数,只有两个因子,1 和它本身。

示例 1:

输入: nums = [1,2,4,6]
输出: 2
解释:
一个最优的跳跃序列是:
从下标 i = 0 开始。向相邻下标 1 跳一步。
在下标 i = 1,nums[1] = 2 是一个质数。因此,我们传送到索引 i = 3,因为 nums[3] = 6 可以被 2 整除。
因此,答案是 2。

示例 2:

输入: nums = [2,3,4,7,9]
输出: 2
解释:
一个最优的跳跃序列是:
从下标 i = 0 开始。向相邻下标 i = 1 跳一步。
在下标 i = 1,nums[1] = 3 是一个质数。因此,我们传送到下标 i = 4,因为 nums[4] = 9 可以被 3 整除。
因此,答案是 2。

示例 3:

输入: nums = [4,6,5,8]
输出: 3
解释:
由于无法进行传送,我们通过 0 → 1 → 2 → 3 移动。因此,答案是 3。

说明:

  • 1 <= n == nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

思路

有一个数组 nums,从下标 0 开始移动,目标是到达下标 n - 1。每次移动可以移动到相邻的位置,如果 nums[i] 是质数,可以直接移动到满足 nums[j] % nums[i] == 0 的位置。返回最少移动次数。

枚举 2 ~ MAX,为每一个数记录质因子,得到哈希表 (num,primeFactorList),枚举数组中的元素,获取 primeFactorList,为其中的每一个质数建立一个跳转列表 jumpIndexList,将当前下标加进去。从 0 开始 bfs,记录跳转次数,直到到达下标 n - 1

代码


/**
 * @date 2026-05-08 16:55
 */
public class MinJumps3629 {

    public static final int MAX = 1000000;
    public static Map<Integer, List<Integer>> primeFactorMap = new HashMap<>();

    static {
        primeFactorMap.computeIfAbsent(1, k -> new ArrayList<>());
        for (int i = 2; i <= MAX; i++) {
            if (primeFactorMap.get(i) == null) {
                for (int j = i; j <= MAX; j += i) {
                    primeFactorMap.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> jumpIndexList = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> primeFactors = primeFactorMap.get(nums[i]);
            for (Integer prime : primeFactors) {
                jumpIndexList.computeIfAbsent(prime, k -> new ArrayList<>()).add(i);
            }
        }
        boolean[] visited = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        int res = 0;
        here:
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Integer index = q.poll();
                if (visited[index]) {
                    continue;
                }
                visited[index] = true;
                if (index == n - 1) {
                    break here;
                }
                int next = index + 1;
                int prev = index - 1;
                if (next < n) {
                    q.offer(next);
                }
                if (prev >= 0) {
                    q.offer(prev);
                }
                if (jumpIndexList.get(nums[index]) != null) {
                    q.addAll(jumpIndexList.get(nums[index]));
                    jumpIndexList.get(nums[index]).clear();
                }
            }
            res++;
        }
        return res;
    }

}

性能

3660.跳跃游戏IX

目标

给你一个整数数组 nums。

从任意下标 i 出发,你可以根据以下规则跳跃到另一个下标 j:

  • 仅当 nums[j] < nums[i] 时,才允许跳跃到下标 j,其中 j > i。
  • 仅当 nums[j] > nums[i] 时,才允许跳跃到下标 j,其中 j < i。

对于每个下标 i,找出从 i 出发且可以跳跃 任意 次,能够到达 nums 中的 最大值 是多少。

返回一个数组 ans,其中 ans[i] 是从下标 i 出发可以到达的最大值。

示例 1:

输入: nums = [2,1,3]
输出: [2,2,3]
解释:
对于 i = 0:没有跳跃方案可以获得更大的值。
对于 i = 1:跳到 j = 0,因为 nums[j] = 2 大于 nums[i]。
对于 i = 2:由于 nums[2] = 3 是 nums 中的最大值,没有跳跃方案可以获得更大的值。
因此,ans = [2, 2, 3]。

示例 2:

输入: nums = [2,3,1]
输出: [3,3,3]
解释:
对于 i = 0:向后跳到 j = 2,因为 nums[j] = 1 小于 nums[i] = 2,然后从 i = 2 跳到 j = 1,因为 nums[j] = 3 大于 nums[2]。
对于 i = 1:由于 nums[1] = 3 是 nums 中的最大值,没有跳跃方案可以获得更大的值。
对于 i = 2:跳到 j = 1,因为 nums[j] = 3 大于 nums[2] = 1。
因此,ans = [3, 3, 3]。

说明:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

思路

有一个整数数组 nums,从任意下标 i 出发,可以向后跳到比 nums[i] 小的位置,向前跳到比 nums[i] 大的位置。返回从每一个下标 i 出发跳跃任意次能够到达的 nums 中的最大值。

定义 dp[i] 表示下标 i 所能到达的最大值,记录前缀最大值 preMax 与后缀最小值 suffixMin。如果 preMax[i + 1] <= suffixMin[i + 1]dp[i] = preMax[i + 1],否则 dp[i] = dp[i + 1]

// todo: 树状数组 线段树 单调栈解法

代码


/**
 * @date 2026-05-07 14:41
 */
public class MaxValue3660 {

    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] preMax = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preMax[i + 1] = Math.max(preMax[i], nums[i]);
        }
        int suffixMin = nums[n - 1];
        dp[n - 1] = preMax[n];
        for (int i = n - 2; i >= 0; i--) {
            if (preMax[i + 1] <= suffixMin) {
                dp[i] = preMax[i + 1];
            } else {
                dp[i] = dp[i + 1];
            }
            suffixMin = Math.min(suffixMin, nums[i]);
        }
        return dp;
    }

}

性能

1861.旋转盒子

目标

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

性能

61.旋转链表

目标

给你一个链表的头节点 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 次,再让 slowfast 同时移动。

代码


/**
 * @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;
    }

}

性能

48.旋转图像

目标

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

}

性能

796.旋转字符串

目标

给定两个字符串, s 和 goal。如果在若干次旋转操作之后,s 能变成 goal ,那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

  • 例如, 若 s = 'abcde',在旋转一次之后结果就是'bcdea' 。

示例 1:

输入: s = "abcde", goal = "cdeab"
输出: true

示例 2:

输入: s = "abcde", goal = "abced"
输出: false

说明:

  • 1 <= s.length, goal.length <= 100
  • s 和 goal 由小写英文字母组成

思路

判断能否将 s 经过任意次旋转变为 goal,每次旋转指将最左边的字符放到最右边。

首先判断 sgoal 的长度是否相等,然后再判断 s + s 是否包含 goal

代码


/**
 * @date 2026-05-06 16:30
 */
public class RotateString796 {

    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

性能

788.旋转数字

目标

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后,我们仍可以得到一个有效的,且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字, 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己;2 和 5 可以互相旋转成对方(在这种情况下,它们以不同的方向旋转,换句话说,2 和 5 互为镜像);6 和 9 同理,除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数?

示例:

输入: 10
输出: 4
解释: 
在[1, 10]中有四个好数: 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

说明:

  • N 的取值范围是 [1, 10000]。

思路

判断 1 ~ N 的数字中,不含 3 4 7,且一定要含 2 5 6 9 的数字个数。

// todo:数位 dp

代码


/**
 * @date 2026-05-06 16:45
 */
public class RotatedDigits788 {

    public int rotatedDigits(int n) {
        int res = 0;
        Set<Integer> set = new HashSet<>();
        set.add(2);
        set.add(5);
        set.add(6);
        set.add(9);
        for (int i = 1; i <= n; i++) {
            int num = i;
            boolean valid = false;
            while (num > 0) {
                int d = num % 10;
                if (d == 3 || d == 4 || d == 7) {
                    break;
                }
                if (set.contains(d)){
                    valid = true;
                }
                num /= 10;
            }
            if (num == 0 && valid) {
                res++;
            }
        }
        return res;
    }
}

性能