标签： medium

目标

给你一个整数数组 nums 和一个整数 target 。

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

示例 1：

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2：

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3：

输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）

说明：

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

思路

统计满足条件的子序列个数，要求子序列最小元素与最大元素之和小于等于 target。

排序后考虑首位元素组成的子序列，如果满足条件，那么有 2^n-1 个，将左指针右移继续判断，如果不满足条件，右指针左移继续判断。

代码

/**
 * @date 2025-06-30 10:47
 */
public class NumSubseq1498 {

    public int numSubseq(int[] nums, int target) {
        int mod = 1000000007;
        Arrays.sort(nums);
        if (nums[0] * 2 > target) {
            return 0;
        }
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        int res = 0;
        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                res = (res + pow(2, r - l, mod)) % mod;
                l++;
            } else {
                r--;
            }
        }
        return res;
    }

    public int pow(int base, int exp, int mod) {
        long res = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = res * base % mod;
            }
            base = (int) (((long) base * base) % mod);
            exp >>= 1;
        }
        return (int) res;
    }

}

性能

目标

给你一个二进制字符串 s 和一个正整数 k 。

请你返回 s 的 最长 子序列的长度，且该子序列对应的 二进制 数字小于等于 k 。

注意：

• 子序列可以有 前导 0 。
• 空字符串视为 0 。
• 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

示例 1：

输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。

示例 2：

输入：s = "00101001", k = 1
输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。

说明：

• 1 <= s.length <= 1000
• s[i] 要么是 '0' ，要么是 '1' 。
• 1 <= k <= 10^9

思路

有一个二进制字符串 s，求满足条件的最长子序列长度，要求子序列表示的二进制数字小于等于 k。

可以计算出 k 的二进制表示 target，长度 l 最大为 30。问题的关键是能否找到长度为 l 的子序列，使得它小于等于 target，显然长度小于 l 的二进制数字必定小于等于 target。但是可以包含前导零，那么只要是 0 就可以加到左边。

贪心策略：判断长为 l 的后缀是否小于等于 k，如果是，则结果加上 l，否则加上 l - 1，然后再累加上 0 ~ n - l - 1 中 0 的个数即可。

代码

/**
 * @date 2025-06-26 8:47
 */
public class LongestSubsequence2311 {

    public int longestSubsequence(String s, int k) {
        int res = 0;
        s = "0" + s;
        int n = s.length();
        long base = 2;
        long v = s.charAt(n - 1) - '0';
        for (int i = n - 1; i > 0; i--) {
            if (v <= k) {
                res++;
                v += base * (s.charAt(i - 1) - '0');
                if (base <= k) {
                    base *= 2;
                }
            } else if (s.charAt(i) == '0') {
                res++;
            }
        }
        return res;
    }

}

性能

目标

给你一个字符串 word 和一个整数 k。

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j 都成立，则认为 word 是 k 特殊字符串。

此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

示例 1：

输入：word = "aabcaba", k = 0
输出：3
解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。

示例 2：

输入：word = "dabdcbdcdcd", k = 2
输出：2
解释：可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd"，此时 freq('b') == 2，freq('c') == 3，freq('d') == 4。

示例 3：

输入：word = "aaabaaa", k = 2
输出：1
解释：可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此，word 变为 "aaaaaa"，此时每个字母的频率都是 6。

说明：

• 1 <= word.length <= 10^5
• 0 <= k <= 10^5
• word 仅由小写英文字母组成。

思路

统计字符串中字符的频次，如果频次最大值减去频次最小值小于等于 k 则称为 k 特殊字符，计算使得字符串变为 k 特殊字符串最少需要删除多少个字符。

贪心策略：要删就将频次最小的字母全部删掉，关注的是最终的最大与最小频次，如果只删除部分则会使差值变大。

算法步骤如下：

1. 统计字母出现频次（去除掉频次为 0 的）并排序。
2. 从小到大枚举频次最小值 i，需要删掉的字符个数为 Σl + Σ(r - i - k)， 其中 l 表示所有小于 i 的频次，r 表示所有大于 i + k 的频次。
3. 取其最小值。

代码

/**
 * @date 2025-06-21 20:58
 */
public class MinimumDeletions3085 {

    public int minimumDeletions(String word, int k) {
        int res = Integer.MAX_VALUE;
        int[] cnt = new int[26];
        char[] chars = word.toCharArray();
        for (char c : chars) {
            cnt[c - 'a']++;
        }
        Arrays.sort(cnt);
        List<Integer> frequency = new ArrayList<>();
        for (int i : cnt) {
            if (i > 0) {
                frequency.add(i);
            }
        }
        int l = 0;
        int n = frequency.size();
        for (Integer i : frequency) {
            int deletions = l;
            l += i;
            int r = i + k;
            for (int j = n - 1; frequency.get(j) > r; j--) {
                deletions += frequency.get(j) - r;
            }
            res = Math.min(res, deletions);
        }
        return res;
    }

}

性能

目标

给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：

• 'N'：向北移动 1 个单位。
• 'S'：向南移动 1 个单位。
• 'E'：向东移动 1 个单位。
• 'W'：向西移动 1 个单位。

初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。

请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。

曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。

示例 1：

输入：s = "NWSE", k = 1
输出：3
解释：
将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。
移动操作 位置 (x, y) 曼哈顿距离 最大值
s[0] == 'N' (0, 1) 0 + 1 = 1 1
s[1] == 'W' (-1, 1) 1 + 1 = 2 2
s[2] == 'N' (-1, 2) 1 + 2 = 3 3
s[3] == 'E' (0, 2) 0 + 2 = 2 3
执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。

示例 2：

输入：s = "NSWWEW", k = 3
输出：6
解释：
将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。
执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。

说明：

• 1 <= s.length <= 10^5
• 0 <= k <= s.length
• s 仅由 'N'、'S'、'E' 和 'W' 。

思路

从原点 (0, 0) 出发，根据操作序列 s 朝四个方向移动，最多可以修改序列中 k 个方向，求能够到达的距离原点的最大曼哈顿距离。

遍历过程中记录距离变小的次数，每修改一次可以使得最大距离加 2。

网友指出每走一步可能增大的距离最多为 2 * k，但是不能超过往一个方向一直走的情况，即当前走的步数 i + 1。

代码

/**
 * @date 2025-06-20 21:47
 */
public class MaxDistance3443 {

    private static final Map<Character, int[]> MAP = new HashMap<>();

    static {
        MAP.put('N', new int[]{0, 1});
        MAP.put('S', new int[]{0, -1});
        MAP.put('E', new int[]{1, 0});
        MAP.put('W', new int[]{-1, 0});
    }

    public int maxDistance(String s, int k) {
        int res = 0;
        int d = 0;
        int prev = 0;
        int backCnt = 0;
        int[] curPos = new int[]{0, 0};
        char[] move = s.toCharArray();
        for (char dir : move) {
            prev = d;
            int[] delta = MAP.get(dir);
            int dx = delta[0];
            int dy = delta[1];
            curPos[0] += dx;
            curPos[1] += dy;
            d = Math.abs(curPos[0]) + Math.abs(curPos[1]);
            if (prev > d) {
                backCnt++;
            }
            res = Math.max(res, d + Math.min(backCnt, k) * 2);
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都 恰好 出现在一个子序列中。

在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的 最少 子序列数目。

子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。

示例 1：

输入：nums = [3,6,1,2,5], k = 2
输出：2
解释：
可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。
第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。
第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。
由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2 。

示例 2：

输入：nums = [1,2,3], k = 1
输出：2
解释：
可以将 nums 划分为两个子序列 [1,2] 和 [3] 。
第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。
第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。
由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。

示例 3：

输入：nums = [2,2,4,5], k = 0
输出：3
解释：
可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。
第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。
第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。
第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。
由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。

说明：

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

思路

将数组划分为子序列，要求子序列中最大元素与最小元素的差不超过 k，并且相同的元素只能被划分到同一个子序列中，求划分的最少子序列项目。

将数组排序然后遍历，记录当前划分的最小元素，尽可能地将符合条件的元素都划分到一起，如果差值超过 k 则一定需要划分，更新最小元素。

代码

/**
 * @date 2025-06-19 9:00
 */
public class PartitionArray2294 {

    public int partitionArray(int[] nums, int k) {
        Arrays.sort(nums);
        int res = 1;
        int min = nums[0];
        for (int num : nums) {
            if (num - min <= k) {
                continue;
            }
            res++;
            min = num;
        }
        return res;
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。

将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件：

• 子数组中 任意 两个元素的差必须 小于或等于 k 。

返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。

示例 1：

输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
输出：[[1,1,3],[3,4,5],[7,8,9]]
解释：
每个数组中任何两个元素之间的差小于或等于 2。

示例 2：

输入：nums = [2,4,2,2,5,2], k = 2
输出：[]
解释：
将 nums 划分为 2 个长度为 3 的数组的不同方式有：
[[2,2,2],[2,4,5]] （及其排列）
[[2,2,4],[2,2,5]] （及其排列）
因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。

示例 3：

输入：nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14
输出：[[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]
解释：
每个数组中任何两个元素之间的差小于或等于 14。

说明：

• n == nums.length
• 1 <= n <= 10^5
• n 是 3 的倍数
• 1 <= nums[i] <= 10^5
• 1 <= k <= 10^5

思路

将数组划分为 n / 3 个长度为 3 的数组，使得子数组内元素的差值不超过 k。如果有多个答案返回任意一个即可，如果满足条件的子数组不够 n / 3，返回空数组。

注意将原数组划分为 n / 3 个数组，先从数组中取 3 个元素，再从剩余元素中取 3 个 …… 。并不是取不重复的长度为 3 的子数组。

排序后每三个元素一组判断即可，因为相邻元素的差值最小，只要有一组不满足条件，那么个数就不够，直接返回空数组。

代码

/**
 * @date 2025-06-18 0:08
 */
public class DivideArray2966 {

    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int[][] res = new int[n / 3][];
        for (int i = 1; i < n - 1; i += 3) {
            int cur = nums[i];
            int prev = nums[i - 1];
            int next = nums[i + 1];
            if (next - prev > k) {
                return new int[][]{};
            }
            res[i / 3] = new int[]{prev, cur, next};
        }
        return res;
    }

}

性能

目标

给你一个整数 num 。你可以对它进行以下步骤共计 两次：

• 选择一个数字 x (0 <= x <= 9).
• 选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
• 将 num 中所有出现 x 的数位都用 y 替换。

令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值 。

注意，新的整数（a 或 b）必须不能 含有前导 0，并且 非 0。

示例 1：

• 输入：num = 555
• 输出：888
• 解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
• 第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
• 现在，我们有 a = 999 和 b = 111 ，最大差值为 888

示例 2：

• 输入：num = 9
• 输出：8
• 解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
• 第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
• 现在，我们有 a = 9 和 b = 1 ，最大差值为 8

示例 3：

• 输入：num = 123456
• 输出：820000

示例 4：

• 输入：num = 10000
• 输出：80000

示例 5：

• 输入：num = 9288
• 输出：8700

说明：

• 1 <= num <= 10^8

思路

从 num 中选择一个数字 d，可以将 num 中所有的 d 都替换成另一个数字（不允许包含前导零），返回能够得到的最大值与最小值的差。

与 2566.替换一个数字后的最大差值 的区别是不能有前导零。

最大值：找到第一个不是 9 的位置，将 num 中所有与之相同的数字替换为 9。

最小值：找到第一个不是 1 的位置，如果是首位，将 num 中所有与之相同的数字替换为 1，否则替换为 0。

代码

/**
 * @date 2025-06-15 18:15
 */
public class MaxDiff1432 {

    public int maxDiff(int num) {
        int a = num, b = num;
        String s = String.valueOf(num);
        int n = s.length();
        int m = (int) Math.pow(10, n - 1);
        int ar = '-', br = '-';
        boolean first = false;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (ar == '-' && c != '9') {
                ar = c;
            }
            if (br == '-' && c > '1') {
                br = c;
                first = i == 0;
            }
            if (ar == c) {
                a += (9 - (c - '0')) * m;
            }
            if (br == c) {
                b -= ((c - '0') - (first ? 1 : 0)) * m;
            }
            m /= 10;
        }
        return a - b;
    }
}

性能

目标

给你一个字符串 s 。它可能包含任意数量的 '' 字符。你的任务是删除所有的 '' 字符。

当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：

• 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。

请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。

示例 1：

输入：s = "aaba*"
输出："aab"
解释：
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。

示例 2：

输入：s = "abc"
输出："abc"
解释：
字符串中没有 '*' 字符。

说明：

• 1 <= s.length <= 10^5
• s 只含有小写英文字母和 '*' 字符。
• 输入保证操作可以删除所有的 '*' 字符。

思路

有一个包含任意数量 * 的字符串，每次操作可以删掉 * 以及它左侧的一个字典序最小的字符，如果有多个可以，删除任意一个。求删除所有 * 之后能够得到的 字典序最小的字符串。

贪心算法，优先删除左侧字典序最小且下标最大的字符即可。

代码

/**
 * @date 2025-06-07 9:37
 */
public class ClearStars3170 {

    public String clearStars(String s) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return b[1] - a[1];
        });
        char[] chars = s.toCharArray();
        int n = chars.length;
        for (int i = 0; i < n; i++) {
            char c = chars[i];
            if (c != '*') {
                q.offer(new int[]{c, i});
            } else {
                q.poll();
            }
        }
        char[] res = new char[q.size()];
        PriorityQueue<int[]> tmp = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        tmp.addAll(q);
        int i = 0;
        while (!tmp.isEmpty()) {
            int[] c = tmp.poll();
            res[i++] = (char) c[0];
        }
        return new String(res);
    }
}

性能

目标

给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

• 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
• 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。

请你返回纸上能写出的字典序最小的字符串。

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。

示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。

示例 3：

输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="bdda" ，t="" 。
执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。

说明：

• 1 <= s.length <= 10^5
• s 只包含小写英文字母。

思路

• 首先统计字符串中的字符个数，要使输出的字典序最小，那么第一个字符一定是字符串中出现过的字典序最小的字符
• 为了将该字符打印到首位，需要先定位到这个字符，它前面的字符都会被暂存到栈中
• 确定了第一个字典序最小的字符之后，下一个字符有两个选择，取栈顶字符，或者找到剩下的字符中的字典序最小的

需要维护剩余字符中最小字典序的字符，可以使用有序集合或者后缀。

代码

/**
 * @date 2025-06-06 8:47
 */
public class RobotWithString2434 {

    public String robotWithString(String s) {
        TreeMap<Character, Integer> map = new TreeMap<>();
        char[] chars = s.toCharArray();
        int n = chars.length;
        for (char c : chars) {
            map.merge(c, 1, Integer::sum);
        }
        ArrayDeque<Character> q = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < n) {
            Character min = map.firstKey();
            while (i < n && chars[i] != min) {
                char c = chars[i++];
                q.offer(c);
                map.merge(c, -1, Integer::sum);
                if (map.get(c) == 0) {
                    map.remove(c);
                }
            }
            sb.append(min);
            map.merge(min, -1, Integer::sum);
            if (map.get(min) == 0) {
                map.remove(min);
            }
            i++;
            while (!q.isEmpty() && (map.size() == 0 || q.peekLast() <= map.firstKey())) {
                sb.append(q.pollLast());
            }
        }
        return sb.toString();
    }

}

性能