标签： 贪心算法

目标

给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。

返回 至少 能删除数组中的一半整数的整数集合的最小大小。

示例 1：

输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。

示例 2：

输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。

说明：

• 1 <= arr.length <= 10^5
• arr.length 为偶数
• 1 <= arr[i] <= 10^5

思路

从整数数组中选出一个元素集合，使该集合中元素在原数组中的出现次数超过原数组长度的一半，求集合大小的最小值。

统计每个元素的出现次数，将出现次数从大到小排序，然后开始选元素直到满足题目条件。

代码

/**
 * @date 2024-12-15 0:17
 */
public class MinSetSize1338 {

    public int minSetSize(int[] arr) {
        int n = arr.length;
        int[] cnt = new int[100001];
        for (int i : arr) {
            cnt[i]++;
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        for (int i : cnt) {
            if (i > 0) {
                q.offer(i);
            }
        }
        int res = 0;
        int l = 0;
        while (!q.isEmpty()) {
            l += q.poll();
            res++;
            if (l >= n / 2) {
                break;
            }
        }
        return res;
    }
}

性能

目标

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

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的 分数 是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小 分数 。

示例 1：

输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。

示例 3：

输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。

说明：

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

思路

这道题与 908.最小差值I 的区别是对于每个元素操作是 必选的，增加或减少的值 固定 为 k 而不是区间 [-k, k]。

每个元素都可以取 nums[i] + k 或 nums[i] - k，如果枚举所有可能的数组，然后再取最大最小值差的最小值显然是不可能的。不考虑重复元素的情况下，可能的数组有 2^n 种。

可以先排序，增大小的值，减少大的值，枚举二者的边界，比如前 i 个元素 [0, i - 1] 加 k，剩余元素减 k，这时上界为 Math.max(nums[i - 1] + k, nums[n - 1] - k) ，下界为 Math.min(nums[0] + k, nums[i] - k)，取上下界的最小值即可。

代码

/**
 * @date 2024-10-21 9:57
 */
public class SmallestRangeII910 {

    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = nums[n - 1] - nums[0];
        for (int i = 1; i < n; i++) {
            int max = Math.max(nums[i - 1] + k, nums[n - 1] - k);
            int min = Math.min(nums[0] + k, nums[i] - k);
            res = Math.min(res, max - min);
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。

你可以在 text 中任意位置插入 一个 字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。

请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。

子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

示例 1：

输入：text = "abdcdbc", pattern = "ac"
输出：4
解释：
如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = 'a' ，那么我们得到 "abadcdbc" 。那么 "ac" 作为子序列出现 4 次。
其他得到 4 个 "ac" 子序列的方案还有 "aabdcdbc" 和 "abdacdbc" 。
但是，"abdcadbc" ，"abdccdbc" 和 "abdcdbcc" 这些字符串虽然是可行的插入方案，但是只出现了 3 次 "ac" 子序列，所以不是最优解。
可以证明插入一个字符后，无法得到超过 4 个 "ac" 子序列。

示例 2：

输入：text = "aabb", pattern = "ab"
输出：6
解释：
可以得到 6 个 "ab" 子序列的部分方案为 "aaabb" ，"aaabb" 和 "aabbb" 。

说明：

• 1 <= text.length <= 10^5
• pattern.length == 2
• text 和 pattern 都只包含小写英文字母。

思路

已知字符串 pattern 包含两个小写英文字符，可以将其中的一个字符插入字符串 text，求插入后最多可以得到多少个个等于 pattern 的子序列。

刚开始想的是根据乘法原理来做，统计字符串中这两个字符出现的次数，cnt1 与 cnt2，插入出现次数较小的字符，可以使子序列个数增加最多。子序列个数为 Math.max(cnt1, cnt2) * (Math.min(cnt1, cnt2) + 1)。

但是这个想法忽略了这种情况，考虑字符串 mpmp，cnt1 = 2, cnt2 = 2，但是子序列个数并不是 4，而是 3，需要减去第二个 m 之前的 p 的个数。我们不妨以 pattern[0] 为终点，统计它前面的 pattern[1] 的个数，将其从结果中减去。

其实这里还有一个漏洞，应该考虑 pattern 这两个字符相同的情况。c(n,2) = n(n - 1)/2，注意实际计算的时候应该将 n 加 1，因为我们插入了一个字符，即 cnt1 * (cnt1 + 1) / 2。

还是存在一个问题，比如 text 中的字符与 pattern 都是由一个相同的字符组成，那么 cnt1 最大值为 10^5，在乘法计算时就会溢出，需要使用long类型。

官网题解的思路是先计算不插入字符时子序列的个数，遇到 pattern[1] 就累加 pattern[0]，同时记录二者的出现次数：

• 如果 pattern[1] 出现次数更多，可以在开头插入 pattern[0] 使得子序列个数增加 pattern[1] 个
• 如果 pattern[0] 出现次数更多，可以在结尾插入 pattern[1] 使得子序列个数增加 pattern[0] 个

最后直接将累加结果加上 Math.max(cnt1, cnt2) 即可。

代码

/**
 * @date 2024-09-24 8:54
 */
public class MaximumSubsequenceCount2207 {
    public long maximumSubsequenceCount(String text, String pattern) {
        long cnt1 = 0, cnt2 = 0;
        char c1 = pattern.charAt(0), c2 = pattern.charAt(1);
        char[] chars = text.toCharArray();
        long sub = 0;
        for (char c : chars) {
            if (c1 == c) {
                cnt1++;
                sub += cnt2;
            } else if (c2 == c) {
                cnt2++;
            }
        }
        if (c1 == c2) {
            return cnt1 * (cnt1 + 1) / 2;
        }
        return Math.max(cnt1, cnt2) * (Math.min(cnt1, cnt2) + 1) - sub;
    }

}

性能

目标

给你一个二维整数数组 point ，其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。

每个矩形的左下角在某个点 (x1, 0) 处，且右上角在某个点 (x2, y2) 处，其中 x1 <= x2 且 y2 >= 0 ，同时对于每个矩形都 必须 满足 x2 - x1 <= w 。

如果一个点在矩形内或者在边上，我们说这个点被矩形覆盖了。

请你在确保每个点都 至少 被一个矩形覆盖的前提下，最少 需要多少个矩形。

注意：一个点可以被多个矩形覆盖。

示例 1：

输入：points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出：2
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (1, 0) ，右上角在 (2, 8) 。
一个矩形的左下角在 (3, 0) ，右上角在 (4, 8) 。

示例 2：

输入：points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出：3
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (0, 0) ，右上角在 (2, 2) 。
一个矩形的左下角在 (3, 0) ，右上角在 (5, 5) 。
一个矩形的左下角在 (6, 0) ，右上角在 (6, 6) 。

示例 3：

输入：points = [[2,3],[1,2]], w = 0
输出：2
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (1, 0) ，右上角在 (1, 2) 。
一个矩形的左下角在 (2, 0) ，右上角在 (2, 3) 。

说明：

• 1 <= points.length <= 10^5
• points[i].length == 2
• 0 <= xi == points[i][0] <= 10^9
• 0 <= yi == points[i][1] <= 10^9
• 0 <= w <= 10^9
• 所有点坐标 (xi, yi) 互不相同。

思路

有一个二维数组表示平面中的点，给定一个整数w表示矩形x方向的最大宽度，矩形的左下角在x坐标轴上某个点，右上角在第一象限某点。问覆盖坐标平面上所有点最少需要多少个矩形，在矩形边上也算被覆盖了。

由于y轴方向没有限制，我们只考虑x轴方向，可以将坐标平面中的点按照x轴坐标大小排序，然后按w宽度分组计数即可。

最快的写法是将二维坐标转成了一维的x坐标，排序只需要寻址一次。

代码

/**
 * @date 2024-07-31 9:12
 */
public class MinRectanglesToCoverPoints3111 {

    public int minRectanglesToCoverPoints_v1(int[][] points, int w) {
        int n = points.length;
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = points[i][0];
        }
        Arrays.sort(x);
        int res = 0;
        int r = -1;
        for (int i = 0; i < n; i++) {
            if (x[i] > r) {
                res++;
                r = x[i] + w;
            }
        }
        return res;
    }

    public int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, (a, b) -> a[0] - b[0]);
        int n = points.length;
        int res = 0;
        int l = 0;
        for (int i = 1; i < n; i++) {
            if (points[i][0] - points[l][0] > w) {
                res++;
                l = i;
            }
        }
        // res 计数的是之前的矩形个数，+1表示将最后的矩形计入
        return res + 1;
    }
}

性能

目标

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

定义函数 distance(s1, s2) ，用于衡量两个长度为 n 的字符串 s1 和 s2 之间的距离，即：

• 字符 'a' 到 'z' 按 循环 顺序排列，对于区间 [0, n - 1] 中的 i ，计算所有「 s1[i] 和 s2[i] 之间 最小距离」的 和 。

例如，distance("ab", "cd") == 4 ，且 distance("a", "z") == 1 。

你可以对字符串 s 执行 任意次 操作。在每次操作中，可以将 s 中的一个字母 改变 为 任意 其他小写英文字母。

返回一个字符串，表示在执行一些操作后你可以得到的 字典序最小 的字符串 t ，且满足 distance(s, t) <= k 。

示例 1：

输入：s = "zbbz", k = 3
输出："aaaz"
解释：在这个例子中，可以执行以下操作：
将 s[0] 改为 'a' ，s 变为 "abbz" 。
将 s[1] 改为 'a' ，s 变为 "aabz" 。
将 s[2] 改为 'a' ，s 变为 "aaaz" 。
"zbbz" 和 "aaaz" 之间的距离等于 k = 3 。
可以证明 "aaaz" 是在任意次操作后能够得到的字典序最小的字符串。
因此，答案是 "aaaz" 。

示例 2：

输入：s = "xaxcd", k = 4
输出："aawcd"
解释：在这个例子中，可以执行以下操作：
将 s[0] 改为 'a' ，s 变为 "aaxcd" 。
将 s[2] 改为 'w' ，s 变为 "aawcd" 。
"xaxcd" 和 "aawcd" 之间的距离等于 k = 4 。
可以证明 "aawcd" 是在任意次操作后能够得到的字典序最小的字符串。
因此，答案是 "aawcd" 。

示例 3：

输入：s = "lol", k = 0
输出："lol"
解释：在这个例子中，k = 0，更改任何字符都会使得距离大于 0 。
因此，答案是 "lol" 。

说明：

• 1 <= s.length <= 100
• 0 <= k <= 2000
• s 只包含小写英文字母。

思路

定义两个由 a - z 组成的长度相等字符串之间的距离为相应位置上字母的最小距离，比如 a 与 z 的最小距离为1，a 与 o 之间的距离为12，而非14，a 与 n 的距离为13，即距离的最大值为13。因此两字符相减 diff 如果大于13，应取 26 - diff。

a b c d e f g h i j k l m

n o p q r s t u v w x y z

现在给定k表示字符串距离，需要我们找出与给定字符串距离为k的字典序最小的字符串。所谓字典序，先取第一个字符比较它在字母表中的排序，如果相等则比较下一个。

因此我们可以遍历给定的字符串的每一个字符，在距离范围内优先将其改为 a，如果距离还有多余，则继续改下一个字母，如果距离不够直接向下取剩余距离的字符。由于字母是首尾相接的，需要考虑是从哪边计算距离最短。第一行从前计算，第二行从后计算，或者两者都计算，比较大小决定如何处理。

代码

/**
 * @date 2024-07-27 22:22
 */
public class GetSmallestString3106 {

    public String getSmallestString(String s, int k) {
        char[] chars = s.toCharArray();
        int n = s.length();
        int i = 0;
        while (k > 0 && i < n) {
            char c = chars[i];
            int dist = Math.min('z' - c + 1, c - 'a');
            if (k < dist) {
                chars[i] = (char) (c - k);
                break;
            }
            chars[i] = 'a';
            k -= dist;
            i++;
        }

        return new String(chars);
    }

}

性能