数组 – 第 3 页 – shelterofly

目标

有一条无限长的数轴，原点在 0 处，沿着 x 轴正方向无限延伸。

给你一个二维数组 queries ，它包含两种操作：

操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处没有任何障碍物。
操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要完全放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块不能被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并不是真的放置这个物块。每个查询都是相互独立的。

请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为 true ，否则为 false 。

示例 1：

输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
输出：[false,true,true]
解释：
查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

示例 2：

输入：queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
输出：[true,true,false]
解释：
查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。
查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以被放置。

说明：

1 <= queries.length <= 15 * 10^4
2 <= queries[i].length <= 3
1 <= queries[i][0] <= 2
1 <= x, sz <= min(5 10^4, 3 queries.length)
输入保证操作 1 中，x 处不会有障碍物。
输入保证至少有一个操作类型 2 。

思路

代码

性能

目标

给你一个整数数组 nums 。

请你将 nums 中每一个元素都替换为它的各个数位之和。

请你返回替换所有元素以后 nums 中的最小元素。

示例 1：

输入：nums = [10,12,13,14]
输出：1
解释：
nums 替换后变为 [1, 3, 4, 5] ，最小元素为 1 。

示例 2：

输入：nums = [1,2,3,4]
输出：1
解释：
nums 替换后变为 [1, 2, 3, 4] ，最小元素为 1 。

示例 3：

输入：nums = [999,19,199]
输出：10
解释：
nums 替换后变为 [27, 10, 19] ，最小元素为 10 。

说明：

1 <= nums.length <= 100
1 <= nums[i] <= 10^4

思路

将数组中的元素换成其各位数字之和，返回替换后数组的最小值。

代码


/**
 * @date 2026-05-29 0:03
 */
public class MinElement3300 {

    public int minElement(int[] nums) {
        int res = Integer.MAX_VALUE;
        for (int num : nums) {
            int sum = 0;
            while (num > 0){
                sum += num % 10;
                num /= 10;
            }
            res = Math.min(res, sum);
        }
        return res;
    }
}

性能

目标

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。

如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。

源数组中可能存在重复项。

注意：数组 A 在轮转 x 个位置后得到长度相同的数组 B ，使得对于每一个有效的下标 i，满足 B[i] == A[(i+x) % A.length]。

示例 1：

输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 2 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。

示例 2：

输入：nums = [2,1,3,4]
输出：false
解释：源数组无法经轮转得到 nums 。

示例 3：

输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 为有序的源数组。
可以轮转 x = 0 个位置（即不轮转）得到 nums 。

说明：

1 <= nums.length <= 100
1 <= nums[i] <= 100

思路

判断循环数组能否通过若干右移变成非递减。

根据题目要求，循环数组最多只能出现一次严格递减。

代码


/**
 * @date 2026-05-26 10:16
 */
public class Check1752 {

    public boolean check(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        if (nums[n - 1] > nums[0]) {
            cnt++;
        }
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                cnt++;
            }
            if (cnt > 1) {
                return false;
            }
        }
        return true;
    }
}

性能

目标

给你两个正整数数组 arr1 和 arr2 。

正整数的前缀是其最左边的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是。

设若整数 c 是整数 a 和 b 的公共前缀，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

说明：

1 <= arr1.length, arr2.length <= 5 * 10^4
1 <= arr1[i], arr2[i] <= 10^8

思路

有两个数组 arr1 和 arr2，返回所有数对 (arr1[i], arr2[j]) 中最长公共前缀的长度。

将 arr1 中每个数字的前缀都计入哈希表，同时判断 arr2 中每个元素的的前缀是否在哈希表中，取前缀的最大长度即可。

或者可以将 arr1 的每个元素都加入 字典树，枚举 arr2 的每一个元素，计算其在字典树中公共前缀的最大长度。

代码


/**
 * @date 2026-05-21 9:03
 */
public class LongestCommonPrefix3043 {

    static class Trie {
        public Trie[] children = new Trie[10];

        public void insert(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    cur.children[d] = new Trie();
                }
                cur = cur.children[d];
            }
        }

        public int prefixLength(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            int l = 0;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    break;
                }
                cur = cur.children[d];
                l++;
            }
            return l;
        }
    }

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Trie root = new Trie();
        for (int num : arr1) {
            root.insert(num);
        }
        int res = 0;
        for (int num : arr2) {
            res = Math.max(res, root.prefixLength(num));
        }
        return res;
    }

}

性能

目标

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须尽可能减少整个过程的操作步骤。

示例 1：

输入：nums = [1,3,5]
输出：1

示例 2：

输入：nums = [2,2,2,0,1]
输出：0

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：这道题与 153.寻找旋转排序数组中的最小值类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

思路

数组 nums 由一个升序数组经过旋转而成，求数组的最小值，要求时间复杂度为 O(log n)。

与 153.寻找旋转排序数组中的最小值不同的是可能存在重复元素。预处理 r，使它指向不等于 nums[0] 的最大下标即可。

代码


/**
 * @date 2026-05-18 11:13
 */
public class FindMin154 {

    public int findMin(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (r >= 0 && nums[0] == nums[r]) {
            r--;
        }
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= nums[0]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return nums[l % n];
    }

}

性能

目标

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

说明：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路

数组 nums的 元素值互不相同，它由一个升序数组经过旋转而成，求数组的最小值，要求时间复杂度为 O(log n)。

所谓旋转，可以视为循环数组向右移动。虽然不是整体有序，但还是可以使用二分。由于元素值互不相同，根据第一个元素可以判断属于哪一部分，进而可以确定搜索方向。

如果大于第一个元素向右搜索，如果小于则向左搜索，注意如果返回的下标是 n 需要对 n 取余指向第一个元素。

代码


/**
 * @date 2024-08-31 22:37
 */
public class FindMin153 {

    public int findMin_v2(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= nums[0]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return nums[l % n];
    }

}

性能

目标

给你一个整数数组 nums ，如果它是数组 base[n] 的一个排列，我们称它是个好数组。

base[n] = [1, 2, ..., n - 1, n, n] （换句话说，它是一个长度为 n + 1 且包含 1 到 n - 1 恰好各一次，包含 n 两次的一个数组）。比方说，base[1] = [1, 1] ，base[3] = [1, 2, 3, 3] 。

如果数组是一个好数组，请你返回 true ，否则返回 false 。

注意：数组的排列是这些数字按任意顺序排布后重新得到的数组。

示例 1：

输入：nums = [2, 1, 3]
输出：false
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 。但是 base[3] 有 4 个元素，但数组 nums 只有 3 个元素，所以无法得到 base[3] = [1, 2, 3, 3] 的排列，所以答案为 false 。

示例 2：

输入：nums = [1, 3, 3, 2]
输出：true
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 ，可以看出数组是 base[3] = [1, 2, 3, 3] 的一个排列（交换 nums 中第二个和第四个元素）。所以答案为 true 。

示例 3：

输入：nums = [1, 1]
输出：true
解释：因为数组的最大元素是 1 ，唯一可以构成这个数组的 base[n] 对应的 n = 1，可以看出数组是 base[1] = [1, 1] 的一个排列。所以答案为 true 。

示例 4：

输入：nums = [3, 4, 4, 1, 2, 1]
输出：false
解释：因为数组的最大元素是 4 ，唯一可以构成这个数组的 base[n] 对应的 n = 4 。但是 base[n] 有 5 个元素而 nums 有 6 个元素。所以答案为 false 。

说明：

1 <= nums.length <= 100
1 <= num[i] <= 200

思路

有一个长度为 n + 1 的数组 nums，判断它是否是数组 [1, 2, 3, ……, n - 1, n, n] 的一个排列。

注意到目标数组的元素与下标的关系为 nums[i] = i + 1, i < n，特殊处理后两个位置，使用一个指针 p 指向下标 n - 1。遍历数组 nums 前 n 个元素，如果当前位置的元素值不满足条件，就将其与满足条件的位置（当 nums[i] < n 时，取 nums[i] - 1，当 nums[i] == n 时取 p，当 nums[i] > n 直接返回 false）上的元素值交换，如果目标位置的元素值已经满足条件或者 n 的出现次数超过两次，返回 false。最后返回 nums[n] == n 即可。

代码


/**
 * @date 2026-05-14 9:40
 */
public class IsGood2784 {

    public boolean isGood(int[] nums) {
        int n = nums.length - 1;
        int p = n - 1;
        for (int i = 0; i < n; i++) {
            while (nums[i] != i + 1) {
                int index = nums[i] - 1;
                if (nums[i] > n || (nums[i] < n && nums[index] == nums[i]) || (nums[i] == n && p > n)) {
                    return false;
                }
                if (nums[i] == n) {
                    index = p++;
                }
                int tmp = nums[index];
                nums[index] = nums[i];
                nums[i] = tmp;
            }
        }
        return nums[n] == n;
    }
}

性能

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;
    }
}

性能

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;
            }
        }
    }

}

性能

1848.到目标元素的最小距离

目标

给你一个整数数组 nums （下标从 0 开始计数）以及两个整数 target 和 start ，请你找出一个下标 i ，满足 nums[i] == target 且 abs(i - start) 最小化。注意：abs(x) 表示 x 的绝对值。

返回 abs(i - start) 。

题目数据保证 target 存在于 nums 中。

示例 1：

输入：nums = [1,2,3,4,5], target = 5, start = 3
输出：1
解释：nums[4] = 5 是唯一一个等于 target 的值，所以答案是 abs(4 - 3) = 1 。

示例 2：

输入：nums = [1], target = 1, start = 0
输出：0
解释：nums[0] = 1 是唯一一个等于 target 的值，所以答案是 abs(0 - 0) = 0 。

示例 3：

输入：nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
输出：0
解释：nums 中的每个值都是 1 ，但 nums[0] 使 abs(i - start) 的结果得以最小化，所以答案是 abs(0 - 0) = 0 。

说明：

1 <= nums.length <= 1000
1 <= nums[i] <= 10^4
0 <= start < nums.length
target 存在于 nums 中

思路

返回元素值为 target 的下标与 start 的最短距离。

可以从 0 开始遍历，也可以枚举距离从 start 向两边遍历。

代码


/**
 * @date 2026-04-13 8:52
 */
public class GetMinDistance1848 {

    public int getMinDistance(int[] nums, int target, int start) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                res = Math.min(res, Math.abs(i - start));
            }
        }
        return res;
    }
}

2026 年 9 月
一	二	三	四	五	六	日
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30