标签： 贪心算法

目标

在一个由 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;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。

说明：

• 1 <= players.length, trainers.length <= 10^5
• 1 <= players[i], trainers[j] <= 10^9

思路

有两个数组 arr1 与 arr2，如果 arr1[i] <= arr2[j]，则称 arr1[i] 与 arr2[j] 相匹配。arr1 中的元素最多只能匹配一个 arr2 中的元素，同时，arr2 中的元素最多只能匹配一个 arr1 中的元素，求最大匹配数。

贪心策略，arr1 中的最小元素优先匹配 arr2 中的最小元素。

代码

/**
 * @date 2025-07-13 20:20
 */
public class MatchPlayersAndTrainers2410 {

    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int m = players.length;
        int n = trainers.length;
        int res = 0;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (players[i] <= trainers[j]) {
                res++;
                i++;
            }
            j++;
        }
        return res;
    }

}

性能

目标

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。

示例 1：

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。

示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4

说明：​​​​​​

• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 10^5

思路

二维数组 events 表示会议的开始与结束时间，每天最多参加一次会议求最多可以参加几个会议。

按开始时间分组，记录结束时间列表，优先参加结束时间最小的会议。遍历每一天，去掉过期的会议结束时间，将当前的结束时间列表加入优先队列，取最小的结束时间，如果大于等于开始时间则计入答案。

代码

/**
 * @date 2025-07-07 9:07
 */
public class MaxEvents1353 {

    public int maxEvents(int[][] events) {
        int max = 0;
        for (int[] event : events) {
            max = Math.max(max, event[1]);
        }
        List<Integer>[] groups = new List[max + 1];
        Arrays.setAll(groups, x -> new ArrayList<>());
        for (int[] event : events) {
            groups[event[0]].add(event[1]);
        }
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int res = 0;
        for (int i = 1; i <= max; i++) {
            while (!q.isEmpty() && q.peek() < i) {
                q.poll();
            }
            q.addAll(groups[i]);
            if (!q.isEmpty()) {
                res++;
                q.poll();
            }
        }
        return 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;
    }

}

性能