shelterofly

目标

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。

示例 1：

输出：low = 100, high = 300
输出：[123,234]

示例 2：

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

说明：

• 10 <= low <= high <= 10^9

思路

定义顺序数字为从左到右每一位都比前一位的数字大 1 的整数。返回 [low, high] 范围内的所有顺序数字，按从小到大返回。

枚举数字长度以及开头数字，判断生成的顺序数字是否在 [low, high] 内即可。

代码

/**
 * @date 2026-07-13 9:10
 */
public class SequentialDigits1291 {

    public List<Integer> sequentialDigits(int low, int high) {
        int l = Integer.toString(low).length();
        int r = Integer.toString(high).length();
        List<Integer> res = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            for(int j = 1; j + i <= 10; j++){
                Integer num = genInteger(j, i);
                if (low <= num && num <= high){
                    res.add(num);
                }
            }
        }
        return res;
    }

    public Integer genInteger(int first, int length) {
        int res = 0;
        for (int i = 0; i < length && first < 10; i++) {
            res = res * 10 + first;
            first++;
        }
        return res;
    }

}

性能

目标

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，该数组按 非递减 顺序排序，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。

返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 ui 和 vi 之间存在路径，否则为 false。

示例 1：

输入: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]
输出: [true,false]
解释:
查询 [0,0]：节点 0 有一条到自己的显然路径。
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |1 - 3| = 2，大于 maxDiff。
因此，在处理完所有查询后，最终答案为 [true, false]。

示例 2：

输入: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]
输出: [false,false,true,true]
解释:
生成的图如下：
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |2 - 5| = 3，大于 maxDiff。
查询 [0,2]：节点 0 和节点 2 之间没有边，因为 |nums[0] - nums[2]| = |2 - 6| = 4，大于 maxDiff。
查询 [1,3]：节点 1 和节点 3 之间存在路径通过节点 2，因为 |nums[1] - nums[2]| = |5 - 6| = 1 和 |nums[2] - nums[3]| = |6 - 8| = 2，都小于等于 maxDiff。
查询 [2,3]：节点 2 和节点 3 之间有一条边，因为 |nums[2] - nums[3]| = |6 - 8| = 2，等于 maxDiff。
因此，在处理完所有查询后，最终答案为 [false, false, true, true]。

说明：

• 1 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• nums 按 非递减 顺序排序。
• 0 <= maxDiff <= 10^5
• 1 <= queries.length <= 10^5
• queries[i] == [ui, vi]
• 0 <= ui, vi < n

思路

有 n 个节点编号为 0 ~ n - 1，节点之间的边由非递减数组 nums 与变量 maxDiff 给出，如果两个节点的差值不超过 maxDiff 则表示它们之间有一条无向边。有一个查询数组 queries，返回每次查询的两个节点是否连通。

由于 nums 非递减，只需考虑相邻节点是否连通即可。如果相邻节点不连通，那么跨过这对节点的区间都不连通。可以使用并查集维护连通性。

代码

/**
 * @date 2026-07-09 8:50
 */
public class PathExistenceQueries3532 {

    class UnionFind {
        private final int[] fa;

        public UnionFind(int n) {
            fa = new int[n];
            Arrays.setAll(fa, i -> i);
        }

        public int find(int i) {
            if (i != fa[i]) {
                fa[i] = find(fa[i]);
            }
            return fa[i];
        }

        public void union(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x < y) {
                fa[y] = x;
            } else if (x > y) {
                fa[x] = y;
            }
        }
    }

    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        UnionFind uf = new UnionFind(n);
        for (int i = 1; i < n; i++) {
            if (Math.abs(nums[i] - nums[i - 1]) <= maxDiff) {
                uf.union(i, i - 1);
            }
        }
        boolean[] res = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            res[i] = uf.find(queries[i][0]) == uf.find(queries[i][1]);
        }
        return res;
    }
}

性能

目标

给你一个长度为 m 的字符串 s，其中仅包含数字。另给你一个二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每个 queries[i]，提取 子串 s[li..ri]，然后执行以下操作：

• 将子串中所有 非零数字 按照原始顺序连接起来，形成一个新的整数 x。如果没有非零数字，则 x = 0。
• 令 sum 为 x 中所有数字的 数字和 。答案为 x * sum。

返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。

由于答案可能非常大，请返回其对 10^9 + 7 取余数的结果。

子串 是字符串中的一个连续、非空 字符序列。

示例 1：

输入： s = "10203004", queries = [[0,7],[1,3],[4,6]]
输出： [12340, 4, 9]
解释：
s[0..7] = "10203004"
    x = 1234
    sum = 1 + 2 + 3 + 4 = 10
    因此，答案是 1234 * 10 = 12340。
s[1..3] = "020"
    x = 2
    sum = 2
    因此，答案是 2 * 2 = 4。
s[4..6] = "300"
    x = 3
    sum = 3
    因此，答案是 3 * 3 = 9。

示例 2：

输入： s = "1000", queries = [[0,3],[1,1]]
输出： [1, 0]
解释：
s[0..3] = "1000"
    x = 1
    sum = 1
    因此，答案是 1 * 1 = 1。
s[1..1] = "0"
    x = 0
    sum = 0
    因此，答案是 0 * 0 = 0。

示例 3：

输入： s = "9876543210", queries = [[0,9]]
输出： [444444137]
解释：
s[0..9] = "9876543210"
    x = 987654321
    sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
    因此，答案是 987654321 * 45 = 44444444445。
    返回结果为 44444444445 mod (10^9 + 7) = 444444137。

说明：

• 1 <= m == s.length <= 10^5
• s 仅由数字组成。
• 1 <= queries.length <= 10^5
• queries[i] = [li, ri]
• 0 <= li <= ri < m

思路

有一个数字字符串 s，针对每一个子串 s[queries[i][0], queries[i][1]]，返回其非零数字所表示的数字 乘以 每位数字之和 对 1000000007 取余的结果。

与 3754.连接非零数字并乘以其数字和I 相比，本题的数字是由 queries 给出的子串，需要返回每一个子串的结果。

数位和可以使用前缀和快速计算。子串非零数字所表示的数字也可以通过前缀计算。

区间 [l, r] 所表示的数字对 MOD 取模的值为 (prefixNum[r + 1] + MOD - prefixNum[l] * base[k] % MOD) % MOD，例如，1230456，[2, 4] 中的非零数字所表示的数字是 34，它等于 prefixNum[5]:1234 - prefixNum[2]:12 * 100，其中 100 = 10^k，k 表示 [l, r] 中非零数字的个数。

代码

/**
 * @date 2026-07-08 9:50
 */
public class SumAndMultiply3756 {

    public int[] sumAndMultiply(String s, int[][] queries) {
        int n = s.length();
        int[] prefix = new int[n + 1];
        int[] prefixLength = new int[n + 1];
        long[] prefixNum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            int d = s.charAt(i) - '0';
            prefix[i + 1] = prefix[i] + d;
            prefixLength[i + 1] = prefixLength[i] + (d != 0 ? 1 : 0);
            prefixNum[i + 1] = (prefixNum[i] * (d != 0 ? 10 : 1) + d) % MOD;
        }
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < ql; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int sum = prefix[r + 1] - prefix[l];
            long x = (prefixNum[r + 1] + MOD - prefixNum[l] * base[prefixLength[r + 1] - prefixLength[l]] % MOD) % MOD;
            res[i] = (int) (x * sum % MOD);
        }
        return res;
    }

}

性能

目标

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

说明：

• 1 <= intervals.length <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• 对于所有的 i != j：intervals[i] != intervals[j]

思路

有一个区间列表，删除被其它区间覆盖的区间，返回剩余的区间。区间 [a, b] 被区间[c, d] 覆盖需满足 c <= a && b <= d。

根据左端点从小到大排序，右端点从大到小排序。按顺序遍历排序后的数组，当前区间的左端点一定大于等于之前的区间的左端点，只需要判断右端点是否超过前面记录的最长右端点即可。

代码

/**
 * @date 2026-07-06 9:00
 */
public class RemoveCoveredIntervals1288 {

    public int removeCoveredIntervals(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> {
            int compare = a[0] - b[0];
            return compare != 0 ? compare : b[1] - a[1];
        });
        int r = intervals[0][1];
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (intervals[i][1] <= r) {
                res++;
            } else {
                r = intervals[i][1];
            }
        }
        return n - res;
    }
}

性能

目标

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。

示例 3：

输入：s = "abc"
输出：1

说明：

• 3 <= s.length <= 5 x 10^4
• s 只包含字符 a，b 和 c 。

思路

有一个字符串只包含三个字符 a b c，求这三个字符至少出现一次的子串个数。

直接的想法是计算这三个字符出现次数的前缀和，然后使用滑动窗口。使用前缀和来判断窗口内的子串是否满足条件，如果 [l, r] 满足条件，那么 [l, r ~ n - 1] 也满足条件。

判断字符是否至少出现一次可以不用前缀和，使用三个变量记录它们上次出现的下标，如果小于左端点则用 -1 标记。

代码

/**
 * @date 2026-06-30 9:14
 */
public class NumberOfSubstrings1358 {

    public int numberOfSubstrings(String s) {
        int n = s.length();
        int a = -1, b = -1, c = -1;
        int l = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a') {
                a = i;
            } else if (s.charAt(i) == 'b') {
                b = i;
            } else {
                c = i;
            }
            while (a >= 0 && b >= 0 && c >= 0) {
                res += n - i;
                if (a <= l) {
                    a = -1;
                } else if (b <= l) {
                    b = -1;
                } else if (c <= l) {
                    c = -1;
                }
                l++;
            }
        }
        return res;
    }

}

性能

目标

给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

• arr 中 第一个 元素必须为 1 。
• 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。

你可以执行以下 2 种操作任意次：

• 减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
• 重新排列 arr 中的元素，你可以以任意顺序重新排列。

请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。

示例 1：

输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。

示例 2：

输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。

示例 3：

输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。

说明：

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

思路

有一个正整数数组 arr，可以将任意元素变成比它更小的正整数，也可以按任意顺序重新排列元素。需要将 arr 变成目标数组，使得第一个元素为 1，且相邻元素差的绝对值不超过 1。返回目标数组可能的最大值。

根据题目要求，第一个元素必须是 1，且相邻元素差的绝对值不超过 1，要使元素值变大只能 +1，且该元素只能由大于等于它的元素转化而来。

贪心策略，从小到大排序数组，遍历数组记录最大值，由于元素值都大于 0，都可以操作成 1，当元素值小于最大值时直接跳过，否则，将元素操作成最大值加一。越大的元素越晚操作，可以使最大值更大。

由于最大值不超过 n，可以将大于 n 的元素都视为 n，这样可以使用计数排序优化。

代码

/**
 * @date 2026-06-29 18:11
 */
public class MaximumElementAfterDecrementingAndRearranging1846 {

    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int res = 0;
        for (int num : arr) {
            if (num <= res) {
                continue;
            }
            res++;
        }
        return res;
    }

}

性能