标签： 贪心算法

目标

给你一个由小写英文字母组成的回文字符串 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;
    }

}

性能

目标

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

说明:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

思路

数组 nums 的元素表示可以向后跳跃的最大长度，求从 0 跳到 n - 1 所需的最小跳跃次数。

定义 dp[i] 表示到达下标 i 所需的最小跳跃次数，状态转移方程为 dp[i + k] = min(dp[i] + 1)，其中 k ∈ [1, nums[i]]。

代码

/**
 * @date 2024-03-07 17:14
 */
public class CanJumpII45 {

    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 0x3f3f3f);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && j <= i + nums[i]; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }

}

性能

目标

有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：

• 每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
• Alice 将会取走硬币数量最多的那一堆。
• 你将会取走硬币数量第二多的那一堆。
• Bob 将会取走最后一堆。
• 重复这个过程，直到没有更多硬币。

给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。

返回你可以获得的最大硬币数目。

示例 1：

输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。

示例 2：

输入：piles = [2,4,5]
输出：4

示例 3：

输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18

说明：

• 3 <= piles.length <= 10^5
• piles.length % 3 == 0
• 1 <= piles[i] <= 10^4

思路

有 3n 堆硬币，每次操作可以任选其中3堆，Alice 取走数量最多的那堆硬币，我们取走硬币数量第二多的，Bob 取走剩下的。求我们能获得的最大硬币数目。

为了使我们获取的硬币数量最多，Bob 每次只能取数量最少的那堆，将数量多的留下。根据这种贪心策略，我们可以将每堆硬币按个数从小到大排序，从倒数第二个开始每隔两个向前取，同时 Bob 从第一个往后挨个取，直到这两个指针相遇。

代码

/**
 * @date 2025-01-22 8:50
 */
public class MaxCoins1561 {

    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int res = 0;
        int n = piles.length;
        int k = 0;
        for (int i = n - 2; i > k; i -= 2, k++) {
            res += piles[i];
        }
        return res;
    }
}

性能