LeetCode Go · 贪心（10）

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

2864. 最大二进制奇数

简单1 种解法

标签：贪心、数学、字符串

题目、示例与约束

给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。

你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。

以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。

注意返回的结果字符串可以含前导零。

示例 1：

输入：s = "010"
输出："001"
解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。

示例 2：

输入：s = "0101"
输出："1001"
解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。

提示：

1 <= s.length <= 100
s 仅由 '0' 和 '1' 组成
s 中至少包含一个 '1'

方法一：贪心 · Go 实现

思考

奇数二进制数末位必须为 $1$ ，其余 $1$ 放在高位才能最大。统计 $1$ 的个数后，将 $c n t - 1$ 个 $1$ 置于开头，中间填 $0$ ，末尾再放一个 $1$ 。

我们先统计字符串 $s$ 中 $1$ 的个数，记为 $c n t$ 。那么我们将 $c n t - 1$ 个 $1$ 放在最高位，剩下的 $| s | - c n t$ 个 $0$ 放在后面，最后再加上一个 $1$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func maximumOddBinaryNumber(s string) string {
	cnt := strings.Count(s, "1")
	return strings.Repeat("1", cnt-1) + strings.Repeat("0", len(s)-cnt) + "1"
}

力扣原题 · Doocs 题解来源

2868. 单词游戏 🔒

困难1 种解法

标签：贪心、数组、数学、双指针、字符串、博弈

题目、示例与约束

Alice 和 Bob 分别拥有一个 按字典序排序 的字符串数组，分别命名为 a 和 b。

他们正在玩一个单词游戏，遵循以下规则：

每一轮，当前玩家应该从他的列表中选择一个单词，并且选择的单词比上一个单词 紧邻大；然后轮到另一名玩家。
如果一名玩家在自己的回合中无法选择单词，则输掉比赛。

Alice 通过选择在 字典序最小 的单词开始游戏。

给定 a 和 b，已知两名玩家都按最佳策略玩游戏，如果 Alice 可以获胜，则返回 true ，否则返回 false。

如果满足以下条件，则称一个单词 w 比另一个单词 z 紧邻大：

w 在 字典序上大于 z。
如果 w₁ 是 w 的第一个字母，z₁ 是 z 的第一个字母，那么 w₁ 应该等于 z₁ 或者是字母表中 z₁ 后面相邻 的字母。
例如，单词 "care" 比 "book" 和 "car" 紧邻大，但不比 "ant" 或 "cook" 紧邻大。

如果在 s 和 t 不同的第一个位置处，字符串 s 的字母比字符串 t 的字母在字母表中的顺序更靠后，则称为字符串 s 在 字典序上大于 字符串 t。如果前 min(s.length, t.length) 个字符没有区别，那么较长的字符串是在字典序上较大的那一个。

示例 1：

输入: a = ["avokado","dabar"], b = ["brazil"]

输出: false

解释: Alice 必须从单词 "avokado" 来开始游戏，因为这是她最小的单词，然后 Bob 使用他唯一的单词 "brazil"，他可以使用它因为它的第一个字母 'b' 在 Alice 的单词的第一个字母 'a' 之后。

Alice 无法出牌，因为剩下的唯一单词的第一个字母既不等于 'b' 也不是 'b' 之后的字母 'c'。

所以，Alice 输了，游戏结束。

示例 2：

输入: a = ["ananas","atlas","banana"], b = ["albatros","cikla","nogomet"]

输出: true

解释: Alice 必须从单词 "ananas" 来开始游戏。

Bob 无法出牌，因为他唯一拥有的以字母 'a' 或 'b' 开头的单词是 "albatros"，而它比 Alice 的单词小。

所以，Alice 获胜，游戏结束。

示例 3：

输入: a = ["hrvatska","zastava"], b = ["bijeli","galeb"]

输出: true

解释: Alice 必须从单词 "hrvatska" 来开始游戏。

Bob 无法出牌，因为他的两个单词的第一个字母都比 Alice 的单词的第一个字母 'h' 小。

所以，Alice 获胜，游戏结束。

约束条件：

1 <= a.length, b.length <= 10⁵
a[i] 和 b[i] 仅包含小写英文字母。
a 和 b 按 字典序排序。
a 和 b 中所有的单词都是 不同的。
a 和 b 中所有单词的长度之和不超过 10⁶。

方法一：模拟 · Go 实现

思考

双方词表已排序，轮流必须接一个首字母相同且字典序更大、或首字母恰好比当前词大 $1$ 的词。双方都会选当前能用的最靠前合法词，故用双指针按序扫描即可模拟整局，无需搜索。

我们记当前轮到 $A l i c e$ 的回合为 $k = 0$ ，轮到 $B o b$ 的回合为 $k = 1$ 。我们用 $i$ 记录 $A l i c e$ 的下标，用 $j$ 记录 $B o b$ 的下标，用 $w$ 记录当前轮到的玩家的单词。初始时 $i = 1$ , $j = 0$ , $w = a [0]$ 。

我们不断地进行如下操作：

如果 $k = 1$ ，则我们判断 $j$ 是否等于 $b$ 的长度，如果等于则说明 $A l i c e$ 获胜，返回 $t r u e$ ；否则我们判断 $b [j]$ 的第一个字母是否等于 $w$ 的第一个字母，如果等于则我们判断 $b [j]$ 是否大于 $w$ ，或者 $b [j]$ 的第一个字母是否比 $w$ 的第一个字母大 $1$ ，如果是则说明 $B o b$ 可以出第 $j$ 个单词，我们令 $w = b [j]$ ，并将 $k$ 取反；否则说明 $B o b$ 无法出第 $j$ 个单词，我们令 $j$ 加一。

如果 $k = 0$ ，则我们判断 $i$ 是否等于 $a$ 的长度，如果等于则说明 $B o b$ 获胜，返回 $f a l s e$ ；否则我们判断 $a [i]$ 的第一个字母是否等于 $w$ 的第一个字母，如果等于则我们判断 $a [i]$ 是否大于 $w$ ，或者 $a [i]$ 的第一个字母是否比 $w$ 的第一个字母大 $1$ ，如果是则说明 $A l i c e$ 可以出第 $i$ 个单词，我们令 $w = a [i]$ ，并将 $k$ 取反；否则说明 $A l i c e$ 无法出第 $i$ 个单词，我们令 $i$ 加一。

时间复杂度 $O (m + n)$ ，其中 $m$ 和 $n$ 分别是数组 $a$ 和 $b$ 的长度。我们只需要遍历数组一次。空间复杂度 $O (1)$ 。

func canAliceWin(a []string, b []string) bool {
	i, j, k := 1, 0, 1
	w := a[0]
	for {
		if k&1 == 1 {
			if j == len(b) {
				return true
			}
			if (b[j][0] == w[0] && w < b[j]) || b[j][0]-w[0] == 1 {
				w = b[j]
				k ^= 1
			}
			j++
		} else {
			if i == len(a) {
				return false
			}
			if (a[i][0] == w[0] && w < a[i]) || a[i][0]-w[0] == 1 {
				w = a[i]
				k ^= 1
			}
			i++
		}
	}
}

力扣原题 · Doocs 题解来源

2870. 使数组为空的最少操作次数

中等1 种解法

标签：贪心、数组、哈希表、计数

题目、示例与约束

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

你可以对数组执行以下两种操作 任意次 ：

从数组中选择两个值相等的元素，并将它们从数组中删除。
从数组中选择三个值相等的元素，并将它们从数组中删除。

请你返回使数组为空的最少操作次数，如果无法达成，请返回 -1 。

示例 1：

输入：nums = [2,3,3,2,2,4,2,3,4]
输出：4
解释：我们可以执行以下操作使数组为空：
- 对下标为 0 和 3 的元素执行第一种操作，得到 nums = [3,3,2,4,2,3,4] 。
- 对下标为 2 和 4 的元素执行第一种操作，得到 nums = [3,3,4,3,4] 。
- 对下标为 0 ，1 和 3 的元素执行第二种操作，得到 nums = [4,4] 。
- 对下标为 0 和 1 的元素执行第一种操作，得到 nums = [] 。
至少需要 4 步操作使数组为空。

示例 2：

输入：nums = [2,1,2,2,3,3]
输出：-1
解释：无法使数组为空。

提示：

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

方法一：哈希表 + 贪心 · Go 实现

思考

每次删除 $2$ 或 $3$ 个相同元素。对每种值的次数 $c$ ，若 $c = 1$ 则不可能删完；否则最少次数为 $⌈ c / 3 ⌉$ ，即 $(c + 2) / / 3$ 。

我们用一个哈希表 $c o u n t$ 统计数组中每个元素出现的次数，然后遍历哈希表，对于每个元素 $x$ ，如果 $x$ 出现的次数为 $c$ ，那么我们可以进行 $⌊ \frac{c + 2}{3} ⌋$ 次操作，将 $x$ 删除，最后我们返回所有元素的操作次数之和即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组的长度。

func minOperations(nums []int) (ans int) {
	count := map[int]int{}
	for _, num := range nums {
		count[num]++
	}
	for _, c := range count {
		if c < 2 {
			return -1
		}
		ans += (c + 2) / 3
	}
	return
}

力扣原题 · Doocs 题解来源

2871. 将数组分割成最多数目的子数组

中等1 种解法

标签：贪心、位运算、数组

题目、示例与约束

给你一个只包含非负整数的数组 nums 。

我们定义满足 l <= r 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。

请你将数组分割成一个或者更多子数组，满足：

每个元素都只属于一个子数组。
子数组分数之和尽可能小。

请你在满足以上要求的条件下，返回最多可以得到多少个子数组。

一个 子数组 是一个数组中一段连续的元素。

示例 1：

输入：nums = [1,0,2,0,1,2]
输出：3
解释：我们可以将数组分割成以下子数组：
- [1,0] 。子数组分数为 1 AND 0 = 0 。
- [2,0] 。子数组分数为 2 AND 0 = 0 。
- [1,2] 。子数组分数为 1 AND 2 = 0 。
分数之和为 0 + 0 + 0 = 0 ，是我们可以得到的最小分数之和。
在分数之和为 0 的前提下，最多可以将数组分割成 3 个子数组。所以返回 3 。

示例 2：

输入：nums = [5,7,1,3]
输出：1
解释：我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。
在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

方法一：贪心 + 位运算 · Go 实现

思考

子数组分数为其中所有数的按位与，拆分后各段分数之和等于整段的与，因而总和最小当且仅当能拆出尽量多的分数为 $0$ 的段。从左到右累积与运算，一旦变为 $0$ 就切一刀；若始终得不到 $0$ ，整段只能作为一段。

我们初始化一个变量 $s c o r e$ ，用来记录当前子数组的分数，初始时 $s c o r e = - 1$ 。然后我们遍历数组，对于每个元素 $n u m$ ，我们将 $s c o r e$ 与 $n u m$ 进行按位与运算，然后将结果赋值给 $s c o r e$ 。如果 $s c o r e = 0$ ，说明当前子数组的分数为 $0$ ，我们就可以将当前子数组分割出来，然后将 $s c o r e$ 重置为 $- 1$ 。最后我们返回分割出的子数组的个数。

时间复杂度 $O (n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O (1)$ 。

func maxSubarrays(nums []int) int {
	ans, score := 1, -1
	for _, num := range nums {
		score &= num
		if score == 0 {
			score--
			ans++
		}
	}
	if ans == 1 {
		return 1
	}
	return ans - 1
}

力扣原题 · Doocs 题解来源

2895. 最小处理时间

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

你有 n 颗处理器，每颗处理器都有 4 个核心。现有 n * 4 个待执行任务，每个核心只执行一次任务。

给你一个下标从 0 开始的整数数组 processorTime ，表示每颗处理器最早空闲时间。另给你一个下标从 0 开始的整数数组 tasks ，表示执行每个任务所需的时间。返回所有任务都执行完毕需要的 最小时间 。

注意：每个核心独立执行任务。

示例 1：

输入：processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
输出：16
解释：
最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器（最早空闲时间 time = 8），下标为 0, 1, 2, 3 的任务分配给第二颗处理器（最早空闲时间 time = 10）。 
第一颗处理器执行完所有任务需要花费的时间 = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16 。
第二颗处理器执行完所有任务需要花费的时间 = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13 。
因此，可以证明执行完所有任务需要花费的最小时间是 16 。

示例 2：

输入：processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]
输出：23
解释：
最优的方案是将下标为 1, 4, 5, 6 的任务分配给第一颗处理器（最早空闲时间 time = 10），下标为 0, 2, 3, 7 的任务分配给第二颗处理器（最早空闲时间 time = 20）。 
第一颗处理器执行完所有任务需要花费的时间 = max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18 。 
第二颗处理器执行完所有任务需要花费的时间 = max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23 。 
因此，可以证明执行完所有任务需要花费的最小时间是 23 。

提示：

1 <= n == processorTime.length <= 25000
1 <= tasks.length <= 10⁵
0 <= processorTime[i] <= 10⁹
1 <= tasks[i] <= 10⁹
tasks.length == 4 * n

方法一：贪心 + 排序 · Go 实现

思考

每台处理器有四个核心，完成时间取决于空闲时刻与所分配任务中的最长者。将处理器空闲时间升序、任务耗时降序，最早空闲的处理器领取当前最长的四个任务，再取所有完成时间的最大值。

要使得处理完所有任务的时间最小，那么越早处于空闲状态的处理器应该处理耗时最长的 $4$ 个任务。

因此，我们对处理器的空闲时间和任务的耗时分别进行排序，然后依次将耗时最长的 $4$ 个任务分配给空闲时间最早的处理器，计算最大的结束时间即可。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 为任务的数量。

func minProcessingTime(processorTime []int, tasks []int) (ans int) {
	sort.Ints(processorTime)
	sort.Ints(tasks)
	i := len(tasks) - 1
	for _, t := range processorTime {
		ans = max(ans, t+tasks[i])
		i -= 4
	}
	return
}

力扣原题 · Doocs 题解来源

2897. 对数组执行操作使平方和最大

困难1 种解法

标签：贪心、位运算、数组、哈希表

题目、示例与约束

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

你可以对数组执行以下操作 任意次 ：

选择两个互不相同的下标 i 和 j ，同时将 nums[i] 更新为 (nums[i] AND nums[j]) 且将 nums[j] 更新为 (nums[i] OR nums[j]) ，OR 表示按位或运算，AND 表示按位与运算。

你需要从最终的数组里选择 k 个元素，并计算它们的平方之和。

请你返回你可以得到的最大平方和。

由于答案可能会很大，将答案对 10⁹ + 7 取余后返回。

示例 1：

输入：nums = [2,6,5,8], k = 2
输出：261
解释：我们可以对数组执行以下操作：
- 选择 i = 0 和 j = 3 ，同时将 nums[0] 变为 (2 AND 8) = 0 且 nums[3] 变为 (2 OR 8) = 10 ，结果数组为 nums = [0,6,5,10] 。
- 选择 i = 2 和 j = 3 ，同时将 nums[2] 变为 (5 AND 10) = 0 且 nums[3] 变为 (5 OR 10) = 15 ，结果数组为 nums = [0,6,0,15] 。
从最终数组里选择元素 15 和 6 ，平方和为 15² + 6² = 261 。
261 是可以得到的最大结果。

示例 2：

输入：nums = [4,5,4,7], k = 3
输出：90
解释：不需要执行任何操作。
选择元素 7 ，5 和 4 ，平方和为 7² + 5² + 4² = 90 。
90 是可以得到的最大结果。

提示：

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

方法一：位运算 + 贪心 · Go 实现

思考

一次操作可把某个 $1$ 从一数移到另一数的同一比特上，平方和在 $1$ 尽量集中时更大。按位统计 $1$ 的个数后，贪心构造 $k$ 个能凑出的最大数（每位能取则取），再累加它们的平方。

根据题目描述，对于一个操作，我们可以将 $n u m s [i]$ 变为 $n u m s [i] AND n u m s [j]$ ，将 $n u m s [j]$ 变为 $n u m s [i] OR n u m s [j]$ 。我们不妨按位考虑，两个 $1$ 或两个 $0$ 进行这样的操作，结果都不会改变，如果是 $1$ 和 $0$ 进行这样的操作，结果会变成 $0$ 和 $1$ ，也即是说，我们可以将 $1$ 转移到 $0$ 上，而 $0$ 不会转移到 $1$ 上。

因此，我们可以用一个数组 $c n t$ 统计每个位置上 $1$ 的个数，然后从中选择 $k$ 个数。由于要使得平方和最大，每次选择的数要尽可能大。这是因为，假设两个数的平方和为 $a^{2} + b^{2}$ （其中 $a > b$ ），将两个数平方和变成 $(a + c)^{2} + (b - c)^{2} = a^{2} + b^{2} + 2 c (a - b) + 2 c^{2} > a^{2} + b^{2}$ 。因此，为了最大化平方和，我们应该让一个数字尽可能大。

时间复杂度 $O (n \times \log M)$ ，空间复杂度 $O (\log M)$ ，其中 $M$ 是数组中的最大值。

func maxSum(nums []int, k int) (ans int) {
	cnt := [31]int{}
	for _, x := range nums {
		for i := 0; i < 31; i++ {
			if x>>i&1 == 1 {
				cnt[i]++
			}
		}
	}
	const mod int = 1e9 + 7
	for ; k > 0; k-- {
		x := 0
		for i := 0; i < 31; i++ {
			if cnt[i] > 0 {
				x |= 1 << i
				cnt[i]--
			}
		}
		ans = (ans + x*x) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

2910. 合法分组的最少组数

中等1 种解法

标签：贪心、数组、哈希表

题目、示例与约束

给你一组带编号的 balls 并要求将它们分类到盒子里，以便均衡地分配。你必须遵守两条规则：

同一个盒子里的球必须具有相同的编号。但是，如果你有多个相同编号的球，你可以把它们放在不同的盒子里。
最大的盒子只能比最小的盒子多一个球。

返回遵循上述规则排列这些球所需要的盒子的最小数目。

示例 1：

输入：balls = [3,2,3,2,3]
输出：2
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
我们可以如下排列 balls 到盒子里：
- [3,3,3]
- [2,2]
两个盒子之间的大小差没有超过 1。

示例 2：

输入：balls = [10,10,10,3,1,1]
输出：4
解释：我们可以如下排列 balls 到盒子里：
- [10]
- [10,10]
- [3]
- [1,1]
无法得到一个遵循上述规则且小于 4 盒的答案。例如，把所有三个编号为 10 的球都放在一个盒子里，就会打破盒子之间最大尺寸差异的规则。

提示：

1 <= balls.length <= 10⁵
1 <= balls[i] <= 10⁹

方法一：哈希表 + 枚举 · Go 实现

思考

同值必须分到若干组，且任意两组大小相差不超过 $1$ ，故全局组大小只能是某 $k$ 或 $k + 1$ 。组数最少时 $k$ 应尽可能大，其上界不超过最小频次。

从 $m i n (c n t . v a l u e s ())$ 递减枚举 $k$ 。对频次 $v$ ，若 $⌊ v / k ⌋ < v mod k$ ，则无法拆成若干个 $k$ 或 $k + 1$ ；否则最少组数为 $⌈ v / (k + 1) ⌉$ 。第一个完全可行的 $k$ 即为最优。

我们用一个哈希表 $c n t$ 统计数组 $n u m s$ 中每个数字出现的次数，我们记数字次数的最小值为 $k$ ，那么我们可以在 $[k, . .1]$ 的范围内枚举分组的大小。由于每个组的大小差值不超过 $1$ ，那么分组大小为 $k$ 或 $k + 1$ 。

对于当前枚举到的分组大小 $k$ ，我们遍历哈希表中的每个次数 $v$ ，如果 $⌊ \frac{v}{k} ⌋ < v mod k$ ，那么说明无法将这个次数 $v$ 分成 $k$ 个或 $k + 1$ 个数值相同的组，因此我们可以直接跳过这个分组大小 $k$ 。否则，说明可以分组，我们只需要尽可能分出最多的分组大小 $k + 1$ ，即可保证得到最小的分组数，因此我们可以将 $v$ 个数分成 $⌈ \frac{v}{k + 1} ⌉$ 组，累加到当前枚举的答案中。由于我们是按照 $k$ 从大到小枚举的，因此只要找到了一个合法的分组方案，那么一定是最优的。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $n u m s$ 的长度。

func minGroupsForValidAssignment(nums []int) int {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	k := len(nums)
	for _, v := range cnt {
		k = min(k, v)
	}
	for ; ; k-- {
		ans := 0
		for _, v := range cnt {
			if v/k < v%k {
				ans = 0
				break
			}
			ans += (v + k) / (k + 1)
		}
		if ans > 0 {
			return ans
		}
	}
}

力扣原题 · Doocs 题解来源

2918. 数组的最小相等和

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你两个由正整数和 0 组成的数组 nums1 和 nums2 。

你必须将两个数组中的所有 0 替换为严格正整数，并且满足两个数组中所有元素的和相等。

返回最小相等和，如果无法使两数组相等，则返回 -1 。

示例 1：

输入：nums1 = [3,2,0,1,0], nums2 = [6,5,0]
输出：12
解释：可以按下述方式替换数组中的 0 ：
- 用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 = [3,2,2,1,4] 。
- 用 1 替换 nums2 中的一个 0 。得到 nums2 = [6,5,1] 。
两个数组的元素和相等，都等于 12 。可以证明这是可以获得的最小相等和。

示例 2：

输入：nums1 = [2,0,2,0], nums2 = [1,4]
输出：-1
解释：无法使两个数组的和相等。

提示：

1 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

方法一：分情况讨论 · Go 实现

思考

每个 $0$ 至少换成 $1$ ，故两数组可达和的下界分别是把 $0$ 都看成 $1$ 后的 $s_{1}, s_{2}$ 。若无 $0$ ，和便固定，无法再抬升。

不妨设 $s_{1} \leq s_{2}$ 。相等则答案即该值；若 $s_{1} < s_{2}$ ，则较小一侧必须仍有 $0$ 才能补齐到 $s_{2}$ ，否则无解。把零个数与求和一并扫描即可判定。

我们记把数组中的 $0$ 视为 $1$ ，统计两个数组的和，分别记为 $s_{1}$ 和 $s_{2}$ 。不妨设 $s_{1} \leq s_{2}$ 。

如果 $s_{1} = s_{2}$ ，那么答案就是 $s_{1}$ 。
如果 $s_{1} < s_{2}$ ，那么 $n u m s 1$ 中必须存在 $0$ ，才能使得两个数组的和相等，此时的答案就是 $s_{2}$ 。否则，说明无法使两个数组的和相等，返回 $- 1$ 。

时间复杂度 $O (n + m)$ ，其中 $n$ 和 $m$ 分别是数组 $n u m s 1$ 和 $n u m s 2$ 的长度。空间复杂度 $O (1)$ 。

func minSum(nums1 []int, nums2 []int) int64 {
	s1, s2 := 0, 0
	hasZero := false
	for _, x := range nums1 {
		if x == 0 {
			hasZero = true
		}
		s1 += max(x, 1)
	}
	for _, x := range nums2 {
		s2 += max(x, 1)
	}
	if s1 > s2 {
		return minSum(nums2, nums1)
	}
	if s1 == s2 {
		return int64(s1)
	}
	if hasZero {
		return int64(s2)
	}
	return -1
}

力扣原题 · Doocs 题解来源

2931. 购买物品的最大开销

困难1 种解法

标签：贪心、数组、矩阵、排序、堆（优先队列）

题目、示例与约束

给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。

每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：

选择商店 i 。
购买数组中最右边的物品 j ，开销为 values[i][j] * d 。换句话说，选择该商店中还没购买过的物品中最大的下标 j ，并且花费 values[i][j] * d 去购买。

注意，所有物品都视为不同的物品。比方说如果你已经从商店 1 购买了物品 0 ，你还可以在别的商店里购买其他商店的物品 0 。

请你返回购买所有 m * n 件物品需要的 最大开销 。

示例 1：

输入：values = [[8,5,2],[6,4,1],[9,7,3]]
输出：285
解释：第一天，从商店 1 购买物品 2 ，开销为 values[1][2] * 1 = 1 。
第二天，从商店 0 购买物品 2 ，开销为 values[0][2] * 2 = 4 。
第三天，从商店 2 购买物品 2 ，开销为 values[2][2] * 3 = 9 。
第四天，从商店 1 购买物品 1 ，开销为 values[1][1] * 4 = 16 。
第五天，从商店 0 购买物品 1 ，开销为 values[0][1] * 5 = 25 。
第六天，从商店 1 购买物品 0 ，开销为 values[1][0] * 6 = 36 。
第七天，从商店 2 购买物品 1 ，开销为 values[2][1] * 7 = 49 。
第八天，从商店 0 购买物品 0 ，开销为 values[0][0] * 8 = 64 。
第九天，从商店 2 购买物品 0 ，开销为 values[2][0] * 9 = 81 。
所以总开销为 285 。
285 是购买所有 m * n 件物品的最大总开销。

示例 2：

输入：values = [[10,8,6,4,2],[9,7,5,3,2]]
输出：386
解释：第一天，从商店 0 购买物品 4 ，开销为 values[0][4] * 1 = 2 。
第二天，从商店 1 购买物品 4 ，开销为 values[1][4] * 2 = 4 。
第三天，从商店 1 购买物品 3 ，开销为 values[1][3] * 3 = 9 。
第四天，从商店 0 购买物品 3 ，开销为 values[0][3] * 4 = 16 。
第五天，从商店 1 购买物品 2 ，开销为 values[1][2] * 5 = 25 。
第六天，从商店 0 购买物品 2 ，开销为 values[0][2] * 6 = 36 。
第七天，从商店 1 购买物品 1 ，开销为 values[1][1] * 7 = 49 。
第八天，从商店 0 购买物品 1 ，开销为 values[0][1] * 8 = 64 。
第九天，从商店 1 购买物品 0 ，开销为 values[1][0] * 9 = 81 。
第十天，从商店 0 购买物品 0 ，开销为 values[0][0] * 10 = 100 。
所以总开销为 386 。
386 是购买所有 m * n 件物品的最大总开销。

提示：

1 <= m == values.length <= 10
1 <= n == values[i].length <= 10⁴
1 <= values[i][j] <= 10⁶
values[i] 按照非递增顺序排序。

方法一：贪心 + 优先队列 · Go 实现

思考

每天买一件，花费为价值乘天数，且每店必须从右往左买。天数越大乘数越大，应把大价值留到后面，等价于每天在当前各店「可买的最右件」中选最小者。

各店右端组成小根堆，弹出最小值计入 $d \cdot v$ ，再把该店前一件压入。共 $m \cdot n$ 次堆操作， $m \leq 10$ 、 $n \leq 10^{4}$ 。

根据题目描述，我们应该优先选择价值越小的物品，把价值越大的物品留到后面购买，这样才能使得总开销最大。因此，我们使用优先队列（小根堆）存储每个商店中还未购买的最小价值的物品。初始时，我们将每个商店中最右边的物品加入优先队列。

在每一天，我们从优先队列中取出价值最小的物品，将其加入答案，并将该物品所在商店中的上一个物品加入优先队列。我们重复上述操作，直到优先队列为空。

时间复杂度 $O (m \times n \times \log m)$ ，空间复杂度 $O (m)$ 。其中 $m$ 和 $n$ 分别是数组 $v a l u e s$ 的行数和列数。

func maxSpending(values [][]int) (ans int64) {
	pq := hp{}
	n := len(values[0])
	for i, row := range values {
		heap.Push(&pq, tuple{row[n-1], i, n - 1})
	}
	for d := 1; len(pq) > 0; d++ {
		p := heap.Pop(&pq).(tuple)
		ans += int64(p.v * d)
		if p.j > 0 {
			heap.Push(&pq, tuple{values[p.i][p.j-1], p.i, p.j - 1})
		}
	}
	return
}

type tuple struct{ v, i, j int }
type hp []tuple

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

力扣原题 · Doocs 题解来源

2938. 区分黑球与白球

中等1 种解法

标签：贪心、双指针、字符串

题目、示例与约束

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

示例 1：

输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。

示例 2：

输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2 。

示例 3：

输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧。

提示：

1 <= n == s.length <= 10⁵
s[i] 不是 '0'，就是 '1'。

方法一：计数模拟 · Go 实现

思考

相邻交换把所有 $1$ 换到右侧（或等价地把 $0$ 换到左侧），次数即每个 $1$ 右边的 $0$ 的个数之和。 $n \leq 10^{5}$ ，从右往左扫：遇到 $1$ 时，它还要穿过尚未计入的右侧空位 $n - i - c n t$ 。

$c n t$ 记录已经看到的 $1$ ，累加这些跨度即得最少交换。无需真正模拟移动。

我们考虑将所有的 $1$ 移到最右边，用一个变量 $c n t$ 记录当前已经移动到最右边的 $1$ 的个数，用一个变量 $a n s$ 记录移动的次数。

我们从右往左遍历字符串，如果当前位置是 $1$ ，那么我们将 $c n t$ 加一，同时将 $n - i - c n t$ 加到 $a n s$ 中，其中 $n$ 是字符串的长度。最后返回 $a n s$ 即可。

时间复杂度 $O (n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O (1)$ 。

func minimumSteps(s string) (ans int64) {
	n := len(s)
	cnt := 0
	for i := n - 1; i >= 0; i-- {
		if s[i] == '1' {
			cnt++
			ans += int64(n - i - cnt)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2939. 最大异或乘积

中等1 种解法

标签：贪心、位运算、数学

题目、示例与约束

给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2ⁿ。

由于答案可能会很大，返回它对 10⁹+ 7 取余后的结果。

注意，XOR 是按位异或操作。

示例 1：

输入：a = 12, b = 5, n = 4
输出：98
解释：当 x = 2 时，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) * (b XOR x) = 98 。
98 是所有满足 0 <= x < 2ⁿ中 (a XOR x) * (b XOR x) 的最大值。

示例 2：

输入：a = 6, b = 7 , n = 5
输出：930
解释：当 x = 25 时，(a XOR x) = 31 且 (b XOR x) = 30 。所以，(a XOR x) * (b XOR x) = 930 。
930 是所有满足 0 <= x < 2ⁿ中 (a XOR x) * (b XOR x) 的最大值。

示例 3：

输入：a = 1, b = 6, n = 3
输出：12
解释： 当 x = 5 时，(a XOR x) = 4 且 (b XOR x) = 3 。所以，(a XOR x) * (b XOR x) = 12 。
12 是所有满足 0 <= x < 2ⁿ中 (a XOR x) * (b XOR x) 的最大值。

提示：

0 <= a, b < 2⁵⁰
0 <= n <= 50

方法一：贪心 + 位运算 · Go 实现

思考

可对 $[0, n)$ 位选择 $x$ ，把 $a, b$ 同时异或。高于 $n$ 的位无法改动，先提取为 $a x, b x$ 。同一位上若 $a, b$ 已相同，则应同时置 $1$ 以增大乘积。

若该位不同，则 $x$ 只能把 $1$ 给其中一方。乘积在两因子尽量接近时更大，故把 $1$ 分给当前较小的一侧。从高位到低位贪心即可，最后取模。

根据题目描述，我们可以给 $a$ 和 $b$ 在二进制下 $[0. . n)$ 位上同时分配一个数字，最终使得 $a$ 和 $b$ 的乘积最大。

因此，我们首先提取 $a$ 和 $b$ 高于 $n$ 位的部分，分别记为 $a x$ 和 $b x$ 。

接下来，从大到小考虑 $[0. . n)$ 位上的每一位，我们将 $a$ 和 $b$ 的当前位分别记为 $x$ 和 $y$ 。

如果 $x = y$ ，那么我们可以将 $a x$ 和 $b x$ 的当前位同时置为 $1$ ，因此，我们更新 $a x = a x ∣ 1 << i$ 和 $b x = b x ∣ 1 << i$ 。否则，如果 $a x < b x$ ，要使得最终的乘积最大，我们应该让 $a x$ 的当前位置为 $1$ ，否则我们可以将 $b x$ 的当前位置为 $1$ 。

最后，我们返回 $a x \times b x mod (10^{9} + 7)$ 即为答案。

时间复杂度 $O (n)$ ，其中 $n$ 为题目给定的整数。空间复杂度 $O (1)$ 。

func maximumXorProduct(a int64, b int64, n int) int {
	const mod int64 = 1e9 + 7
	ax := (a >> n) << n
	bx := (b >> n) << n
	for i := n - 1; i >= 0; i-- {
		x, y := (a>>i)&1, (b>>i)&1
		if x == y {
			ax |= 1 << i
			bx |= 1 << i
		} else if ax < bx {
			ax |= 1 << i
		} else {
			bx |= 1 << i
		}
	}
	ax %= mod
	bx %= mod
	return int(ax * bx % mod)
}

力扣原题 · Doocs 题解来源

2952. 需要添加的硬币的最小数量

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。

如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的非空数组，删除过程不会改变剩余元素的相对位置。

示例 1：

输入：coins = [1,4,10], target = 19
输出：2
解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。

示例 2：

输入：coins = [1,4,10,5,7,19], target = 19
输出：1
解释：只需要添加一枚面值为 2 的硬币，得到硬币数组 [1,2,4,5,7,10,19] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 1 。

示例 3：

输入：coins = [1,1,1], target = 20
输出：3
解释：
需要添加面值为 4 、8 和 16 的硬币各一枚，得到硬币数组 [1,1,1,4,8,16] 。 
可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 3 。

提示：

1 <= target <= 10⁵
1 <= coins.length <= 10⁵
1 <= coins[i] <= target

方法一：贪心 + 构造 · Go 实现

思考

要用现有及新加的硬币凑出 $[1, t a r g e t]$ 。若已能表示 $[0, s - 1]$ ，加入 $x \leq s$ 可将区间扩到 $s + x - 1$ ；若下一个硬币太大，则必须先补一枚 $s$ ，区间翻倍。这是构造完全覆盖的经典贪心。

硬币先排序，指针只前进。 $s \leq t a r g e t$ 时循环，每次要么吃掉当前硬币，要么 $s \leftarrow 2 s$ 并计数。

我们不妨假设当前需要构造的金额为 $s$ ，且我们已经构造出了 $[0, . . ., s - 1]$ 内的所有金额。如果此时有一个新的硬币 $x$ ，我们把它加入到数组中，可以构造出 $[x, s + x - 1]$ 内的所有金额。

接下来，分类讨论：

如果 $x \leq s$ ，那么我们可以将上面两个区间合并，得到 $[0, s + x - 1]$ 内的所有金额。
如果 $x > s$ ，那么我们就需要添加一个面值为 $s$ 的硬币，这样可以构造出 $[0, 2 s - 1]$ 内的所有金额。然后我们再考虑 $x$ 和 $s$ 的大小关系，继续分析。

因此，我们将数组 $c o i n s$ 按照升序排序，然后从小到大遍历数组中的硬币。对于每个硬币 $x$ ，我们进行上述分类讨论，直到 $s > t a r g e t$ 为止。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 是数组的长度。

func minimumAddedCoins(coins []int, target int) (ans int) {
	slices.Sort(coins)
	for i, s := 0, 1; s <= target; {
		if i < len(coins) && coins[i] <= s {
			s += coins[i]
			i++
		} else {
			s <<= 1
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2966. 划分数组并满足最大差限制

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。

将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件：

子数组中任意两个元素的差必须 小于或等于 k 。

返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。

示例 1：

输入：nums = [1,3,4,8,7,9,3,5,1], k = 2

输出：[[1,1,3],[3,4,5],[7,8,9]]

解释：

每个数组中任何两个元素之间的差小于或等于 2。

示例 2：

输入：nums = [2,4,2,2,5,2], k = 2

输出：[]

解释：

将 nums 划分为 2 个长度为 3 的数组的不同方式有：

[[2,2,2],[2,4,5]] （及其排列）
[[2,2,4],[2,2,5]] （及其排列）

因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。

示例 3：

输入：nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14

输出：[[2,2,2],[4,5,5],[5,5,7],[7,8,8],[9,9,10],[11,12,12]]

解释：

每个数组中任何两个元素之间的差小于或等于 14。

提示：

n == nums.length
1 <= n <= 10⁵
n 是 3 的倍数
1 <= nums[i] <= 10⁵
1 <= k <= 10⁵

方法一：排序 · Go 实现

思考

把数组分成若干长为 $3$ 的组，组内最大差 $\leq k$ ，并按任意顺序返回。排序后相邻三元组是差最小的分法：跨更远的元素只会增大极差。

每三段检查 $t [2] - t [0]$ ，超限则无解。 $n$ 为 $3$ 的倍数且可达 $10^{5}$ ，排序后线性分组。

我们先对数组进行排序，然后每次取出三个元素，如果这三个元素的最大值和最小值的差大于 $k$ ，则无法满足条件，返回空数组。否则，我们将这三个元素组成的数组加入答案数组中。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组的长度。

func divideArray(nums []int, k int) [][]int {
	sort.Ints(nums)
	ans := [][]int{}
	for i := 0; i < len(nums); i += 3 {
		t := slices.Clone(nums[i : i+3])
		if t[2]-t[0] > k {
			return [][]int{}
		}
		ans = append(ans, t)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2967. 使数组成为等数数组的最小代价

中等1 种解法

标签：贪心、数组、数学、二分查找、排序

题目、示例与约束

给你一个整数数组 nums。

在一次操作中，你可以选择一个下标 i，并将 nums[i] 加 1 或减 1。

返回将 nums 中每个元素都变为相同的正回文整数所需的最小操作数。

示例 1：

输入：nums = [1,2,3,4,5]
输出：6
解释：增加 nums[0] 两次和 nums[1] 一次，然后减少 nums[3] 一次和 nums[4] 两次。经过 6 次操作，nums 变为 [3,3,3,3,3]，3 是一个正回文整数。
可以证明这是所需的最小操作次数。

示例 2：

输入：nums = [10,12,13,14,15]
输出：11
解释：增加 nums[0] 一次，然后分别减少 nums[1]、nums[2]、nums[3] 和 nums[4] 1、2、3 和 4 次。经过 11 次操作后，nums 变为 [11,11,11,11,11]，11 是一个正回文整数。
可以证明这是所需的最小操作次数。

示例 3 ：

输入：nums = [22,33,22,33,22]
输出：22
解释：减少 nums[1] 和 nums[3] 各 11 次。经过 22 次操作，nums 变为 [22,22,22,22,22]，22 是一个正回文整数。
可以证明这是所需的最小操作次数。

提示：

1 <= n <= 10⁵
1 <= nums[i] <= 10⁹

方法一：预处理 + 排序 + 二分查找 · Go 实现

思考

把所有数改成同一个回文数，代价为绝对差之和，最优目标接近中位数。回文数可在 $[1, 10^{5}]$ 枚举半边并镜像，预处理排序后的 $p s$ 。

对 $n u m s$ 排序取中位数，在 $p s$ 中二分出邻近的两三个回文，计算代价取最小。 $n \leq 10^{5}$ ，避免枚举全部目标。

题目中回文数的范围是 $[1, 10^{9}]$ ，回文数由于对称性，我们可以在 $[1, 10^{5}]$ 的范围内枚举，然后将其翻转后拼接，得到所有的回文数，注意，如果是奇数长度的回文数，我们在翻转前要去掉最后一位。预处理得到的回文数数组记为 $p s$ 。我们对数组 $p s$ 进行排序。

接下来，我们对数组 $n u m s$ 进行排序，然后取 $n u m s$ 的中位数 $x$ ，我们只需要通过二分查找，在回文数组 $p s$ 中，找到一个与 $x$ 最接近的数，然后计算 $n u m s$ 变成这个数的代价，即可得到答案。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (M)$ 。其中 $n$ 是数组 $n u m s$ 的长度，而 $M$ 是回文数组 $p s$ 的长度。

相似题目：

906. 超级回文数

var ps [2 * 100000]int64

func init() {
	for i := 1; i <= 100000; i++ {
		s := strconv.Itoa(i)
		t1 := reverseString(s)
		t2 := reverseString(s[:len(s)-1])
		ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
		ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
	}
	sort.Slice(ps[:], func(i, j int) bool {
		return ps[i] < ps[j]
	})
}

func reverseString(s string) string {
	cs := []rune(s)
	for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
		cs[i], cs[j] = cs[j], cs[i]
	}
	return string(cs)
}

func minimumCost(nums []int) int64 {
	sort.Ints(nums)
	i := sort.Search(len(ps), func(i int) bool {
		return ps[i] >= int64(nums[len(nums)/2])
	})

	f := func(x int64) int64 {
		var ans int64
		for _, v := range nums {
			ans += int64(abs(int(x - int64(v))))
		}
		return ans
	}

	ans := int64(math.MaxInt64)
	for j := i - 1; j <= i+1; j++ {
		if 0 <= j && j < len(ps) {
			ans = min(ans, f(ps[j]))
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

2971. 找到最大周长的多边形

中等1 种解法

标签：贪心、数组、多边形、前缀和、排序

题目、示例与约束

给你一个长度为 n 的正整数数组 nums 。

多边形 指的是一个至少有 3 条边的封闭二维图形。多边形的 最长边 一定小于所有其他边长度之和。

如果你有 k （k >= 3）个正数 a₁，a₂，a₃, ...，a_k 满足 a₁ <= a₂ <= a₃ <= ... <= a_k 且 a₁ + a₂ + a₃ + ... + a_k-1 > a_k，那么一定存在一个 k 条边的多边形，每条边的长度分别为 a₁ ，a₂ ，a₃ ， ...，a_k 。

一个多边形的周长指的是它所有边之和。

请你返回从 nums 中可以构造的 多边形 的 最大周长 。如果不能构造出任何多边形，请你返回 -1 。

示例 1：

输入：nums = [5,5,5]
输出：15
解释：nums 中唯一可以构造的多边形为三角形，每条边的长度分别为 5 ，5 和 5 ，周长为 5 + 5 + 5 = 15 。

示例 2：

输入：nums = [1,12,1,2,5,50,3]
输出：12
解释：最大周长多边形为五边形，每条边的长度分别为 1 ，1 ，2 ，3 和 5 ，周长为 1 + 1 + 2 + 3 + 5 = 12 。
我们无法构造一个包含变长为 12 或者 50 的多边形，因为其他边之和没法大于两者中的任何一个。
所以最大周长为 12 。

示例 3：

输入：nums = [5,5,50]
输出：-1
解释：无法构造任何多边形，因为多边形至少要有 3 条边且 50 > 5 + 5 。

提示：

3 <= n <= 10⁵
1 <= nums[i] <= 10⁹

方法一：排序 + 前缀和 · Go 实现

思考

多边形条件是最长边小于其余边之和。排序后最长边若取 $a_{k}$ ，其余边应取更小的 $k - 1$ 条才能尽量构成且周长更大，故只需检查前 $k$ 项。

前缀和 $s [k - 1] > n u m s [k - 1]$ 则更新周长 $s [k]$ 。从 $k = 3$ 扫到 $n$ ， $n \leq 10^{5}$ 。

我们可以将数组 $n u m s$ 排序，然后定义一个答案变量 $a n s$ ，初始值为 $- 1$ 。

接下来，我们在 $[3, n]$ 的范围内枚举最长边 $a_{k}$ ，如果 $a_{1} + a_{2} + \dots + a_{k - 1} > a_{k}$ ，那么就可以构成一个周长为 $a_{1} + a_{2} + \dots + a_{k}$ 的多边形。这里，我们可以使用前缀和数组 $s$ ，其中 $s_{i} = a_{1} + a_{2} + \dots + a_{i}$ ，那么 $a_{1} + a_{2} + \dots + a_{k - 1} = s_{k - 1}$ ，判断是否 $s_{k - 1} > a_{k}$ ，如果是，那么更新答案 $a n s = max (a n s, s_{k})$ 。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $n u m s$ 的长度。

func largestPerimeter(nums []int) int64 {
	sort.Ints(nums)
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	ans := -1
	for k := 3; k <= n; k++ {
		if s[k-1] > nums[k-1] {
			ans = max(ans, s[k])
		}
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

3002. 移除后集合的最多元素数

中等1 种解法

标签：贪心、数组、哈希表

题目、示例与约束

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们的长度都是偶数 n 。

你必须从 nums1 中移除 n / 2 个元素，同时从 nums2 中也移除 n / 2 个元素。移除之后，你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。

返回集合 s可能的最多包含多少元素。

示例 1：

输入：nums1 = [1,2,1,2], nums2 = [1,1,1,1]
输出：2
解释：从 nums1 和 nums2 中移除两个 1 。移除后，数组变为 nums1 = [2,2] 和 nums2 = [1,1] 。因此，s = {1,2} 。
可以证明，在移除之后，集合 s 最多可以包含 2 个元素。

示例 2：

输入：nums1 = [1,2,3,4,5,6], nums2 = [2,3,2,3,2,3]
输出：5
解释：从 nums1 中移除 2、3 和 6 ，同时从 nums2 中移除两个 3 和一个 2 。移除后，数组变为 nums1 = [1,4,5] 和 nums2 = [2,3,2] 。因此，s = {1,2,3,4,5} 。
可以证明，在移除之后，集合 s 最多可以包含 5 个元素。

示例 3：

输入：nums1 = [1,1,2,2,3,3], nums2 = [4,4,5,5,6,6]
输出：6
解释：从 nums1 中移除 1、2 和 3 ，同时从 nums2 中移除 4、5 和 6 。移除后，数组变为 nums1 = [1,2,3] 和 nums2 = [4,5,6] 。因此，s = {1,2,3,4,5,6} 。
可以证明，在移除之后，集合 s 最多可以包含 6 个元素。

提示：

n == nums1.length == nums2.length
1 <= n <= 2 * 10⁴
n是偶数。
1 <= nums1[i], nums2[i] <= 10⁹

方法一 · Go 实现

思考

两数组等长 $n$ 且为偶数， $n \leq 2 \times 10^{4}$ ，需各删去 $n / 2$ 个元素后使并集最大。枚举删除方案不可行。

并集大小受三部分约束：仅出现在 ${nums}_{1}$ 的值、仅出现在 ${nums}_{2}$ 的值，以及交集。每边最多保留 $n / 2$ 个位置。

因此先把两边的独有元素尽量填满配额，剩余空位再由交集填补，最后与 $n$ 取最小值。集合差与交一次性给出这三类计数。

func maximumSetSize(nums1 []int, nums2 []int) int {
	s1 := map[int]bool{}
	s2 := map[int]bool{}
	for _, x := range nums1 {
		s1[x] = true
	}
	for _, x := range nums2 {
		s2[x] = true
	}
	a, b, c := 0, 0, 0
	for x := range s1 {
		if !s2[x] {
			a++
		}
	}
	for x := range s2 {
		if !s1[x] {
			b++
		} else {
			c++
		}
	}
	n := len(nums1)
	a = min(a, n/2)
	b = min(b, n/2)
	return min(a+b+c, n)
}

力扣原题 · Doocs 题解来源

3012. 通过操作使数组长度最小

中等1 种解法

标签：贪心、数组、数学、数论

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，它只包含正整数。

你的任务是通过进行以下操作 任意次 （可以是 0 次） 最小化 nums 的长度：

在 nums 中选择 两个不同 的下标 i 和 j ，满足 nums[i] > 0 且 nums[j] > 0 。
将结果 nums[i] % nums[j] 插入 nums 的结尾。
将 nums 中下标为 i 和 j 的元素删除。

请你返回一个整数，它表示进行任意次操作以后 nums 的 最小长度 。

示例 1：

输入：nums = [1,4,3,1]
输出：1
解释：使数组长度最小的一种方法是：
操作 1 ：选择下标 2 和 1 ，插入 nums[2] % nums[1] 到数组末尾，得到 [1,4,3,1,3] ，然后删除下标为 2 和 1 的元素。
nums 变为 [1,1,3] 。
操作 2 ：选择下标 1 和 2 ，插入 nums[1] % nums[2] 到数组末尾，得到 [1,1,3,1] ，然后删除下标为 1 和 2 的元素。
nums 变为 [1,1] 。
操作 3 ：选择下标 1 和 0 ，插入 nums[1] % nums[0] 到数组末尾，得到 [1,1,0] ，然后删除下标为 1 和 0 的元素。
nums 变为 [0] 。
nums 的长度无法进一步减小，所以答案为 1 。
1 是可以得到的最小长度。

示例 2：

输入：nums = [5,5,5,10,5]
输出：2
解释：使数组长度最小的一种方法是：
操作 1 ：选择下标 0 和 3 ，插入 nums[0] % nums[3] 到数组末尾，得到 [5,5,5,10,5,5] ，然后删除下标为 0 和 3 的元素。
nums 变为 [5,5,5,5] 。
操作 2 ：选择下标 2 和 3 ，插入 nums[2] % nums[3] 到数组末尾，得到 [5,5,5,5,0] ，然后删除下标为 2 和 3 的元素。
nums 变为 [5,5,0] 。
操作 3 ：选择下标 0 和 1 ，插入 nums[0] % nums[1] 到数组末尾，得到 [5,5,0,0] ，然后删除下标为 0 和 1 的元素。
nums 变为 [0,0] 。
nums 的长度无法进一步减小，所以答案为 2 。
2 是可以得到的最小长度。

示例 3：

输入：nums = [2,3,4]
输出：1
解释：使数组长度最小的一种方法是：
操作 1 ：选择下标 1 和 2 ，插入 nums[1] % nums[2] 到数组末尾，得到 [2,3,4,3] ，然后删除下标为 1 和 2 的元素。
nums 变为 [2,3] 。
操作 2 ：选择下标 1 和 0 ，插入 nums[1] % nums[0] 到数组末尾，得到 [2,3,1] ，然后删除下标为 1 和 0 的元素。
nums 变为 [1] 。
nums 的长度无法进一步减小，所以答案为 1 。
1 是可以得到的最小长度。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

方法一：分情况讨论 · Go 实现

思考

操作把两个正数换成其余数，长度减一， $n \leq 10^{5}$ 不能模拟到只剩少数元素。

余数严格小于被减的较大数，故全局最小值 $mi$ 一旦存在且并非所有数都是它的倍数，就能造出比 $mi$ 更小的值，再与其余数配对后只剩一个。

若所有数都是 $mi$ 的倍数，则无法造出更小正数，剩下的只能是 $mi$ 本身，两两合并后长度为 $⌈ cnt / 2 ⌉$ 。

我们不妨记数组 $n u m s$ 的最小的元素为 $m i$ 。

如果 $m i$ 只出现一次，那么我们将 $m i$ 与数组 $n u m s$ 的其他元素进行操作，可以将其他元素全部消去，最终剩下 $m i$ 一个元素，答案为 $1$ 。

如果 $m i$ 出现多次，我们判断数组 $n u m s$ 中的元素是否都是 $m i$ 的倍数。如果不是，即存在至少一个元素 $x$ ，使得 $0 < x mod m i < m i$ ，说明我们可以通过操作，构造出一个小于 $m i$ 的元素，那么这个小于 $m i$ 的元素与其他元素进行操作，可以将其他元素全部消去，最终剩下这个小于 $m i$ 的元素，答案为 $1$ ；如果都是 $m i$ 的倍数，我们可以先借助 $m i$ ，将所有大于 $m i$ 的元素消去，最终剩下的元素都是 $m i$ ，个数为 $c n t$ ，两两配对，每两个元素进行一次操作，最终剩下 $⌈ c n t / 2 ⌉$ 个元素，答案为 $⌈ c n t / 2 ⌉$ 。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度 $O (1)$ 。

func minimumArrayLength(nums []int) int {
	mi := slices.Min(nums)
	cnt := 0
	for _, x := range nums {
		if x%mi != 0 {
			return 1
		}
		if x == mi {
			cnt++
		}
	}
	return (cnt + 1) / 2
}

力扣原题 · Doocs 题解来源

3014. 输入单词需要的最少按键次数 I

简单1 种解法

标签：贪心、数学、字符串

题目、示例与约束

给你一个字符串 word，由不同小写英文字母组成。

电话键盘上的按键与不同小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。

现在允许你将编号为 2 到 9 的按键重新映射到不同字母集合。每个按键可以映射到 任意数量 的字母，但每个字母必须恰好映射到一个按键上。你需要找到输入字符串 word 所需的最少按键次数。

返回重新映射按键后输入 word 所需的最少按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xycdefghij"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 2 上按两次
"c" -> 在按键 3 上按一次
"d" -> 在按键 3 上按两次
"e" -> 在按键 4 上按一次
"f" -> 在按键 5 上按一次
"g" -> 在按键 6 上按一次
"h" -> 在按键 7 上按一次
"i" -> 在按键 8 上按一次
"j" -> 在按键 9 上按一次
总成本为 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12 。
可以证明不存在其他成本更低的映射方案。

提示：

1 <= word.length <= 26
word 仅由小写英文字母组成。
word 中的所有字母互不相同。

方法一：贪心 · Go 实现

思考

字母互不相同且长度不超过 $26$ ，八个按键上只能按出现顺序分配。每种字母按一次、两次……的代价随该键已放字母数递增。

因各字母只出现一次，最优是把它们尽量均匀地摊到 $8$ 个键上，即先填满每一轮的 $8$ 个「第 $k$ 次」位置。

按轮次累加 $k \times 8$ ，最后一轮用余数即可，不必真正分配字母。

我们注意到，字符串 $w o r d$ 中的所有字母都是不同的，因此，我们贪心地将字母均匀地分配到 $8$ 个按键上，即可使得按键次数最少。

时间复杂度 $O (n / 8)$ ，其中 $n$ 是字符串 $w o r d$ 的长度。空间复杂度 $O (1)$ 。

func minimumPushes(word string) (ans int) {
	n := len(word)
	k := 1
	for i := 0; i < n/8; i++ {
		ans += k * 8
		k++
	}
	ans += k * (n % 8)
	return
}

力扣原题 · Doocs 题解来源

3016. 输入单词需要的最少按键次数 II

中等1 种解法

标签：贪心、哈希表、字符串、计数、排序

题目、示例与约束

给你一个字符串 word，由小写英文字母组成。

返回重新映射按键后输入 word 所需的最少按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xyzxyzxyzxyz"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 3 上按一次
"z" -> 在按键 4 上按一次
总成本为 1 * 4 + 1 * 4 + 1 * 4 = 12 。
可以证明不存在其他成本更低的映射方案。
注意按键 9 没有映射到任何字母：不必让每个按键都存在与之映射的字母，但是每个字母都必须映射到按键上。

示例 3：

输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
"f" -> 在按键 7 上按一次
"g" -> 在按键 8 上按一次
"h" -> 在按键 9 上按两次
"i" -> 在按键 9 上按一次
总成本为 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24 。
可以证明不存在其他成本更低的映射方案。

提示：

1 <= word.length <= 10⁵
word 仅由小写英文字母组成。

方法一：贪心 + 排序 · Go 实现

思考

与 I 不同，字母可重复且 $n \leq 10^{5}$ 。同一字母必须放在同一键上，代价等于其频次乘以该键上的按压档位。

高频字母应占用更靠前的档位。先统计 $26$ 个频次，从大到小排序后，第 $i$ 个字母的档位为 $⌊ i / 8 ⌋ + 1$ 。

排序后按这一公式加权求和即可。

我们用一个哈希表或数组 $c n t$ 统计字符串 $w o r d$ 中每个字母出现的次数。接下来，按照字母出现的次数从大到小排序，然后每 $8$ 个字母一组，将每组中的字母分配到 $8$ 个按键上。

时间复杂度 $O (n + | Σ | \times \log | Σ |)$ ，空间复杂度 $O (| Σ |)$ 。其中 $n$ 是字符串 $w o r d$ 的长度，而 $Σ$ 是字符串 $w o r d$ 中出现的字母集合。

func minimumPushes(word string) (ans int) {
	cnt := make([]int, 26)
	for _, c := range word {
		cnt[c-'a']++
	}
	sort.Ints(cnt)
	for i := 0; i < 26; i++ {
		ans += (i/8 + 1) * cnt[26-i-1]
	}
	return
}

力扣原题 · Doocs 题解来源

3022. 给定操作次数内使剩余元素的或值最小

困难1 种解法

标签：贪心、位运算、数组

题目、示例与约束

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

一次操作中，你可以选择 nums 中满足 0 <= i < nums.length - 1 的一个下标 i ，并将 nums[i] 和 nums[i + 1] 替换为数字 nums[i] & nums[i + 1] ，其中 & 表示按位 AND 操作。

请你返回至多 k 次操作以内，使 nums 中所有剩余元素按位 OR 结果的 最小值 。

示例 1：

输入：nums = [3,5,3,2,7], k = 2
输出：3
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [1,3,2,7] 。
2. 将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ，得到 nums 为 [1,3,2] 。
最终数组的按位或值为 3 。
3 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

示例 2：

输入：nums = [7,3,15,14,2,8], k = 4
输出：2
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,15,14,2,8] 。
2. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,14,2,8] 。
3. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [2,2,8] 。
4. 将 nums[1] 和 nums[2] 替换为 (nums[1] & nums[2]) ，得到 nums 为 [2,0] 。
最终数组的按位或值为 2 。
2 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

示例 3：

输入：nums = [10,7,10,3,9,14,9,4], k = 1
输出：15
解释：不执行任何操作，nums 的按位或值为 15 。
15 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] < 2³⁰
0 <= k < nums.length

方法一 · Go 实现

思考

每次把相邻两项换成它们的按位与，最多 $k$ 次， $n \leq 10^{5}$ 。最终序列的 OR 希望尽量小。

OR 的高位比低位更值钱，应从高到低尝试关掉每一位。关掉某位，意味着可以用至多 $k$ 次与运算，把所有「该位为 $1$ 」的段合并掉。

对每一位构造探测掩码，扫描数组统计必须额外消耗的合并次数；若不超过 $k$ 则该位可以关掉，否则记入答案。

func minOrAfterOperations(nums []int, k int) int {
    ans := 0
    rans := 0
    for i := 29; i >= 0; i-- {
        test := ans + (1 << i)
        cnt := 0
        val := 0
        for _, num := range nums {
            if val == 0 {
                val = test & num
            } else {
                val &= test & num
            }
            if val != 0 {
                cnt++
            }
        }
        if cnt > k {
            rans += (1 << i)
        } else {
            ans += (1 << i)
        }
    }
    return rans
}

力扣原题 · Doocs 题解来源

3035. 回文字符串的最大数量

中等1 种解法

标签：贪心、数组、哈希表、字符串、计数、排序

题目、示例与约束

给你一个下标从 0 开始的字符串数组 words ，数组的长度为 n ，且包含下标从 0 开始的若干字符串。

你可以执行以下操作任意次数（包括零次）：

选择整数i、j、x和y，满足0 <= i, j < n，0 <= x < words[i].length，0 <= y < words[j].length，交换字符 words[i][x] 和 words[j][y] 。

返回一个整数，表示在执行一些操作后，words 中可以包含的回文串的最大数量。

注意：在操作过程中，i 和 j 可以相等。

示例 1：

输入：words = ["abbb","ba","aa"]
输出：3
解释：在这个例子中，获得最多回文字符串的一种方式是：
选择 i = 0, j = 1, x = 0, y = 0，交换 words[0][0] 和 words[1][0] 。words 变成了 ["bbbb","aa","aa"] 。
words 中的所有字符串都是回文。
因此，可实现的回文字符串的最大数量是 3 。

示例 2：

输入：words = ["abc","ab"]
输出：2
解释：在这个例子中，获得最多回文字符串的一种方式是： 
选择 i = 0, j = 1, x = 1, y = 0，交换 words[0][1] 和 words[1][0] 。words 变成了 ["aac","bb"] 。
选择 i = 0, j = 0, x = 1, y = 2，交换 words[0][1] 和 words[0][2] 。words 变成了 ["aca","bb"] 。
两个字符串都是回文 。
因此，可实现的回文字符串的最大数量是 2。

示例 3：

输入：words = ["cd","ef","a"]
输出：1
解释：在这个例子中，没有必要执行任何操作。
words 中有一个回文 "a" 。
可以证明，在执行任何次数操作后，无法得到更多回文。
因此，答案是 1 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成。

方法一 · Go 实现

思考

任意两串之间可交换字符，目标是让尽量多的串成为回文。 $n \leq 1000$ ，总长有限。

回文只关心偶数位置的成对字母；所有串的字母可视为一个公共池。奇数次字母各浪费一个，剩余成对容量按串长从短到长分配最省。

异或掩码统计奇数次字母个数，总长减去该个数得到可用偶数位。按长度排序后依次扣 $2 ⌊ | w | / 2 ⌋$ 。

func maxPalindromesAfterOperations(words []string) (ans int) {
	var s, mask int
	for _, w := range words {
		s += len(w)
		for _, c := range w {
			mask ^= 1 << (c - 'a')
		}
	}
	s -= bits.OnesCount(uint(mask))
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})
	for _, w := range words {
		s -= len(w) / 2 * 2
		if s < 0 {
			break
		}
		ans++
	}
	return
}

力扣原题 · Doocs 题解来源

3049. 标记所有下标的最早秒数 II

困难1 种解法

标签：贪心、数组、二分查找、堆（优先队列）

题目、示例与约束

给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。

一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中所有下标。

从第 1 秒到第 m 秒（包括第 m 秒），对于每一秒 s ，你可以执行以下操作之一：

选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
将 nums[changeIndices[s]] 设置成任意的非负整数。
选择范围 [1, n] 中的一个下标 i ，满足 nums[i] 等于 0, 并标记下标 i 。
什么也不做。

请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中所有下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。

示例 1：

输入：nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
输出：6
解释：这个例子中，我们总共有 7 秒。按照以下操作标记所有下标：
第 1 秒：将 nums[changeIndices[1]] 变为 0 。nums 变为 [0,2,3] 。
第 2 秒：将 nums[changeIndices[2]] 变为 0 。nums 变为 [0,2,0] 。
第 3 秒：将 nums[changeIndices[3]] 变为 0 。nums 变为 [0,0,0] 。
第 4 秒：标记下标 1 ，因为 nums[1] 等于 0 。
第 5 秒：标记下标 2 ，因为 nums[2] 等于 0 。
第 6 秒：标记下标 3 ，因为 nums[3] 等于 0 。
现在所有下标已被标记。
最早可以在第 6 秒标记所有下标。
所以答案是 6 。

示例 2：

输入：nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
输出：7
解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标：
第 1 秒：标记下标 1 ，因为 nums[1] 等于 0 。
第 2 秒：标记下标 2 ，因为 nums[2] 等于 0 。
第 3 秒：将 nums[4] 减少 1 。nums 变为 [0,0,1,1] 。
第 4 秒：将 nums[4] 减少 1 。nums 变为 [0,0,1,0] 。
第 5 秒：将 nums[3] 减少 1 。nums 变为 [0,0,0,0] 。
第 6 秒：标记下标 3 ，因为 nums[3] 等于 0 。
第 7 秒：标记下标 4 ，因为 nums[4] 等于 0 。
现在所有下标已被标记。
最早可以在第 7 秒标记所有下标。
所以答案是 7 。

示例 3：

输入：nums = [1,2,3], changeIndices = [1,2,3]
输出：-1
解释：这个例子中，无法标记所有下标，因为我们没有足够的秒数。
所以答案是 -1 。

提示：

1 <= n == nums.length <= 5000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 5000
1 <= changeIndices[i] <= n

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可 · 原题解

更形象的题意

题意有点抽象，形象地解释一下：

你有 $n$ 门课程需要考试，第 $i$ 门课程需要用 $nums [i]$ 天复习。同一天只能复习一门课程（慢速复习）。

在第 $i$ 天，你可以快速搞定第 $changeIndices [i]$ 门课程的复习。

你可以在任意一天完成一门课程的考试（前提是复习完成）。考试这一天不能复习。

搞定所有课程的复习+考试，至少要多少天？

提示 1

答案越大，越能够搞定所有课程，反之越不能。据此，可以二分答案。

提示 2

如果决定在第 $i$ 天快速复习第 $changeIndices [i]$ 门课程，那么在第 $i$ 天前慢速复习这门课程是没有意义的。同理，如果决定慢速复习某门课程，那么也没必要对这门课程使用快速复习。

在 $nums [i] > 1$ 的情况下，如果用快速复习+考试，只需要花费 $2$ 天。这比只用慢速复习+考试要更快。

但是！如果一门课程对应的 $changeIndices$ 很靠后，可能没有时间快速复习这门课程并完成考试。比如只剩下 $2$ 天，但是还有 $3$ 门课程没有考。这样的课程用慢速复习更合适。

此外，如果一门课程的复习时间很长（ $nums [i]$ 很大），当我们把后续时间都用在快速复习其它复习时间比较小的课程上，可能就没有时间快速复习 $nums [i]$ 很大的课程了（还要留一天来考试）。

如何权衡哪些课程快速复习，哪些课程慢速复习呢？

提示 3

设二分的答案为 $mx$ 。我们从下标 $mx - 1$ 开始，倒着遍历 $changeIndices$ 的前 $mx$ 个数，和 3048. 标记所有下标的最早秒数 I 一样，尽量选择靠左的时间来快速复习，这样右边就有更充足的时间用来考试。

用一个数组 $firstT$ 记录 $1$ 到 $n$ （代码中是 $0$ 到 $n - 1$ ）在 $changeIndices$ 中首次出现的下标。初始化可用天数 $cnt = 0$ 。

设当前天数为 $t$ ，设 $i = changeIndices [t] - 1$ 。
如果 $i$ 不是在 $changeIndices$ 中首次出现的数，或者 $nums [i] \leq 1$ ，那么把时间留给左边再决定做什么， $cnt$ 加一。
否则如果 $cnt > 0$ ，我们直接快速复习第 $i$ 门课程，并消耗一天用来考试，把 $cnt$ 减一。然后把 $nums [i]$ 加到一个小根堆中。
否则如果 $cnt = 0$ ，那么尝试在小根堆中「反悔」一个复习时间比 $nums [i]$ 小的数。如果堆为空或者堆顶大于等于 $nums [i]$ 就不反悔，否则弹出堆顶并把 $cnt$ 加二（一天快速复习，一天考试），然后做法同上述 $cnt > 0$ 的情况。这里从堆中弹出的课程，相当于用更靠左的时间去慢速复习+考试。

遍历结束后，对于每个未快速复习的课程，全部使用慢速复习+考试，将 $cnt$ 减去这些课程对应的 $nums [i] + 1$ 。如果最终 $cnt \geq 0$ 则说明可以在 $mx$ 天内搞定所有课程的复习+考试。这一过程可以在遍历中动态维护，具体见代码。

下面代码用的开区间二分（其它写法也可以），原理请看二分查找红蓝染色法【基础算法精讲 04】。

本题视频讲解（第四题）

复杂度分析

时间复杂度： $O (m \log m \log n)$ ，其中 $n$ 为 $nums$ 的长度， $m$ 为 $changeIndices$ 的长度。二分的时候保证 $n \leq m$ ，时间复杂度以 $m$ 为主。注意堆中至多有 $n$ 个元素。
空间复杂度： $O (n)$ 。

专题训练

见下面贪心题单的「§1.9 反悔贪心」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

import (
	"container/heap"
	"sort"
)

// https://space.bilibili.com/206214
func earliestSecondToMarkIndices(nums, changeIndices []int) int {
	n, m := len(nums), len(changeIndices)
	if n > m {
		return -1
	}

	total := n
	for _, v := range nums {
		total += v
	}

	firstT := make([]int, n)
	for t := m - 1; t >= 0; t-- {
		firstT[changeIndices[t]-1] = t + 1
	}

	h := hp{}
	ans := n + sort.Search(m+1-n, func(mx int) bool {
		mx += n
		cnt, slow := 0, total
		h.IntSlice = h.IntSlice[:0]
		for t := mx - 1; t >= 0; t-- {
			i := changeIndices[t] - 1
			v := nums[i]
			if v <= 1 || t != firstT[i]-1 {
				cnt++ // 留给左边，用来快速复习/考试
				continue
			}
			if cnt == 0 {
				if h.Len() == 0 || v <= h.IntSlice[0] {
					cnt++ // 留给左边，用来快速复习/考试
					continue
				}
				slow += heap.Pop(&h).(int) + 1
				cnt += 2 // 反悔：一天快速复习，一天考试
			}
			slow -= v + 1
			cnt-- // 快速复习，然后消耗一天来考试
			heap.Push(&h, v)
		}
		return cnt >= slow // 剩余天数不能慢速复习+考试
	})
	if ans > m {
		return -1
	}
	return ans
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

力扣原题 · Doocs 题解来源

3074. 重新分装苹果

简单1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的最小数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

提示：

1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
输入数据保证可以将包裹中的苹果重新分装到箱子中。

方法一：贪心 + 排序 · Go 实现

思考

苹果可任意重装，箱子容量固定，求最少箱子数。 $n, m \leq 50$ 。

只需容量之和达到苹果总数，与分配细节无关。优先用大箱子能最快凑够。

容量降序排列，累减苹果总和直至非正，返回已用只数。

为了使得需要的箱子数量尽可能少，我们应该优先使用容量大的箱子。因此，我们可以对箱子按照容量从大到小排序，然后依次使用箱子，直到所有的苹果都被分装完，返回此时使用的箱子数量。

时间复杂度 $O (m \times \log m + n)$ ，空间复杂度 $O (\log m)$ 。其中 $m$ 和 $n$ 分别是数组 $capacity$ 和 $apple$ 的长度。

func minimumBoxes(apple []int, capacity []int) int {
	sort.Ints(capacity)
	s := 0
	for _, x := range apple {
		s += x
	}
	for i := 1; ; i++ {
		s -= capacity[len(capacity)-i]
		if s <= 0 {
			return i
		}
	}
}

力扣原题 · Doocs 题解来源

3075. 幸福值最大化的选择方案

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有尚未被选中的孩子的 幸福值 将减少 1 。注意，幸福值不能变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。

提示：

1 <= n == happiness.length <= 2 * 10⁵
1 <= happiness[i] <= 10⁸
1 <= k <= n

方法一：贪心 + 排序 · Go 实现

思考

每次选一个孩子，其余未选者幸福值减 $1$ （不低于 $0$ ）。 $n \leq 2 \times 10^{5}$ ，选 $k$ 个。

后选的人会被前面的选择连减多次，因此应先选当前幸福值更大者，第 $i$ 个被选者实际贡献 $max (h - i, 0)$ 。

降序排序后取前 $k$ 项按上式求和。

为了使得幸福值之和尽可能大，我们应该优先选择幸福值大的孩子。因此，我们可以对孩子按照幸福值从大到小排序，然后依次选择 $k$ 个孩子。对于当前第 $i$ 个孩子，能够得到的幸福值为 $max (happiness [i] - i, 0)$ ，最后返回这 $k$ 个孩子的幸福值之和。

时间复杂度 $O (n \times \log n + k)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 是数组 $happiness$ 的长度。

func maximumHappinessSum(happiness []int, k int) (ans int64) {
	sort.Ints(happiness)
	for i := 0; i < k; i++ {
		x := happiness[len(happiness)-i-1] - i
		ans += int64(max(x, 0))
	}
	return
}

力扣原题 · Doocs 题解来源

3081. 替换字符串中的问号使分数最小

中等1 种解法

标签：贪心、哈希表、字符串、计数、排序、堆（优先队列）

题目、示例与约束

给你一个字符串 s 。s[i] 要么是小写英文字母，要么是问号 '?' 。

对于长度为 m 且只含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同字符出现的次数。

字符串 t 的分数为所有下标 i 的 cost(i) 之和。

比方说，字符串 t = "aab" ：

cost(0) = 0
cost(1) = 1
cost(2) = 0
所以，字符串 "aab" 的分数为 0 + 1 + 0 = 1 。

你的任务是用小写英文字母替换 s 中所有问号，使 s 的分数最小。

请你返回替换所有问号 '?' 之后且分数最小的字符串。如果有多个字符串的 分数最小 ，那么返回字典序最小的一个。

示例 1：

输入：s = "???"

输出： "abc"

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abc" 。

对于字符串 "abc" ，cost(0) = 0 ，cost(1) = 0 和 cost(2) = 0 。

"abc" 的分数为 0 。

其他修改 s 得到分数 0 的字符串为 "cba" ，"abz" 和 "hey" 。

这些字符串中，我们返回字典序最小的。

示例 2：

输入： s = "a?a?"

输出： "abac"

解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abac" 。

对于字符串 "abac" ，cost(0) = 0 ，cost(1) = 0 ，cost(2) = 1 和 cost(3) = 0 。

"abac" 的分数为 1 。

提示：

1 <= s.length <= 10⁵
s[i] 要么是小写英文字母，要么是 '?' 。

方法一：贪心 + 优先队列 · Go 实现

思考

把 ? 换成小写字母，使 $\sum freq (freq - 1) / 2$ 最小，且结果字典序尽量小。 $n \leq 10^{5}$ 。

该平方和在频次越均衡时越小，因此每次应把一个 ? 给当前出现次数最少的字母。得到的字母多重集再按字典序填回 ? 的位置。

小根堆维护 $26$ 个 $(cnt, c)$ ，弹出写入列表后排序，再按原串顺序替换问号。

根据题目，我们可以发现，如果一个字母 $c$ 出现的次数为 $v$ ，那么它对答案贡献的分数为 $1 + 2 + \dots + (v - 1) = \frac{v \times (v - 1)}{2}$ 。为了使得答案尽可能小，我们应该尽量替换问号为那些出现次数较少的字母。

因此，我们可以使用优先队列（小根堆）来维护每个字母的出现次数，每次取出出现次数最少的字母，将其记录到数组 $t$ 中，然后将其出现次数加一，再放回优先队列中。最后，我们将数组 $t$ 排序，然后遍历字符串 $s$ ，将每个问号依次替换为数组 $t$ 中的字母即可。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func minimizeStringValue(s string) string {
	cnt := [26]int{}
	k := 0
	for _, c := range s {
		if c == '?' {
			k++
		} else {
			cnt[c-'a']++
		}
	}
	pq := hp{}
	for i, c := range cnt {
		heap.Push(&pq, pair{c, i})
	}
	t := make([]int, k)
	for i := 0; i < k; i++ {
		p := heap.Pop(&pq).(pair)
		t[i] = p.c
		p.v++
		heap.Push(&pq, p)
	}
	sort.Ints(t)
	cs := []byte(s)
	j := 0
	for i, c := range cs {
		if c == '?' {
			cs[i] = byte(t[j] + 'a')
			j++
		}
	}
	return string(cs)
}

type pair struct{ v, c int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v || h[i].v == h[j].v && h[i].c < h[j].c }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

力扣原题 · Doocs 题解来源

3085. 成为 K 特殊字符串需要删除的最少字符数

中等1 种解法

标签：贪心、哈希表、字符串、计数、排序

题目、示例与约束

给你一个字符串 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⁵
0 <= k <= 10⁵
word 仅由小写英文字母组成。

方法一：计数 + 枚举 · Go 实现

思考

任意两字符频次之差不超过 $k$ 。只能删字符， $n \leq 10^{5}$ ，字母仅 $26$ 种。

保留下来的频次落在某个区间 $[v, v + k]$ 。低于 $v$ 的字母整类删除，高于 $v + k$ 的删到 $v + k$ 。

枚举最小保留频次 $v$ ，对 $26$ 个计数求和式取最小。

我们可以先统计字符串中每个字符的出现次数，将所有次数放入数组 $n u m s$ 中，由于题目中字符串只包含小写字母，所以数组 $n u m s$ 的长度不会超过 $26$ 。

接下来，我们可以枚举在 $[0, . . n]$ 的范围内枚举 $K$ 特殊字符串中的字符最小频率 $v$ ，然后用一个函数 $f (v)$ 来计算将所有字符的频率调整为 $v$ 的最小删除次数，最后取所有 $f (v)$ 的最小值即为答案。

函数 $f (v)$ 的计算方法如下：

遍历数组 $n u m s$ 中的每个元素 $x$ ，如果 $x < v$ ，则说明我们需要将出现次数为 $x$ 的字符全部删除，删除次数为 $x$ ；如果 $x > v + k$ ，则说明我们需要将出现次数为 $x$ 的字符全部调整为 $v + k$ ，删除次数为 $x - v - k$ 。累加所有删除次数即为 $f (v)$ 的值。

时间复杂度 $O (n \times | Σ |)$ ，空间复杂度 $O (| Σ |)$ 。其中 $n$ 为字符串长度；而 $| Σ |$ 为字符集大小，本题中 $| Σ | = 26$ 。

func minimumDeletions(word string, k int) int {
	freq := [26]int{}
	for _, c := range word {
		freq[c-'a']++
	}
	nums := []int{}
	for _, v := range freq {
		if v > 0 {
			nums = append(nums, v)
		}
	}
	f := func(v int) int {
		ans := 0
		for _, x := range nums {
			if x < v {
				ans += x
			} else if x > v+k {
				ans += x - v - k
			}
		}
		return ans
	}
	ans := len(word)
	for i := 0; i <= len(word); i++ {
		ans = min(ans, f(i))
	}
	return ans
}

力扣原题 · Doocs 题解来源

3086. 拾起 K 个 1 需要的最少行动次数

困难1 种解法

标签：贪心、数组、前缀和、滑动窗口

题目、示例与约束

给你一个下标从 0 开始的二进制数组 nums，其长度为 n ；另给你一个 正整数 k 以及一个 非负整数 maxChanges 。

Alice 在玩一个游戏，游戏的目标是让 Alice 使用最少数量的行动次数从 nums 中拾起 k 个 1 。游戏开始时，Alice 可以选择数组 [0, n - 1] 范围内的任何索引 aliceIndex 站立。如果 nums[aliceIndex] == 1 ，Alice 会拾起一个 1 ，并且 nums[aliceIndex] 变成0（这不算作一次行动）。之后，Alice 可以执行 任意数量 的行动（包括零次），在每次行动中 Alice 必须恰好执行以下动作之一：

选择任意一个下标 j != aliceIndex 且满足 nums[j] == 0 ，然后将 nums[j] 设置为 1 。这个动作最多可以执行 maxChanges 次。
选择任意两个相邻的下标 x 和 y（|x - y| == 1）且满足 nums[x] == 1, nums[y] == 0 ，然后交换它们的值（将 nums[y] = 1 和 nums[x] = 0）。如果 y == aliceIndex，在这次行动后 Alice 拾起一个 1 ，并且 nums[y] 变成 0 。

返回 Alice 拾起恰好 k 个 1 所需的最少行动次数。

示例 1：

输入：nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1

输出：3

解释：如果游戏开始时 Alice 在 aliceIndex == 1 的位置上，按照以下步骤执行每个动作，他可以利用 3 次行动拾取 3 个 1 ：

游戏开始时 Alice 拾取了一个 1 ，nums[1] 变成了 0。此时 nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 j == 2 并执行第一种类型的动作。nums 变为 [1,0,1,0,0,1,1,0,0,1]
选择 x == 2 和 y == 1 ，并执行第二种类型的动作。nums 变为 [1,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 x == 0 和 y == 1 ，并执行第二种类型的动作。nums 变为 [0,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为 [0,0,0,0,0,1,1,0,0,1] 。

请注意，Alice 也可能执行其他的 3 次行动序列达成拾取 3 个 1 。

示例 2：

输入：nums = [0,0,0,0], k = 2, maxChanges = 3

输出：4

解释：如果游戏开始时 Alice 在 aliceIndex == 0 的位置上，按照以下步骤执行每个动作，他可以利用 4 次行动拾取 2 个 1 ：

选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于 y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。
再次选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
再次选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。

提示：

2 <= n <= 10⁵
0 <= nums[i] <= 1
1 <= k <= 10⁵
0 <= maxChanges <= 10⁵
maxChanges + sum(nums) >= k

方法一：贪心 + 前缀和 + 二分查找 · Go 实现

思考

在位置 $i$ 收集 $k$ 个 $1$ ，可用邻格一步拿走、用限额把 $0$ 变成邻格再拿走，或从更远处移来。 $n \leq 10^{5}$ 。

站立位置值得枚举。邻格与 $maxChanges$ 的用量是贪心确定的；更远的 $1$ 应按距离由近到远，其个数与代价可用前缀个数、前缀下标和在倍增区间上二分。

对每个 $i$ 先用自身与左右，再消耗限额，剩余用二分半径 $d$ 使两侧 $[i - d, i - 2] \cup [i + 2, i + d]$ 内的 $1$ 够用，并用前缀和计算移动步数。

我们考虑枚举 Alice 的站立位置 $i$ ，对于每个 $i$ ，我们按照如下的策略进行操作：

首先，如果位置 $i$ 的数字为 $1$ ，我们可以直接拾取一个 $1$ ，不需要行动次数。
然后，我们对 $i$ 的左右两侧位置的数字 $1$ 进行拾取，执行的是行动 $2$ ，即把位置 $i - 1$ 的 $1$ 移到位置 $i$ ，然后拾取；把位置 $i + 1$ 的 $1$ 移到位置 $i$ ，然后拾取。每拾取一个 $1$ ，需要 $1$ 次行动。
接下来，我们最大限度地将 $i - 1$ 或 $i + 1$ 上的 $0$ ，利用行动 $1$ ，将其置为 $1$ ，然后利用行动 $2$ ，将其移动到位置 $i$ ，拾取。直到拾取的 $1$ 的数量达到 $k$ 或者行动 $1$ 的次数达到 $maxChanges$ 。我们假设行动 $1$ 的次数为 $c$ ，那么总共需要 $2 c$ 次行动。
利用完行动 $1$ ，如果拾取的 $1$ 的数量还没有达到 $k$ ，我们需要继续考虑在 $[1, . . i - 2]$ 和 $[i + 2, . . n]$ 的区间内，进行行动 $2$ ，将 $1$ 移动到位置 $i$ ，拾取。我们可以使用二分查找来确定这个区间的大小，使得拾取的 $1$ 的数量达到 $k$ 。具体地，我们二分枚举一个区间的大小 $d$ ，然后在区间 $[i - d, . . i - 2]$ 和 $[i + 2, . . i + d]$ 内，进行行动 $2$ ，将 $1$ 移动到位置 $i$ ，拾取。如果拾取的 $1$ 的数量达到 $k$ ，我们就更新答案。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $nums$ 的长度。

func minimumMoves(nums []int, k int, maxChanges int) int64 {
	n := len(nums)
	cnt := make([]int, n+1)
	s := make([]int, n+1)

	for i := 1; i <= n; i++ {
		cnt[i] = cnt[i-1] + nums[i-1]
		s[i] = s[i-1] + i*nums[i-1]
	}

	ans := math.MaxInt64

	for i := 1; i <= n; i++ {
		t := 0
		need := k - nums[i-1]

		for _, j := range []int{i - 1, i + 1} {
			if need > 0 && 1 <= j && j <= n && nums[j-1] == 1 {
				need--
				t++
			}
		}

		c := min(need, maxChanges)
		need -= c
		t += c * 2

		if need <= 0 {
			ans = min(ans, t)
			continue
		}

		l, r := 2, max(i-1, n-i)

		for l <= r {
			mid := (l + r) >> 1
			l1, r1 := max(1, i-mid), max(0, i-2)
			l2, r2 := min(n+1, i+2), min(n, i+mid)

			c1 := cnt[r1] - cnt[l1-1]
			c2 := cnt[r2] - cnt[l2-1]

			if c1+c2 >= need {
				t1 := c1*i - (s[r1] - s[l1-1])
				t2 := s[r2] - s[l2-1] - c2*i
				ans = min(ans, t+t1+t2)
				r = mid - 1
			} else {
				l = mid + 1
			}
		}
	}

	return int64(ans)
}

力扣原题 · Doocs 题解来源

3088. 使字符串反回文 🔒

困难1 种解法

标签：贪心、字符串、计数排序、排序

题目、示例与约束

我们称一个长度为偶数的字符串 s 为 反回文 的，如果对于每一个下标 0 <= i < n ，s[i] != s[n - i - 1]。

给定一个字符串 s，你需要进行任意次（包括 0）操作使 s 成为 反回文。

在一次操作中，你可以选择 s 中的两个字符并且交换它们。

返回结果字符串。如果有多个字符串符合条件，返回字典序最小的那个。如果它不能成为一个反回文，返回 "-1"。

示例 1：

输入：s = "abca"

输出："aabc"

解释：

"aabc" 是一个反回文字符串，因为 s[0] != s[3] 并且 s[1] != s[2]。同时，它也是 "abca" 的一个重排。

示例 2:

输入：s = "abba"

输出："aabb"

解释：

"aabb" 是一个反回文字符串，因为 s[0] != s[3] 并且 s[1] != s[2]。同时，它也是 "abba" 的一个重排。

示例 3:

输入：s = "cccd"

输出："-1"

解释：

你可以发现无论你如何重排 "cccd" 的字符，都有 s[0] == s[3] 或 s[1] == s[2]。所以它不能形成一个反回文字符串。

提示：

2 <= s.length <= 10⁵
s.length % 2 == 0
s 只包含小写英文字母。

方法一：贪心 + 排序 · Go 实现

思考

反回文要求 $s [i] \neq s [n - 1 - i]$ ，并在所有可达串中取字典序最小。 $n$ 为偶数且 $\leq 10^{5}$ 。

字典序最小先把字符排序。若中缝两侧已经不同，则整串对位也不同；若中缝相同，说明后半有一段与前半对称冲突，需把后半中更靠后的不同字母换到中缝一带。

排序后若 $s [m] = s [m - 1]$ ，从后半找到下一段不同字母，与中缝起的对称位置交换；换尽仍冲突则无解。

题目要求我们将字符串 $s$ 变成字典序最小的反回文字符串，我们不妨先对字符串 $s$ 进行排序。

接下来，我们只需要比较中间的两个字符 $s [m]$ 和 $s [m - 1]$ 是否相等，如果相等，我们就在后半部分找到第一个不等于 $s [m]$ 的字符 $s [i]$ ，用一个指针 $j$ 指向 $m$ ，然后交换 $s [i]$ 和 $s [j]$ 。如果找不到这样的字符 $s [i]$ ，说明字符串 $s$ 无法变成反回文字符串，返回 "1"。否则，执行交换操作，并向右移动 $i$ 和 $j$ ，比较 $s [j]$ 和 $s [n - j - 1]$ 是否相等，如果相等，继续执行交换操作，直到 $i$ 超出字符串长度。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是字符串 $s$ 的长度。

func makeAntiPalindrome(s string) string {
	cs := []byte(s)
	sort.Slice(cs, func(i, j int) bool { return cs[i] < cs[j] })
	n := len(cs)
	m := n / 2
	if cs[m] == cs[m-1] {
		i := m
		for i < n && cs[i] == cs[i-1] {
			i++
		}
		for j := m; j < n && cs[j] == cs[n-j-1]; i, j = i+1, j+1 {
			if i >= n {
				return "-1"
			}
			cs[i], cs[j] = cs[j], cs[i]
		}
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

3091. 执行操作使数据元素之和大于等于 K

中等1 种解法

标签：贪心、数学、枚举

题目、示例与约束

给你一个正整数 k 。最初，你有一个数组 nums = [1] 。

你可以对数组执行以下任意操作任意次数（可能为零）：

选择数组中的任何一个元素，然后将它的值增加 1 。
复制数组中的任何一个元素，然后将它附加到数组的末尾。

返回使得最终数组元素之和大于或等于 k 所需的最少操作次数。

示例 1：

输入：k = 11

输出：5

解释：

可以对数组 nums = [1] 执行以下操作：

将元素的值增加 1 三次。结果数组为 nums = [4] 。
复制元素两次。结果数组为 nums = [4,4,4] 。

最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。
执行的总操作次数为 3 + 2 = 5 。

示例 2：

输入：k = 1

输出：0

解释：

原始数组的和已经大于等于 1 ，因此不需要执行操作。

提示：

1 <= k <= 10⁵

方法一：枚举 · Go 实现

思考

数组从 $[1]$ 开始，可把某个数加一，或把某个数追加一份。目标是元素和 $\geq k$ ， $k \leq 10^{5}$ 。

追加是复制当前值，因此应先把某一个数加到 $x$ ，再复制 $x$ 。操作次数为 $(x - 1) + (⌈ k / x ⌉ - 1)$ 。

枚举加一次数 $a$ （即 $x = a + 1$ ），计算对应复制次数并取 $a + b$ 最小。

我们应该将复制的操作（即操作 $2$ ）放后面，这样可以减少操作次数。

因此，我们在 $[0, k]$ 的范围内枚举操作 $1$ 的次数 $a$ ，那么操作 $2$ 的次数 $b = ⌈ \frac{k}{a + 1} ⌉ - 1$ 。取最小的 $a + b$ 即可。

时间复杂度 $O (k)$ ，其中 $k$ 为输入的正整数 $k$ 。空间复杂度 $O (1)$ 。

func minOperations(k int) int {
	ans := k
	for a := 0; a < k; a++ {
		x := a + 1
		b := (k+x-1)/x - 1
		ans = min(ans, a+b)
	}
	return ans
}

力扣原题 · Doocs 题解来源

3106. 满足距离约束且字典序最小的字符串

中等1 种解法

标签：贪心、字符串

题目、示例与约束

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

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

字符 'a' 到 'z' 按循环顺序排列，对于区间 [0, n - 1] 中的 i ，计算所有「 s₁[i] 和 s₂[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 只包含小写英文字母。

方法一：枚举 · Go 实现

思考

每次可将一个字符沿字母环移动，总代价不超过 $k$ ，目标是字典序最小。若对剩余代价做全局搜索，状态空间随位置与 $k$ 膨胀。

字典序由左到右决定，贪心地把左侧字符尽量改小不会妨碍右侧。单个字符改到更小字母的最小环距离为 $min (c_{1} - c_{2}, 26 - (c_{1} - c_{2}))$ 。

因此从左到右枚举每个位置，在小于当前字符的字母中找代价不超过剩余 $k$ 的最小者，扣去代价后继续。字母表大小为 $26$ ，枚举即可。

我们可以遍历字符串 $s$ 的每个位置，对于每个位置，我们枚举所有小于当前字符的字符，计算改变到这个字符的代价 $d$ ，如果 $d \leq k$ ，我们就将当前位置的字符改为这个字符，并将 $k$ 减去 $d$ ，然后结束枚举，继续遍历下一个位置。

遍历结束后，我们就得到了一个满足条件的字符串。

时间复杂度 $O (n \times | Σ |)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是字符串 $s$ 的长度；而 $| Σ |$ 是字符集的大小，本题中 $| Σ | \leq 26$ 。

func getSmallestString(s string, k int) string {
	cs := []byte(s)
	for i, c1 := range cs {
		for c2 := byte('a'); c2 < c1; c2++ {
			d := int(min(c1-c2, 26-c1+c2))
			if d <= k {
				cs[i] = c2
				k -= d
				break
			}
		}
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

LeetCode Go · 贪心（10） ​

2864. 最大二进制奇数 ​

2868. 单词游戏 🔒 ​

2870. 使数组为空的最少操作次数 ​

2871. 将数组分割成最多数目的子数组 ​

2895. 最小处理时间 ​

2897. 对数组执行操作使平方和最大 ​

2910. 合法分组的最少组数 ​

2918. 数组的最小相等和 ​

2931. 购买物品的最大开销 ​

2938. 区分黑球与白球 ​

2939. 最大异或乘积 ​

2952. 需要添加的硬币的最小数量 ​

2966. 划分数组并满足最大差限制 ​

2967. 使数组成为等数数组的最小代价 ​

2971. 找到最大周长的多边形 ​

3002. 移除后集合的最多元素数 ​

3012. 通过操作使数组长度最小 ​

3014. 输入单词需要的最少按键次数 I ​

3016. 输入单词需要的最少按键次数 II ​

3022. 给定操作次数内使剩余元素的或值最小 ​

3035. 回文字符串的最大数量 ​

3049. 标记所有下标的最早秒数 II ​

3074. 重新分装苹果 ​

3075. 幸福值最大化的选择方案 ​

3081. 替换字符串中的问号使分数最小 ​

3085. 成为 K 特殊字符串需要删除的最少字符数 ​

3086. 拾起 K 个 1 需要的最少行动次数 ​

3088. 使字符串反回文 🔒 ​

3091. 执行操作使数据元素之和大于等于 K ​

3106. 满足距离约束且字典序最小的字符串 ​

继续阅读

LeetCode Go · 贪心（10）

2864. 最大二进制奇数

2868. 单词游戏 🔒

2870. 使数组为空的最少操作次数

2871. 将数组分割成最多数目的子数组

2895. 最小处理时间

2897. 对数组执行操作使平方和最大

2910. 合法分组的最少组数

2918. 数组的最小相等和

2931. 购买物品的最大开销

2938. 区分黑球与白球

2939. 最大异或乘积

2952. 需要添加的硬币的最小数量

2966. 划分数组并满足最大差限制

2967. 使数组成为等数数组的最小代价

2971. 找到最大周长的多边形

3002. 移除后集合的最多元素数

3012. 通过操作使数组长度最小

3014. 输入单词需要的最少按键次数 I

3016. 输入单词需要的最少按键次数 II

3022. 给定操作次数内使剩余元素的或值最小

3035. 回文字符串的最大数量

3049. 标记所有下标的最早秒数 II

3074. 重新分装苹果

3075. 幸福值最大化的选择方案

3081. 替换字符串中的问号使分数最小

3085. 成为 K 特殊字符串需要删除的最少字符数

3086. 拾起 K 个 1 需要的最少行动次数

3088. 使字符串反回文 🔒

3091. 执行操作使数据元素之和大于等于 K

3106. 满足距离约束且字典序最小的字符串