标签： 贪心算法

目标

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

• 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
• 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

示例 1：

输入：s = "0011"
输出：2
解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2：

输入：s = "010101"
输出：9
解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
执行第二种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 

说明：

• 1 <= s.length == n <= 10^5
• s[i] 为 '0' 或 '1'

思路

有一个二进制字符串，每次操作可以反转前缀 0 ~ i，成本是 i + 1，也可以反转后缀 i ~ n - 1，成本是 n - i。求使字符串所有字符相等的最小成本。

如何操作才能使字符相等？相等字符是 0 还是 1？操作哪边才能使成本最小？

关键点是想清楚与是 0 还是 1 没有关系，只要相邻的元素值不同，就必须要反转，无非是考虑反转前缀还是后缀，每次操作只影响相邻的元素关系。

代码

/**
 * @date 2025-03-27 1:33
 */
public class MinimumCost2712 {

    public long minimumCost(String s) {
        int n = s.length();
        long res = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                // i 表示反转 0 ~ i - 1，n - i 表示反转 i ~ n - 1
                res += Math.min(i, n - i);
            }
        }
        return res;
    }
}

性能

目标

给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

示例 1：

输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。 

说明：

• 1 <= n, k <= 50

思路

定义 k-avoiding 数组是由不同的正整数组成，并且任意两个元素的和不等于 k 的数组。求长度为 n 的 k-avoiding 数组的最小和。

构造一个长度为 n 的正整数数组，要使和最小，需要从 num = 1 开始选，跳过 k - num。

网友指出可以使用等差数列求和来计算，第一部分是 1 ~ m, m = min(k / 2, n) 和为 m * (m + 1) / 2，第二部分是 k ~ k + n - m - 1，和为 (n - m) * (2 * k + n - m - 1) / 2。

代码

/**
 * @date 2025-03-26 0:13
 */
public class MinimumSum2829 {

    public int minimumSum(int n, int k) {
        int res = 0;
        int length = 0;
        int num = 1;
        Set<Integer> avoiding = new HashSet<>();
        while (length < n) {
            if (avoiding.contains(num)) {
                num++;
                continue;
            }
            if (num < k) {
                avoiding.add(k - num);
            }
            length++;
            res += num;
            num++;
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

说明：

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

思路

有一个整数数组 nums，最多可以对它执行 k 次操作，每次操作可以任选一个数将其左移 1 位。求操作后数组所有元素的最大或值。

操作集中到同一个数上可以将最高有效位移到最高，少一次操作最高位就低一位。问题的关键在于，如果所有数字都有相同的最高有效位，移哪个是不确定的。

这时就需要枚举操作数了，每选择一个操作数就需要重新计算其余元素的或值。由于或运算没有逆运算，我们无法撤销已经或进去的值。

直接的想法是计算或前缀、后缀，枚举所有元素，将其左移 k 次，然后与前后缀进行或运算，取最大值。

网友提供了另一种基于位运算的解法，计算全体元素的或值，同时计算所有 bit 位上存在重复 1 的位置，通过异或运算将当前元素对或值的贡献抵消，然后补上重复位置上的 1。

代码

/**
 * @date 2025-03-21 0:08
 */
public class MaximumOr2680 {

    public long maximumOr_v1(int[] nums, int k) {
        int n = nums.length;
        int or = 0;
        int multiBits = 0;
        for (int i = 0; i < n; i++) {
            multiBits = multiBits | or & nums[i];
            or = or | nums[i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, or ^ nums[i] | multiBits | ((long) nums[i] << k));
        }
        return res;
    }

    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] | nums[i - 1];
            suffix[n - i] = suffix[n - i + 1] | nums[n - i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, prefix[i] | suffix[i + 1] | ((long) nums[i] << k));
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 ：

• 字符串是一个空字符串，或者
• 字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
• 字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。

你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 s 变成 平衡字符串 所需要的 最小 交换次数。

示例 1：

输入：s = "][]["
输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。

示例 2：

输入：s = "]]][[["
输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][][" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。

示例 3：

输入：s = "[]"
输出：0
解释：这个字符串已经是平衡字符串。

说明：

• n == s.length
• 2 <= n <= 10^6
• n 为偶数
• s[i] 为'[' 或 ']'
• 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

思路

有一个长度为偶数 n 的字符串，有 n / 2 个 [ 和 ]。定义括号能够匹配的字符串是平衡字符串。每一次操作可以交换任意两个下标对应的括号，求将字符串变平衡的最少操作次数。

[[]] 和 [][] 都是平衡字符串，如何确定该与哪个括号交换才能使操作次数最小？对于 ]][[ 和 ][][，第一个与最后一个交换之后变为平衡字符串 [][] 和 [[]]。而如果选择与倒数第二个 [ 交换，会变成 []][，需要再交换一次才能变为平衡字符串。

平衡字符串有这样的性质：其前缀中 [ 的个数总是大于等于 ] 的个数。如果发现 ] 的个数超过 [，那么必须要进行交换。最好将它交换到最后，因为这样可以减少它在前面前缀中对 ] 的贡献，将交换操作尽可能地延后，减小必须进行交换的次数。

也可以先将平衡的括号消掉，剩下的必然是 ]]]......[[[ 的形式。交换一次最多可以抵消 4 个，最少抵消 2 个，即 (stack.size() + 2) / 4。

代码

/**
 * @date 2025-03-17 16:32
 */
public class MinSwaps1963 {

    public int minSwaps_v1(String s) {
        int n = s.length();
        int left = 0, right = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '[') {
                left++;
            } else if (c == ']' && left > 0) {
                left--;
            } else {
                right++;
            }
        }
        return (left + right + 2) / 4;
    }

    public int minSwaps(String s) {
        int n = s.length();
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return (stack.size() + 2) / 4;
    }

}

性能

目标

给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。

请你返回结果字符串。如果无法做到，则返回一个 空串 。

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc” 字典序比 "abcd" 小，因为不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。

示例 1：

输入：palindrome = "abccba"
输出："aaccba"
解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
在所有方法中，"aaccba" 的字典序最小。

示例 2：

输入：palindrome = "a"
输出：""
解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。

说明：

• 1 <= palindrome.length <= 1000
• palindrome 只包含小写英文字母。

思路

有一个回文字符串，可以修改其中一个字符使其不是回文，求修改后字典序最小的字符串。如果无法破会回文串，返回空串。

根据题意，字符串长度为 1 直接返回空串。

要使字典序最小，只需使字符串最左边的字符为 a，但是需考虑能否破坏回文串。于是就有了贪心解法，从左到右将对应位置上的字符修改为 a，判断是否是回文，不是回文直接返回。如果均为 a，将最后一个字符替换为 b。

注意不要改中间的字符，它不会破坏回文串。

代码

/**
 * @date 2025-03-05 0:06
 */
public class BreakPalindrome1328 {

    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        if (n == 1) {
            return "";
        }
        int l = 0, r = n - 1;
        char[] chars = palindrome.toCharArray();
        while (l < r) {
            if (chars[r] != 'a') {
                chars[l] = 'a';
                return new String(chars);
            }
            l++;
            r--;
        }
        chars[n - 1] = 'b';
        return new String(chars);
    }

}

性能

目标

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

示例 1：

输入：[[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

示例 2：

输入：arrays = [[1],[1]]
输出：0

说明：

• m == arrays.length
• 2 <= m <= 10^5
• 1 <= arrays[i].length <= 500
• -10^4 <= arrays[i][j] <= 10^4
• arrays[i] 以 升序 排序。
• 所有数组中最多有 10^5 个整数。

思路

有一个二维数组，其中的每个数组都按升序排列。任选其中两个数组，从每个数组中选两个元素，求这两个元素距离的最大值，距离指差的绝对值。

显然应该选取最大值与最小值的差，但题目限制是从两个数组中取。我们可以求得最大与次最大、最小与次最小，同时记录所属数组。

如果有多个最值相同，从哪个数组中取有影响吗？由于我们从每个组只取首尾两个元素，最值与次最值一定来自不同的组，所以最值的比较可以使用 >= 和 <=。如果最值来自相同的组，那么只需比较最大值与次最小值，次最大值与最小值。

网友题解使用变量记录前面的最大与最小值，那么最大距离为 Math.max(res, Math.max(curMax - preMin, preMax - curMin))。

代码

/**
 * @date 2025-02-19 8:57
 */
public class MaxDistance624 {

    public int maxDistance_v1(List<List<Integer>> arrays) {
        int res = 0;
        int preMax = Integer.MIN_VALUE / 2;
        int preMin = Integer.MAX_VALUE / 2;
        for (List<Integer> array : arrays) {
            int n = array.size();
            Integer curMax = array.get(n - 1);
            Integer curMin = array.get(0);
            res = Math.max(res, Math.max(curMax - preMin, preMax - curMin));
            preMax = Math.max(preMax, curMax);
            preMin = Math.min(preMin, curMin);
        }
        return res;
    }

    public int maxDistance(List<List<Integer>> arrays) {
        int[] max = new int[]{Integer.MIN_VALUE, -1};
        int secondMax = Integer.MIN_VALUE;
        int[] min = new int[]{Integer.MAX_VALUE, -1};
        int secondMin = Integer.MAX_VALUE;
        for (int i = 0; i < arrays.size(); i++) {
            List<Integer> array = arrays.get(i);
            int n = array.size();
            if (min[0] >= array.get(0)) {
                secondMin = min[0];
                min[0] = array.get(0);
                min[1] = i;
            } else if (secondMin > array.get(0)) {
                secondMin = array.get(0);
            }
            if (max[0] <= array.get(n - 1)) {
                secondMax = max[0];
                max[0] = array.get(n - 1);
                max[1] = i;
            } else if (secondMax < array.get(n - 1)) {
                secondMax = array.get(n - 1);
            }
        }
        if (max[1] != min[1]) {
            return max[0] - min[0];
        } else {
            return Math.max(max[0] - secondMin, secondMax - min[0]);
        }
    }

}

性能

目标

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

示例 1：

输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

示例 2：

输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

说明：

• n == position.length
• 2 <= n <= 10^5
• 1 <= position[i] <= 10^9
• 所有 position 中的整数 互不相同 。
• 2 <= m <= position.length

提示：

• If you can place balls such that the answer is x then you can do it for y where y < x.
• Similarly if you cannot place balls such that the answer is x then you can do it for y where y > x.
• Binary search on the answer and greedily see if it is possible.

思路

将 m 个球放到 n 个空篮子中，任意两个球之间的磁力为 |position[a] - position[b]|，返回最大的磁力最小值。

看到最大化最小值就想到二分，n 个盒子放 m 个球，每个盒子至多放 1 个。假定最小磁力为 y，即相邻球的磁力最少为 y。将 position 排序，累加相邻元素的差即磁力，如果大于 y 则放置一个球，看能否放得下。

代码

/**
 * @date 2025-02-14 9:35
 */
public class MaxDistance1552 {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int n = position.length;
        int left = 0, right = position[n - 1] / (m - 1);
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(mid, position, m - 1)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = left + (right - left) / 2;
        }
        return right;
    }

    public boolean check(int mid, int[] position, int m) {
        int start = position[0];
        for (int i = 1; i < position.length; i++) {
            if (position[i] >= start + mid) {
                if (--m == 0) {
                    return true;
                }
                start = position[i];
            }
        }
        return false;
    }

}

性能

目标

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
• 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

示例 2：

输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

示例 3：

输入：nums = [7,17], maxOperations = 2
输出：7

说明：

1 <= nums.length <= 10^5
1 <= maxOperations, nums[i] <= 10^9

思路

有 n 个袋子，nums[i] 表示第 i + 1 个袋子中球的数目。每次操作可以任选一个袋子，将其中的球分成非空的两部分并装入两个 新 袋子。求执行 maxOperations 次操作后袋中球的数量最大值的最小值是多少。

考虑暴力解法，要最小化最大值，我们应该首先操作球最多的袋子，划分方案有 max / 2 种。这里需要枚举所有划分方案，然后重新计算球最多的袋子重复这一处理流程。最坏的情况下所有元素值都相等，时间复杂度为 O((max/2)^maxOperations)。这种解法显然行不通。

既然正向思维行不通，那就考虑逆向思维。假定一个最大值 mid，看能否在 maxOperations 次操作内将所有袋子种的球都降到 mid 以下。

将数字 num 拆分成不大于 mid 的数字最少需要操作几次？这里可以使用贪心思想，将 num 拆分为 num - mid 和 mid，然后接着拆分 num - mid 直到它小于等于 mid。

关于次数的计算，如果 num % mid == 0，我们只需划分 num / mid - 1 次，因为剩余的部分为 mid。如果余数不为 0，则需要划分 num / mid 次。以上两种情况可以统一写成 (num - 1) / mid。

代码

/**
 * @date 2025-02-12 0:03
 */
public class MinimumSize1760 {

    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1, right = 1000000000;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums, mid, maxOperations)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = left + (right - left) / 2;
        }
        return left;
    }

    public boolean check(int[] nums, int mid, int maxOperations) {
        for (int num : nums) {
            maxOperations -= (num - 1) / mid;
            if (maxOperations < 0) {
                return false;
            }
        }
        return true;
    }

}

性能