标签： 贪心算法

目标

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

你可以对数组中的每个元素 最多 执行 一次 以下操作：

• 将一个在范围 [-k, k] 内的整数加到该元素上。

返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。

示例 1：

输入： nums = [1,2,2,3,3,4], k = 2
输出： 6
解释：
对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。

示例 2：

输入： nums = [4,4,4,4], k = 1
输出： 3
解释：
对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。

说明：

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

思路

有一个整数数组 nums，允许对数组中的每个元素加上 [-k, k] 的整数，求操作后数组中不同元素的最大个数。

先对数组进行排序，计算相同元素个数，同时记录前一个元素操作后的最大值 + 1，当前相同元素的个数可以操作变成不同元素的范围是 [Math.max(nums[start] - k, prev), Math.min(nums[start] + k, l + cnt - 1)]。

代码

/**
 * @date 2025-10-20 10:09
 */
public class MaxDistinctElements3397 {

    public int maxDistinctElements(int[] nums, int k) {
        int n = nums.length;
        int i = 0;
        int prev = Integer.MIN_VALUE;
        int res = 0;
        Arrays.sort(nums);
        while (i < n) {
            int start = i;
            while (i < n && nums[i] == nums[start]) {
                i++;
            }
            int cnt = i - start;
            int l = Math.max(nums[start] - k, prev);
            int r = Math.min(nums[start] + k, l + cnt - 1);
            res += r - l + 1;
            prev = r + 1;
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

• 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

示例 1：

输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。

示例 2：

输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。

说明：

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

思路

有一个数组，可以执行 任意 次操作，每次操作可以将任意元素加上或者减去 value，求数组中缺失的最小非负整数的最大值。

题目要求返回缺失的最小非负整数，可以从 0 开始枚举每一个整数 target，问题是如何判断数组中是否存在元素 nums[i] + k * value == target。两边同时对 value 取余可得 nums[i] ≡ target (mod value)。

可以对 nums[i] % value 计数，枚举 target 判断是否还剩有同余元素即可。

代码

/**
 * @date 2025-10-16 8:46
 */
public class FindSmallestInteger2598 {

    public int findSmallestInteger(int[] nums, int value) {
        int[] cnt = new int[value];
        for (int num : nums) {
            int rem = num % value;
            rem = rem >= 0 ? rem : rem + value;
            cnt[rem]++;
        }
        int res = 0;
        while (true) {
            int rem = res % value;
            if (cnt[rem] > 0) {
                cnt[rem]--;
            } else {
                return res;
            }
            res++;
        }
    }

}

性能

目标

在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。

给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：

• 总共有 n 种语言，编号从 1 到 n 。
• languages[i] 是第 i 位用户掌握的语言集合。
• friendships[i] = [ui, vi] 表示 ui 和 vi 为好友关系。

你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。

请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。

示例 1：

输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出：1
解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。

示例 2：

输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出：2
解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。

说明：

• 2 <= n <= 500
• languages.length == m
• 1 <= m <= 500
• 1 <= languages[i].length <= n
• 1 <= languages[i][j] <= n
• 1 <= u​​​​​​i < v​​​​​​i <= languages.length
• 1 <= friendships.length <= 500
• 所有的好友关系 (u​​​​​i, v​​​​​​i) 都是唯一的。
• languages[i] 中包含的值互不相同。

思路

有 n 种语言，编号 1 ~ n，同时有 m 个用户，编号从 1 ~ m，languages[i] 表示编号为 i + 1 的用户所掌握的语言，friendships 数组记录了用户的朋友关系。现在可以选择 一门 语言教会任意用户使得所有朋友都可以沟通，求需要教的最少人数。

找出无法沟通的朋友关系（统计总人数 total），统计每一种语言的人数 cnt[i]（注意去重），最少人数即 total - max(cnt)。

代码

/**
 * @date 2025-09-10 8:49
 */
public class MinimumTeachings1733 {

    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        int[] cnt = new int[n + 1];
        HashSet<Integer>[] lang = new HashSet[m + 1];
        Arrays.setAll(lang, x -> new HashSet<>());
        for (int i = 0; i < m; i++) {
            for (int language : languages[i]) {
                lang[i + 1].add(language);
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int[] friendship : friendships) {
            int a = friendship[0];
            int b = friendship[1];
            HashSet<Integer> tmp = new HashSet<>(lang[a]);
            tmp.retainAll(lang[b]);
            if (tmp.size() == 0) {
                if (!set.contains(a)) {
                    for (Integer t : lang[a]) {
                        cnt[t]++;
                    }
                    set.add(a);
                }
                if (!set.contains(b)) {
                    for (Integer t : lang[b]) {
                        cnt[t]++;
                    }
                    set.add(b);
                }
            }
        }
        return set.size() - Arrays.stream(cnt).max().orElse(0);
    }

}

性能

目标

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10^-5 以内的结果都会视为正确结果。

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

说明：

• 1 <= classes.length <= 10^5
• classes[i].length == 2
• 1 <= passi <= totali <= 10^5
• 1 <= extraStudents <= 10^5

思路

有一个二维数组 classes， classes[i][0] 表示班级 i 期末考试中通过考试的人数，classes[i][1] 表示班级 i 的总人数。有 extraStudents 个聪明学生一定可以通过期末考试，现在需要将这些学生分配到班级中去，使得班级通过率的平均值最大。返回最大平均通过率。

为了使平均值更大，可以优先将聪明学生安排到通过率提升最大的班级，使用优先队列。

代码

/**
 * @date 2025-09-01 21:21
 */
public class MaxAverageRatio1792 {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> (int) (((b[1] - b[0]) * (long) a[1] * (a[1] + 1) - (a[1] - a[0]) * (long) b[1] * (b[1] + 1)) % 1000000007));
        for (int[] item : classes) {
            q.offer(item);
        }
        for (int i = 0; i < extraStudents; i++) {
            int[] peek = q.poll();
            peek[0]++;
            peek[1]++;
            q.offer(peek);
        }
        double res = 0.0;
        for (int[] item : classes) {
            res += (double) item[0] / item[1];
        }
        return res / classes.length;
    }

}

性能

目标

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

说明：

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

思路

返回数组的全 0 子数组个数。

长度为 k 的子数组个数为 (1 + k) * k / 2。可以使用贪心策略，如果当前元素是 0 找到以它为起点的最长连续 0 数组，计算子数组个数。

代码

/**
 * @date 2025-08-19 8:54
 */
public class ZeroFilledSubarray2348 {

    public long zeroFilledSubarray(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int i = 0;
        while (i < n){
            if (nums[i] != 0){
                i++;
                continue;
            }
            int start = i;
            while (i < n && nums[i] == 0){
                i++;
            }
            int cnt = i - start;
            res += (1L + cnt) * cnt / 2;
        }

        return res;
    }
}

性能

目标

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

• 删除子字符串 "ab" 并得到 x 分。
  • 比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
• 删除子字符串"ba" 并得到 y 分。
  • 比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20

说明：

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

思路

贪心策略，优先处理分值高的字符串。

代码

/**
 * @date 2025-07-23 9:01
 */
public class MaximumGain1717 {

    public int maximumGain(String s, int x, int y) {
        char prev, cur;
        int max, min;
        if (x > y) {
            prev = 'a';
            cur = 'b';
            max = x;
            min = y;
        } else {
            prev = 'b';
            cur = 'a';
            max = y;
            min = x;
        }
        Deque<Character> q = new ArrayDeque<>();
        q.push('^');
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (q.peek() == prev && c == cur) {
                q.pop();
                res += max;
            } else {
                q.push(c);
            }
        }
        q.removeLast();
        Deque<Character> p = new ArrayDeque<>();
        p.push('^');
        while (!q.isEmpty()) {
            if (q.peekLast() == prev && p.peek() == cur) {
                q.removeLast();
                p.pop();
                res += min;
            } else {
                p.push(q.removeLast());
            }
        }
        return res;
    }

}

性能