LeetCode Go · 贪心（6）

返回题库与筛选 · 收录范围与使用说明

来源与许可

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

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

1899. 合并若干三元组以形成目标三元组

中等1 种解法

标签：贪心、数组

题目、示例与约束

三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ，其中 triplets[i] = [ai, bi, ci] 表示第 i 个 三元组 。同时，给你一个整数数组 target = [x, y, z] ，表示你想要得到的 三元组 。

为了得到 target ，你需要对 triplets 执行下面的操作 任意次（可能 零 次）：

• 选出两个下标（下标 从 0 开始 计数）i 和 j（i != j），并 更新 triplets[j] 为 [max(ai, aj), max(bi, bj), max(ci, cj)] 。
  • 例如，triplets[i] = [2, 5, 3] 且 triplets[j] = [1, 7, 5]，triplets[j] 将会更新为 [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5] 。

如果通过以上操作我们可以使得目标 三元组 target 成为 triplets 的一个 元素 ，则返回 true ；否则，返回 false 。

 

示例 1：

输入：triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
输出：true
解释：执行下述操作：
- 选择第一个和最后一个三元组 [[2,5,3],[1,8,4],[1,7,5]] 。更新最后一个三元组为 [max(2,1), max(5,7), max(3,5)] = [2,7,5] 。triplets = [[2,5,3],[1,8,4],[2,7,5]]
目标三元组 [2,7,5] 现在是 triplets 的一个元素。

示例 2：

输入：triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
输出：true
解释：目标三元组 [2,5,8] 已经是 triplets 的一个元素。

示例 3：

输入：triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
输出：true
解释：执行下述操作：
- 选择第一个和第三个三元组 [[2,5,3],[2,3,4],[1,2,5],[5,2,3]] 。更新第三个三元组为 [max(2,1), max(5,2), max(3,5)] = [2,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
- 选择第三个和第四个三元组 [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。更新第四个三元组为 [max(2,5), max(5,2), max(5,3)] = [5,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]] 。
目标三元组 [5,5,5] 现在是 triplets 的一个元素。

示例 4：

输入：triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
输出：false
解释：无法得到 [3,2,5] ，因为 triplets 不含 2 。

 

提示：

• 1 <= triplets.length <= 105
• triplets[i].length == target.length == 3
• 1 <= ai, bi, ci, x, y, z <= 1000

方法一：贪心 · Go 实现

思考

合并把两个三元组各维取 $max$。一旦某维已经超过目标，该三元组不能再参与，否则无法降下来。

只保留三维都不超过 $target$ 的三元组，对它们各维取 $max$。若结果恰为 $target$，说明每一维都有来源，可以合并得到。

我们记 $\mathit{\text{target}}=[x,y,z]$，我们需要判断是否存在三元组 $[a,b,c]$ 使得 $a\le x,b\le y,c\le z$。

我们可以将所有的三元组分为两类：

1. 满足 $a\le x,b\le y,c\le z$ 的三元组。
2. 不满足 $a\le x,b\le y,c\le z$ 的三元组。

对于第一类三元组，我们可以将它们的 $a,b,c$ 分别取最大值，得到一个新的三元组 $[d,e,f]$。

对于第二类三元组，我们可以忽略它们，因为它们无法帮助我们得到目标三元组。

最后，我们只需要判断 $[d,e,f]$ 是否等于 $\mathit{\text{target}}$ 即可。如果等于，返回 $\mathit{\text{true}}$，否则返回 $\mathit{\text{false}}$。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\mathit{\text{triplets}}$ 的长度。空间复杂度 $O(1)$。

func mergeTriplets(triplets [][]int, target []int) bool {
	x, y, z := target[0], target[1], target[2]
	d, e, f := 0, 0, 0
	for _, t := range triplets {
		a, b, c := t[0], t[1], t[2]
		if a <= x && b <= y && c <= z {
			d = max(d, a)
			e = max(e, b)
			f = max(f, c)
		}
	}
	return d == x && e == y && f == z
}

力扣原题 · Doocs 题解来源

1903. 字符串中的最大奇数

简单1 种解法

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

题目、示例与约束

给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有 非空子字符串 中找出 值最大的奇数 ，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 "" 。

子字符串 是字符串中的一个连续的字符序列。

 

示例 1：

输入：num = "52"
输出："5"
解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。

示例 2：

输入：num = "4206"
输出：""
解释：在 "4206" 中不存在奇数。

示例 3：

输入：num = "35427"
输出："35427"
解释："35427" 本身就是一个奇数。

 

提示：

• 1 <= num.length <= 105
• num 仅由数字组成且不含前导零

方法一：逆序遍历 · Go 实现

思考

数值上最大的奇子串必是原串的某个前缀，且该前缀应以奇数结尾。 $n\le {10}^5$，不能把所有前缀转成整数再比较。

从右向左扫描即可：第一个奇数数字使以其为结尾的前缀同时满足“奇数”与“最长”，因而也最大。

若不存在奇数位，则答案为空串。整段扫描一次，额外空间为常数。

我们可以从后往前遍历字符串，找到第一个奇数，然后返回从开头到该奇数的子字符串即可。如果不存在奇数，则返回空字符串。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $num$ 的长度。忽略答案字符串的空间消耗，空间复杂度 $O(1)$。

func largestOddNumber(num string) string {
	for i := len(num) - 1; i >= 0; i-- {
		c := num[i] - '0'
		if (c & 1) == 1 {
			return num[:i+1]
		}
	}
	return ""
}

力扣原题 · Doocs 题解来源

1921. 消灭怪物的最大数量

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给定一个 下标从 0 开始 且大小为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：千米）。

怪物以 恒定 的速度走向城市。每个怪物的速度都以一个长度为 n 的整数数组 speed 表示，其中 speed[i] 是第 i 个怪物的速度（单位：千米/分）。

你有一种武器，一旦充满电，就可以消灭 一个 怪物。但是，武器需要 一分钟 才能充电。武器在游戏开始时是充满电的状态，怪物从 第 0 分钟 时开始移动。

一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 恰好 在某一分钟开始时到达城市（距离表示为0），这也会被视为 输掉 游戏，在你可以使用武器之前，游戏就会结束。

返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回  n 。

 

示例 1：

输入：dist = [1,3,4], speed = [1,1,1]
输出：3
解释：
第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,2,3]，你消灭了第二个怪物。
第 3 分钟开始时，怪物的距离是 [X,X,2]，你消灭了第三个怪物。
所有 3 个怪物都可以被消灭。

示例 2：

输入：dist = [1,1,2,3], speed = [1,1,1,1]
输出：1
解释：
第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,1,2]，所以你输掉了游戏。
你只能消灭 1 个怪物。

示例 3：

输入：dist = [3,2,4], speed = [5,3,2]
输出：1
解释：
第 0 分钟开始时，怪物的距离是 [3,2,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,2]，你输掉了游戏。 
你只能消灭 1 个怪物。

 

提示：

• n == dist.length == speed.length
• 1 <= n <= 105
• 1 <= dist[i], speed[i] <= 105

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

思考

武器每分钟只能消灭一只，若按到达时间任意穿插，需要比较的顺序很多。每只怪物的最晚击杀时刻由距离与速度唯一确定。

第 $i$ 分钟开始时已用掉 $i$ 次射击，因此应按最晚可击杀时间升序消灭：若排序后第 $i$ 只的时限小于 $i$，则无法再多杀。

$\lfloor (d-1)/s\rfloor$ 给出「到达前最后一分钟」，排序后扫描即可。

我们用 $\mathit{\text{times}}$ 数组记录每个怪物最晚可被消灭的时间。对于第 $i$ 个怪物，最晚可被消灭的时间满足：

$$\mathit{\text{times}}[i]=\lfloor \frac{\mathit{\text{dist}}[i]-1}{\mathit{\text{speed}}[i]}\rfloor$$

接下来，我们对 $\mathit{\text{times}}$ 数组升序排列。

然后遍历 $\mathit{\text{times}}$ 数组，对于第 $i$ 个怪物，如果 $\mathit{\text{times}}[i]\ge i$，说明第 $i$ 个怪物可以被消灭，否则说明第 $i$ 个怪物无法被消灭，直接返回 $i$ 即可。

若所有怪物都可以被消灭，则返回 $n$。

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

func eliminateMaximum(dist []int, speed []int) int {
	n := len(dist)
	times := make([]int, n)
	for i, d := range dist {
		times[i] = (d - 1) / speed[i]
	}
	sort.Ints(times)
	for i, t := range times {
		if t < i {
			return i
		}
	}
	return n
}

力扣原题 · Doocs 题解来源

1927. 求和游戏

中等1 种解法

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

题目、示例与约束

Alice 和 Bob 玩一个游戏，两人轮流行动，Alice 先手 。

给你一个 偶数长度 的字符串 num ，每一个字符为数字字符或者 '?' 。每一次操作中，如果 num 中至少有一个 '?' ，那么玩家可以执行以下操作：

1. 选择一个下标 i 满足 num[i] == '?' 。
2. 将 num[i] 用 '0' 到 '9' 之间的一个数字字符替代。

当 num 中没有 '?' 时，游戏结束。

Bob 获胜的条件是 num 中前一半数字的和 等于 后一半数字的和。Alice 获胜的条件是前一半的和与后一半的和 不相等 。

• 比方说，游戏结束时 num = "243801" ，那么 Bob 获胜，因为 2+4+3 = 8+0+1 。如果游戏结束时 num = "243803" ，那么 Alice 获胜，因为 2+4+3 != 8+0+3 。

在 Alice 和 Bob 都采取 最优 策略的前提下，如果 Alice 获胜，请返回 true ，如果 Bob 获胜，请返回 false 。

 

示例 1：

输入：num = "5023"
输出：false
解释：num 中没有 '?' ，没法进行任何操作。
前一半的和等于后一半的和：5 + 0 = 2 + 3 。

示例 2：

输入：num = "25??"
输出：true
解释：Alice 可以将两个 '?' 中的一个替换为 '9' ，Bob 无论如何都无法使前一半的和等于后一半的和。

示例 3：

输入：num = "?3295???"
输出：false
解释：Bob 总是能赢。一种可能的结果是：
- Alice 将第一个 '?' 用 '9' 替换。num = "93295???" 。
- Bob 将后面一半中的一个 '?' 替换为 '9' 。num = "932959??" 。
- Alice 将后面一半中的一个 '?' 替换为 '2' 。num = "9329592?" 。
- Bob 将后面一半中最后一个 '?' 替换为 '7' 。num = "93295927" 。
Bob 获胜，因为 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7 。

 

提示：

• 2 <= num.length <= 105
• num.length 是 偶数 。
• num 只包含数字字符和 '?' 。

方法一：分类讨论 · Go 实现

思考

双方交替填 ?，Alice 要使左右半和不同。完整博弈树随问号个数指数增长，但最优策略可归结为问号奇偶与两侧已有数字之差。

问号总数为奇数时 Alice 先手多填一次，必能使两侧不等。偶数时双方总能把剩余问号对冲到同一侧，Bob 能逼平当且仅当已有和之差恰好等于 $9$ 乘以两侧问号数之差的一半。

因此扫描左右半的问号个数与数字和，按上述等式判断即可，无需模拟对局。

如果 '?' 的个数为奇数，那么 Alice 一定会获胜，因为她可以选择将最后一个 '?' 替换为任何一个数字，使得前一半的和与后一半的和不相等。

如果 '?' 的个数为偶数，Alice 为了使得前一半的和与后一半的和不相等，那么会选择在当前和较大的一半数字中放置 $9$，在当前和较小的一半数字中放置 $0$，而 Bob 为了使得前后两半的和相等，那么会选择在 Alice 替换数字的另一半放置一个与 Alice 替换数字相同的数字。

因此，最终会使得剩下的所有偶数个 '?' 集中在其中一半。假设当前两半的数字差值为 $d$。

我们先考虑，如果剩下两个 '?'，差值为 $x$，此时：

• 如果 $x<9$，那么 Alice 必胜，因为 Alice 可以将其中一个 '?' 替换为 $9$，使得前一半的和与后一半的和不相等；
• 如果 $x>9$，那么 Alice 必胜，因为 Alice 可以将其中一个 '?' 替换为 $0$，使得前一半的和与后一半的和不相等；
• 如果 $x=9$，那么 Bob 必胜，假设 Alice 替换的数字为 $a$，那么 Bob 可以将另一个 '?' 替换为 $9-a$，使得前后两半的和相等。

因此，如果两半数字差值为 $d=\frac{9\times cnt}{2}$，其中 $cnt$ 为剩下的 '?' 的个数，那么 Bob 必胜，否则 Alice 必胜。

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

func sumGame(num string) bool {
	n := len(num)
	var cnt1, cnt2, s1, s2 int
	for i := 0; i < n/2; i++ {
		if num[i] == '?' {
			cnt1++
		} else {
			s1 += int(num[i] - '0')
		}
	}
	for i := n / 2; i < n; i++ {
		if num[i] == '?' {
			cnt2++
		} else {
			s2 += int(num[i] - '0')
		}
	}
	return (cnt1+cnt2)%2 == 1 || s1-s2 != (cnt2-cnt1)*9/2
}

力扣原题 · Doocs 题解来源

1936. 新增的最少台阶数

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你一个 严格递增 的整数数组 rungs ，用于表示梯子上每一台阶的 高度 。当前你正站在高度为 0 的地板上，并打算爬到最后一个台阶。

另给你一个整数 dist 。每次移动中，你可以到达下一个距离你当前位置（地板或台阶）不超过 dist 高度的台阶。当然，你也可以在任何正 整数 高度处插入尚不存在的新台阶。

返回爬到最后一阶时必须添加到梯子上的 最少 台阶数。

 

示例 1：

输入：rungs = [1,3,5,10], dist = 2
输出：2
解释：
现在无法到达最后一阶。
在高度为 7 和 8 的位置增设新的台阶，以爬上梯子。 
梯子在高度为 [1,3,5,7,8,10] 的位置上有台阶。

示例 2：

输入：rungs = [3,6,8,10], dist = 3
输出：0
解释：
这个梯子无需增设新台阶也可以爬上去。

示例 3：

输入：rungs = [3,4,6,7], dist = 2
输出：1
解释：
现在无法从地板到达梯子的第一阶。 
在高度为 1 的位置增设新的台阶，以爬上梯子。 
梯子在高度为 [1,3,4,6,7] 的位置上有台阶。

示例 4：

输入：rungs = [5], dist = 10
输出：0
解释：这个梯子无需增设新台阶也可以爬上去。

 

提示：

• 1 <= rungs.length <= 105
• 1 <= rungs[i] <= 109
• 1 <= dist <= 109
• rungs 严格递增

方法一：贪心 + 模拟 · Go 实现

思考

相邻两档高度差超过 $\mathit{\text{dist}}$ 时必须插入新档，且新档也受 $\mathit{\text{dist}}$ 限制。 $n\le {10}^5$、高度达 ${10}^9$，不能逐步模拟每一档。

从高度 $a$ 到 $b$ 最少插入 $\lfloor (b-a-1)/\mathit{\text{dist}}\rfloor$ 档。在起点补 $0$ 后对相邻高度求和即可。

贪心把插入位置尽量拉满 $\mathit{\text{dist}}$，不会比该公式更优。

根据题目描述，我们知道，每一次计划爬上一个新的台阶，都需要满足新的台阶的高度与当前所在位置的高度之差不超过 dist，否则，我们需要贪心地在距离当前位置 $dist$ 的地方插入一个新的台阶，爬上一个新的台阶，一共需要插入的台阶数为 $\lfloor \frac{b-a-1}{dist}\rfloor$，其中 $a$ 和 $b$ 分别为当前位置和新台阶的高度。那么答案即为所有插入的台阶数之和。

时间复杂度 $O(n)$，其中 $n$ 为 rungs 的长度。空间复杂度 $O(1)$。

func addRungs(rungs []int, dist int) (ans int) {
	prev := 0
	for _, x := range rungs {
		ans += (x - prev - 1) / dist
		prev = x
	}
	return
}

力扣原题 · Doocs 题解来源

1946. 子字符串突变后可能得到的最大整数

中等1 种解法

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

题目、示例与约束

给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且 下标从 0  开始 的整数数组 change ，该数组将 0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。

你可以选择 突变  num 的任一子字符串。突变 子字符串意味着将每位数字 num[i] 替换为该数字在 change 中的映射（也就是说，将 num[i] 替换为 change[num[i]]）。

请你找出在对 num 的任一子字符串执行突变操作（也可以不执行）后，可能得到的 最大整数 ，并用字符串表示返回。

子字符串 是字符串中的一个连续序列。

 

示例 1：

输入：num = "132", change = [9,8,5,0,3,6,4,2,6,8]
输出："832"
解释：替换子字符串 "1"：
- 1 映射为 change[1] = 8 。
因此 "132" 变为 "832" 。
"832" 是可以构造的最大整数，所以返回它的字符串表示。

示例 2：

输入：num = "021", change = [9,4,3,5,7,2,1,9,0,6]
输出："934"
解释：替换子字符串 "021"：
- 0 映射为 change[0] = 9 。
- 2 映射为 change[2] = 3 。
- 1 映射为 change[1] = 4 。
因此，"021" 变为 "934" 。
"934" 是可以构造的最大整数，所以返回它的字符串表示。 

示例 3：

输入：num = "5", change = [1,4,7,5,3,2,5,6,9,4]
输出："5"
解释："5" 已经是可以构造的最大整数，所以返回它的字符串表示。

 

提示：

• 1 <= num.length <= 105
• num 仅由数字 0-9 组成
• change.length == 10
• 0 <= change[d] <= 9

方法一：贪心 · Go 实现

思考

只能对一段连续子串做映射，且要得到字典序最大。从高位开始，一旦开始替换就应持续到映射不再变大。

尚未替换时，映射更小或相等则跳过；映射更大则开始替换。已经替换后，映射更小必须立刻停止，相等可继续。

一次从左到右扫描即可决定唯一最优区间。

根据题目描述，我们可以从字符串的高位开始，贪心的进行连续的替换操作，直到遇到一个比当前位数字小的数字为止。

我们先将字符串 $\mathit{\text{num}}$ 转换为字符数组 $\mathit{\text{s}}$，用一个变量 $\mathit{\text{changed}}$ 记录是否已经发生过变化，初始时 $\mathit{\text{changed}}=\text{false}$。

然后我们遍历字符数组 $\mathit{\text{s}}$，对于每个字符 $\mathit{\text{c}}$，我们将其转换为数字 $\mathit{\text{d}}=\text{change}[\text{int}(\mathit{\text{c}})]$，如果已经发生过变化且 $\mathit{\text{d}}<\mathit{\text{c}}$，则说明我们不能再继续变化，直接退出循环；否则，如果 $\mathit{\text{d}}>\mathit{\text{c}}$，则说明我们可以将 $\mathit{\text{c}}$ 替换为 $\mathit{\text{d}}$，此时我们将 $\mathit{\text{changed}}=\text{true}$，并将 $\mathit{\text{s}}[i]$ 替换为 $\mathit{\text{d}}$。

最后我们将字符数组 $\mathit{\text{s}}$ 转换为字符串并返回即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $\mathit{\text{num}}$ 的长度。

func maximumNumber(num string, change []int) string {
	s := []byte(num)
	changed := false
	for i, c := range num {
		d := byte('0' + change[c-'0'])
		if changed && d < s[i] {
			break
		}
		if d > s[i] {
			s[i] = d
			changed = true
		}
	}
	return string(s)
}

力扣原题 · Doocs 题解来源

1953. 你可以工作的最大周数

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你 n 个项目，编号从 0 到 n - 1 。同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。

你可以按下面两个规则参与项目中的工作：

• 每周，你将会完成 某一个 项目中的 恰好一个 阶段任务。你每周都 必须 工作。
• 在 连续的 两周中，你 不能 参与并完成同一个项目中的两个阶段任务。

一旦所有项目中的全部阶段任务都完成，或者执行仅剩的一个阶段任务将会导致你违反上面的规则，你将 停止工作。注意，由于这些条件的限制，你可能无法完成所有阶段任务。

返回在不违反上面规则的情况下你 最多 能工作多少周。

 

示例 1：

输入：milestones = [1,2,3]
输出：6
解释：一种可能的情形是：
​​​​- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 2 中的一个阶段任务。
- 第 3 周，你参与并完成项目 1 中的一个阶段任务。
- 第 4 周，你参与并完成项目 2 中的一个阶段任务。
- 第 5 周，你参与并完成项目 1 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
总周数是 6 。

示例 2：

输入：milestones = [5,2,1]
输出：7
解释：一种可能的情形是：
- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 1 中的一个阶段任务。
- 第 3 周，你参与并完成项目 0 中的一个阶段任务。
- 第 4 周，你参与并完成项目 1 中的一个阶段任务。
- 第 5 周，你参与并完成项目 0 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
- 第 7 周，你参与并完成项目 0 中的一个阶段任务。
总周数是 7 。
注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。
因此，项目 0 中会有一个阶段任务维持未完成状态。

 

提示：

• n == milestones.length
• 1 <= n <= 105
• 1 <= milestones[i] <= 109

方法一：贪心 · Go 实现

思考

相邻周不能做同一项目。若某一项目阶段数超过其余之和加一，多出的部分永远插不进去。

记总和 $s$、最大 $mx$、其余 $rest=s-mx$。若 $mx>rest+1$，最多完成 $2\cdot rest+1$ 周；否则可以做完全部 $s$ 周。

一次求最大与求和即可，无需模拟周进度。

我们考虑什么情况下不能完成所有阶段任务。如果存在一个项目 $i$，它的阶段任务数大于其余所有项目的阶段任务数之和再加 $1$，那么就不能完成所有阶段任务。否则，我们一定可以通过不同项目之间来回穿插的方式完成所有阶段任务。

我们记所有项目的阶段任务数之和为 $s$，最大的阶段任务数为 $mx$，那么其余所有项目的阶段任务数之和为 $rest=s-mx$。

如果 $mx>rest+1$，那么就不能完成所有阶段任务，最多只能完成 $rest\times 2+1$ 个阶段任务。否则，我们可以完成所有阶段任务，数量为 $s$。

时间复杂度 $O(n)$，其中 $n$ 为项目数。空间复杂度 $O(1)$。

func numberOfWeeks(milestones []int) int64 {
	mx := slices.Max(milestones)
	s := 0
	for _, x := range milestones {
		s += x
	}
	rest := s - mx
	if mx > rest+1 {
		return int64(rest*2 + 1)
	}
	return int64(s)
}

力扣原题 · Doocs 题解来源

1962. 移除石子使总数最小

中等1 种解法

标签：贪心、数组、堆（优先队列）

题目、示例与约束

给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：

• 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。

注意：你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后，剩下石子的 最小 总数。

floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。

 

示例 1：

输入：piles = [5,4,9], k = 2
输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。
剩下石子的总数为 12 。

示例 2：

输入：piles = [4,3,6,7], k = 3
输出：12
解释：可能的执行情景如下：
- 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。
- 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。
- 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。
剩下石子的总数为 12 。

 

提示：

• 1 <= piles.length <= 105
• 1 <= piles[i] <= 104
• 1 <= k <= 105

方法一：贪心 + 优先队列（大根堆） · Go 实现

思考

每次把某一堆减半向下取整，要让剩余总和最小，应总是操作当前最大堆。 $k$ 次选择用大根堆维护。

堆内存堆石数的相反数，每次把堆顶替换为减半后的值。 $k$ 次后求和取负。

根据题目描述，为了使得剩下的石子总数最小，我们需要尽可能多地移除石子堆中的石子。因此，每次应该选择数量最多的石子堆进行移除。

我们创建一个优先队列（大根堆） $pq$，用于存储石子堆的数量。初始时，将所有石子堆的数量加入优先队列。

接下来，我们进行 $k$ 次操作。在每一次操作中，我们取出优先队列的堆顶元素 $x$，将 $x$ 减半后重新加入优先队列。

在进行了 $k$ 次操作后，优先队列中所有元素的和即为答案。

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

func minStoneSum(piles []int, k int) (ans int) {
	pq := &hp{piles}
	heap.Init(pq)
	for ; k > 0; k-- {
		x := pq.pop()
		pq.push(x - x/2)
	}
	for pq.Len() > 0 {
		ans += pq.pop()
	}
	return
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
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
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int   { return heap.Pop(h).(int) }

力扣原题 · Doocs 题解来源

1963. 使字符串平衡的最小交换次数

中等1 种解法

标签：栈、贪心、双指针、字符串、括号序列

题目、示例与约束

给你一个字符串 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 <= 106
• n 为偶数
• s[i] 为'[' 或 ']'
• 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

方法一：贪心 · Go 实现

思考

括号可任意交换，不必邻接。扫描匹配后，剩余形态必为若干 ] 后接若干 [。

未匹配左括号个数为 $x$ 时，每次交换两端可消掉两个，故次数为 $\lfloor (x+1)/2\rfloor$。一遍计数即可。

我们用一个变量 $x$ 记录当前未匹配的左括号的数量，遍历字符串 $s$，对于每个字符 $c$：

• 如果 $c$ 是左括号，那么 $x$ 加一；
• 如果 $c$ 是右括号，那么我们需要判断 $x$ 是否大于零，如果大于零，那么将当前右括号与左侧最近的一个未匹配的左括号匹配，即 $x$ 减一。

遍历结束后，得到的一定是形如 "]]]...[[[..."的字符串，我们再贪心地每次将两端的括号交换，这样一次可以消去 $2$ 个不匹配的左括号。因此，一共需要交换的次数为 $\lfloor \frac{x+1}{2}\rfloor$。

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

func minSwaps(s string) int {
	x := 0
	for _, c := range s {
		if c == '[' {
			x++
		} else if x > 0 {
			x--
		}
	}
	return (x + 1) / 2
}

力扣原题 · Doocs 题解来源

1968. 构造元素不等于两相邻元素平均值的数组

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个 下标从 0 开始 的数组 nums ，数组由若干 互不相同的 整数组成。你打算重新排列数组中的元素以满足：重排后，数组中的每个元素都 不等于 其两侧相邻元素的 平均值 。

更公式化的说法是，重新排列的数组应当满足这一属性：对于范围 1 <= i < nums.length - 1 中的每个 i ，(nums[i-1] + nums[i+1]) / 2 不等于 nums[i] 均成立 。

返回满足题意的任一重排结果。

 

示例 1：

输入：nums = [1,2,3,4,5]
输出：[1,2,4,5,3]
解释：
i=1, nums[i] = 2, 两相邻元素平均值为 (1+4) / 2 = 2.5
i=2, nums[i] = 4, 两相邻元素平均值为 (2+5) / 2 = 3.5
i=3, nums[i] = 5, 两相邻元素平均值为 (4+3) / 2 = 3.5

示例 2：

输入：nums = [6,2,0,9,7]
输出：[9,7,6,2,0]
解释：
i=1, nums[i] = 7, 两相邻元素平均值为 (9+6) / 2 = 7.5
i=2, nums[i] = 6, 两相邻元素平均值为 (7+2) / 2 = 4.5
i=3, nums[i] = 2, 两相邻元素平均值为 (6+0) / 2 = 3

 

提示：

• 3 <= nums.length <= 105
• 0 <= nums[i] <= 105

方法一：排序 · Go 实现

思考

需避免 $2\cdot a[i]=a[i-1]+a[i+1]$，即三点不构成等差。元素互异，排序后把较小一半与较大一半交错放置。

偶数下标取前半、奇数下标取后半，每个中位邻居分别来自大小两端，无法再平均。

由于数组中的元素是互不相同的，我们可以先对数组进行排序，然后将数组分成两部分，将前一半的元素放到答案数组中的偶数位置，将后一半的元素放到答案数组中的奇数位置。这样，对于每个元素，它的两个相邻元素都不会等于它的平均值。

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

func rearrangeArray(nums []int) (ans []int) {
	sort.Ints(nums)
	n := len(nums)
	m := (n + 1) >> 1
	for i := 0; i < m; i++ {
		ans = append(ans, nums[i])
		if i+m < n {
			ans = append(ans, nums[i+m])
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1969. 数组元素的最小非零乘积

中等1 种解法

标签：贪心、递归、数学

题目、示例与约束

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作 任意 次：

• 从 nums 中选择两个元素 x 和 y  。
• 选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。

比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。

请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109 + 7 取余 后返回。

注意：答案应为取余 之前 的最小值。

 

示例 1：

输入：p = 1
输出：1
解释：nums = [1] 。
只有一个元素，所以乘积为该元素。

示例 2：

输入：p = 2
输出：6
解释：nums = [01, 10, 11] 。
所有交换要么使乘积变为 0 ，要么乘积与初始乘积相同。
所以，数组乘积 1 * 2 * 3 = 6 已经是最小值。

示例 3：

输入：p = 3
输出：1512
解释：nums = [001, 010, 011, 100, 101, 110, 111]
- 第一次操作中，我们交换第二个和第五个元素最左边的数位。
    - 结果数组为 [001, 110, 011, 100, 001, 110, 111] 。
- 第二次操作中，我们交换第三个和第四个元素中间的数位。
    - 结果数组为 [001, 110, 001, 110, 001, 110, 111] 。
数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512 是最小乘积。

 

提示：

• 1 <= p <= 60

方法一：贪心 + 快速幂 · Go 实现

思考

允许交换两个数的二进制位，总和不变。总和固定时，乘积在把数尽量两极分化后最小，且不能出现 $0$。

最大元 $2^p-1$ 不必动；其余配成 $(1,2^p-2)$ 各 $2^{p-1}-1$ 对。答案为 $(2^p-1)(2^p-2{)}^{2^{p-1}-1}$，用快速幂取模。

我们注意到，每一次操作，并不会改变元素的和，而在元素和不变的情况下，要想使得乘积最小，应该尽可能最大化元素的差值。

由于最大的元素为 $2^p-1$，无论与哪个元素交换，都不会使得差值变大，因此我们不需要考虑与最大元素交换的情况。

对于其它的 $[1,.{.2}^p-2]$ 的元素，我们依次将首尾元素两两配对，即 $x$ 与 $2^p-1-x$ 进行配置，那么经过若干次操作过后，每一对元素都变成了 $(1,2^p-2)$，那么最终的乘积为 $(2^p-1)\times (2^p-2{)}^{2^{p-1}-1}$。

时间复杂度 $O(p)$，空间复杂度 $O(1)$。

func minNonZeroProduct(p int) int {
	const mod int = 1e9 + 7
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	a := ((1 << p) - 1) % mod
	b := qpow(((1<<p)-2)%mod, (1<<(p-1))-1)
	return a * b % mod
}

力扣原题 · Doocs 题解来源

1974. 使用特殊打字机键入单词的最少时间

简单1 种解法

标签：贪心、字符串

题目、示例与约束

有一个特殊打字机，它由一个 圆盘 和一个 指针 组成， 圆盘上标有小写英文字母 'a' 到 'z'。只有 当指针指向某个字母时，它才能被键入。指针 初始时 指向字符 'a' 。

每一秒钟，你可以执行以下操作之一：

• 将指针 顺时针 或者 逆时针 移动一个字符。
• 键入指针 当前 指向的字符。

给你一个字符串 word ，请你返回键入 word 所表示单词的 最少 秒数 。

 

示例 1：

输入：word = "abc"
输出：5
解释：
单词按如下操作键入：
- 花 1 秒键入字符 'a'，因为指针初始指向 'a' ，故不需移动指针。
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 1 秒将指针顺时针移到 'c' 。
- 花 1 秒键入字符 'c' 。

示例 2：

输入：word = "bza"
输出：7
解释：
单词按如下操作键入：
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 2 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 1 秒将指针顺时针移到 'a' 。
- 花 1 秒键入字符 'a' 。

示例 3：

输入：word = "zjpc"
输出：34
解释：
单词按如下操作键入：
- 花 1 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 10 秒将指针顺时针移到 'j' 。
- 花 1 秒键入字符 'j' 。
- 花 6 秒将指针顺时针移到 'p' 。
- 花 1 秒键入字符 'p' 。
- 花 13 秒将指针逆时针移到 'c' 。
- 花 1 秒键入字符 'c' 。

 

提示：

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

方法一：贪心 · Go 实现

思考

指针在圆环字母表上移动，每个字符还需一秒键入。两点间应走较短弧，不必枚举方向组合。

从 'a' 起对相邻字符取 $|c-a|$ 与 $26-|c-a|$ 的较小者，再加单词长度。

我们初始化答案变量 $\mathit{\text{ans}}$ 为字符串的长度，表示我们至少需要 $\mathit{\text{ans}}$ 秒来键入字符串。

接下来，我们遍历字符串，对于每个字符，我们计算当前字符和前一个字符之间的最小距离，将这个距离加到答案中。然后我们更新当前字符为前一个字符，继续遍历。

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

func minTimeToType(word string) int {
	ans := len(word)
	a := rune('a')
	for _, c := range word {
		d := int(max(a-c, c-a))
		ans += min(d, 26-d)
		a = c
	}
	return ans
}

力扣原题 · Doocs 题解来源

1975. 最大方阵和

中等1 种解法

标签：贪心、数组、矩阵

题目、示例与约束

给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ：

• 选择 matrix 中 相邻 两个元素，并将它们都 乘以 -1 。

如果两个元素有 公共边 ，那么它们就是 相邻 的。

你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。

 

示例 1：

输入：matrix = [[1,-1],[-1,1]]
输出：4
解释：我们可以执行以下操作使和等于 4 ：
- 将第一行的 2 个元素乘以 -1 。
- 将第一列的 2 个元素乘以 -1 。

示例 2：

输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
输出：16
解释：我们可以执行以下操作使和等于 16 ：
- 将第二行的最后 2 个元素乘以 -1 。

 

提示：

• n == matrix.length == matrix[i].length
• 2 <= n <= 250
• -105 <= matrix[i][j] <= 105

方法一：贪心 · Go 实现

思考

相邻两格可同时变号，等价于把负号在网格上移动。零或偶数个负号可全部消掉；奇数个负号必然剩一个。

答案为绝对值之和，奇数负号时再减去两倍最小绝对值，把负号留在绝对值最小的格子上。

如果矩阵中存在零，或者矩阵中负数的个数为偶数，那么最大和就是矩阵中所有元素的绝对值之和。

否则，说明矩阵中有奇数个负数，最终一定会剩下一个负数，我们选择绝对值最小的数，将其变为负数，这样可以使得最终的和最大。

时间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$。

func maxMatrixSum(matrix [][]int) int64 {
	var s int64
	mi, cnt := 1<<30, 0
	for _, row := range matrix {
		for _, x := range row {
			if x < 0 {
				cnt++
				x = -x
			}
			mi = min(mi, x)
			s += int64(x)
		}
	}
	if cnt%2 == 0 {
		return s
	}
	return s - int64(mi*2)
}

力扣原题 · Doocs 题解来源

1989. 捉迷藏中可捕获的最大人数 🔒

中等1 种解法

标签：贪心、数组、双指针

题目、示例与约束

你正在和你的朋友玩捉迷藏游戏。在捉迷藏比赛中，人们被分成两组：是 “鬼” 的人，和不是 “鬼” 的人。是 “鬼” 的人想要抓住尽可能多的不是 “鬼” 的人。

给定一个 从 0 开始建立索引 的整数数组 team，其中只包含 0 (表示 不是 “鬼” 的人) 和 1 (表示是 “鬼” 的人)，以及一个整数 dist。索引 i 为 “鬼” 的人可以捕获索引在 [i - dist, i + dist](包括) 范围内且 不是 “鬼” 的任何一个人。

返回 “鬼” 所能捕获的最大人数。

 

示例 1:

输入: team = [0,1,0,1,0], dist = 3
输出: 2
解释:
在索引 1 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [1-3, 1+3] = [-2, 4] 内的人。
他们可以抓住索引 2 中不是 “鬼” 的人。
在索引 3 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [3-3, 3+3] = [0, 6] 内的人。
他们可以抓住索引 0 中不是 “鬼” 的人。
在索引 4 上不是 “鬼” 的人不会被抓住，因为在索引 1 和 3 上的人已经抓住了一个人。

示例 2:

输入: team = [1], dist = 1
输出: 0
解释:
没有 “鬼" 要抓的人。

示例 3:

输入: team = [0], dist = 1
输出: 0
解释:
没有 “鬼” 来抓人。

 

提示:

• 1 <= team.length <= 105
• 0 <= team[i] <= 1
• 1 <= dist <= team.length

方法一：双指针 · Go 实现

思考

每个鬼最多抓距离 $\mathit{\text{dist}}$ 内一个未被抓的人，求最多抓多少。一对多匹配可用双指针从左扫描。

$i$ 指向鬼， $j$ 指向下一个可抓的人； $j$ 落后过多或仍是鬼则右移。匹配成功则双方前进。

每人至多被考虑一次。

我们可以用两个指针 $i$ 和 $j$ 指向鬼和非鬼的人，初始时 $i=0$, $j=0$。

然后我们从左到右遍历数组，当遇到鬼时，即 $team[i]=1$ 时，如果此时 $j<n$ 并且 $\mathit{\text{team}}[j]=1$ 或者 $i-j>\mathit{\text{dist}}$，则指针 $j$ 循环右移，也即是说，我们要找到第一个不是鬼的人，且 $i$ 和 $j$ 之间的距离不超过 $\mathit{\text{dist}}$。如果找到了这样的人，则将指针 $j$ 右移一位，表示我们已经抓住了这个人，同时答案加一。继续遍历数组，直到遍历完整个数组。

最后返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\mathit{\text{team}}$ 的长度。空间复杂度 $O(1)$。

func catchMaximumAmountofPeople(team []int, dist int) (ans int) {
	n := len(team)
	for i, j := 0, 0; i < n; i++ {
		if team[i] == 1 {
			for j < n && (team[j] == 1 || i-j > dist) {
				j++
			}
			if j < n && abs(i-j) <= dist {
				ans++
				j++
			}
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

1996. 游戏中弱角色的数量

中等1 种解法

标签：栈、贪心、数组、排序、单调栈

题目、示例与约束

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。

如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。

返回 弱角色 的数量。

 

示例 1：

输入：properties = [[5,5],[6,3],[3,6]]
输出：0
解释：不存在攻击和防御都严格高于其他角色的角色。

示例 2：

输入：properties = [[2,2],[3,3]]
输出：1
解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。

示例 3：

输入：properties = [[1,5],[10,4],[4,3]]
输出：1
解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。

 

提示：

• 2 <= properties.length <= 105
• properties[i].length == 2
• 1 <= attacki, defensei <= 105

方法一：排序 + 遍历 · Go 实现

思考

弱角色存在另一人攻防都严格更大。二维偏序若对每人对扫描为平方。按攻击降序、同攻击按防御升序排序后，扫描时左侧攻击已更大（或相同但防御更小，无法构成严格双优）。

维护已见最大防御，当前防御更小则为弱角色。

我们可以将所有角色按照攻击力降序排序，防御力升序排序。

然后遍历所有角色，对于当前角色，如果其防御力小于之前的最大防御力，则说明其为弱角色，答案加一，否则更新最大防御力。

遍历结束后，即可得到答案。

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

func numberOfWeakCharacters(properties [][]int) (ans int) {
	sort.Slice(properties, func(i, j int) bool {
		a, b := properties[i], properties[j]
		if a[0] == b[0] {
			return a[1] < b[1]
		}
		return a[0] > b[0]
	})
	mx := 0
	for _, x := range properties {
		if x[1] < mx {
			ans++
		} else {
			mx = x[1]
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2007. 从双倍数组中还原原数组

中等1 种解法

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

题目、示例与约束

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

 

示例 1：

输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。

示例 2：

输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。

示例 3：

输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。

 

提示：

• 1 <= changed.length <= 105
• 0 <= changed[i] <= 105

方法一：排序 · Go 实现

思考

$n\le {10}^5$，不能对每个元素再线性查找其两倍。若 changed 可由某数组翻倍得到，则其中最小者必属于原数组：更小的「一半」不存在。

排序后从小到大消费：每次把 $x$ 配给尚存的 $2x$。计数器记录剩余次数，已配对的 $x$ 跳过。

若某次 $2x$ 不足，则无法还原。零与重复值由计数器一并处理。

我们注意到，如果数组 changed 是一个双倍数组，那么数组 changed 中最小的元素也一定是原数组中的元素，因此，我们可以先对数组 changed 进行排序，然后以第一个元素作为起点，从小到大遍历数组 changed。

我们使用一个哈希表或数组 $cnt$ 来统计数组 changed 中每个元素的出现次数。对于数组 changed 中的每个元素 $x$，我们首先检查 $x$ 是否存在于 $cnt$ 中。如果不存在，我们直接跳过这个元素。否则，我们将 $cnt[x]$ 减一，并检查 $x\times 2$ 是否存在于 $cnt$ 中。如果不存在，我们直接返回一个空数组。否则，我们将 $cnt[x\times 2]$ 减一，并将 $x$ 加入答案数组中。

遍历结束后，返回答案数组即可。

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

func findOriginalArray(changed []int) (ans []int) {
	sort.Ints(changed)
	cnt := make([]int, changed[len(changed)-1]+1)
	for _, x := range changed {
		cnt[x]++
	}
	for _, x := range changed {
		if cnt[x] == 0 {
			continue
		}
		cnt[x]--
		y := x << 1
		if y >= len(cnt) || cnt[y] <= 0 {
			return []int{}
		}
		cnt[y]--
		ans = append(ans, x)
	}
	return
}

力扣原题 · Doocs 题解来源

2027. 转换字符串的最少操作次数

简单1 种解法

标签：贪心、字符串

题目、示例与约束

给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。

一次 操作 定义为从 s 中选出 三个连续字符 并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持 不变 。

返回将 s 中所有字符均转换为 'O' 需要执行的 最少 操作次数。

 

示例 1：

输入：s = "XXX"
输出：1
解释：XXX -> OOO
一次操作，选中全部 3 个字符，并将它们转换为 'O' 。

示例 2：

输入：s = "XXOX"
输出：2
解释：XXOX -> OOOX -> OOOO
第一次操作，选择前 3 个字符，并将这些字符转换为 'O' 。
然后，选中后 3 个字符，并执行转换。最终得到的字符串全由字符 'O' 组成。

示例 3：

输入：s = "OOOO"
输出：0
解释：s 中不存在需要转换的 'X' 。

 

提示：

• 3 <= s.length <= 1000
• s[i] 为 'X' 或 'O'

方法一：贪心 · Go 实现

思考

每次操作覆盖连续三位，可将其中任意 X 变成 O。 $n\le 1000$，模拟即可。为减少次数，每次应尽量吃掉尚未处理的最左 X，并一次覆盖其后两位。

因此遇到 X 就计数加一，下标跳过三格；遇到 O 则只前进一步。覆盖区间互不重叠，次数最优。

遍历字符串 $s$，只要遇到 'X'，指针 $i$ 就直接往后移动三格，并且答案加 $1$；否则指针 $i$ 往后移动一格。

时间复杂度 $O(n)$。其中 $n$ 表示字符串 $s$ 的长度。

func minimumMoves(s string) (ans int) {
	for i := 0; i < len(s); i++ {
		if s[i] == 'X' {
			ans++
			i += 2
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2029. 石子游戏 IX

中等1 种解法

标签：贪心、极小化极大、数组、数学、计数、博弈、Nim 游戏、零和博弈

题目、示例与约束

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。

• 如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
• 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。

假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。

 

示例 1：

输入：stones = [2,1]
输出：true
解释：游戏进行如下：
- 回合 1：Alice 可以移除任意一个石子。
- 回合 2：Bob 移除剩下的石子。 
已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。

示例 2：

输入：stones = [2]
输出：false
解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。 
由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。

示例 3：

输入：stones = [5,1,2,4,3]
输出：false
解释：Bob 总会获胜。其中一种可能的游戏进行方式如下：
- 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
- 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
- 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
- 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
- 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.
Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。

 

提示：

• 1 <= stones.length <= 105
• 1 <= stones[i] <= 104

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

思考

胜负只与价值和模 $3$ 有关， $n\le {10}^5$ 不能模拟到取完。余 $0$ 不改变当前模，可穿插使用；先手第一枚不能取 $0$。

先手选 $1$ 后，最优序列为 $1,1,2,1,2,\dots$（对称地从 $2$ 开始）。把余 $0$ 的个数计入回合长度后，若总回合为奇数且两种非零余数尚未耗尽成平局，则先手胜。

对 $cnt$ 与对调后的 $(cnt[0],cnt[2],cnt[1])$ 各判定一次，存在一种开局即可。

由于玩家的目标是使得已移除石子的价值总和不能被 $3$ 整除，因此我们只需要考虑每个石子的价值对 $3$ 的余数即可。

我们用一个长度为 $3$ 的数组 $\mathit{\text{cnt}}$ 维护当前剩余石子的价值对 $3$ 的余数的个数，其中 $\mathit{\text{cnt}}[0]$ 表示余数为 $0$ 的个数，而 $\mathit{\text{cnt}}[1]$ 和 $\mathit{\text{cnt}}[2]$ 分别表示余数为 $1$ 和 $2$ 的个数。

在第一回合，Alice 不能移除余数为 $0$ 的石子，因为这样会使得已移除石子的价值总和能被 $3$ 整除。因此，Alice 只能移除余数为 $1$ 或 $2$ 的石子。

我们首先考虑 Alice 移除余数为 $1$ 的石子的情况。如果 Alice 移除了一个余数为 $1$ 的石子，石子 $0$ 对石子价值总和对 $3$ 的余数不会改变，因此价值对 $3$ 的余数为 $0$ 的石子可以在任意回合被移除，我们暂时不考虑。所以 Bob 也只能移除余数为 $1$ 的石子，之后 Alice 移除余数为 $2$ 的石子，依次进行，序列为 $1,1,2,1,2,\dots$。在这种情况下，如果最终回合数为奇数，且还有剩余石子，那么 Alice 获胜，否则 Bob 获胜。

对于第一回合 Alice 移除余数为 $2$ 的石子的情况，我们可以得到类似的结论。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{stones}}$ 的长度。空间复杂度 $O(1)$。

func stoneGameIX(stones []int) bool {
	c1 := [3]int{}
	for _, x := range stones {
		c1[x%3]++
	}
	c2 := [3]int{c1[0], c1[2], c1[1]}
	check := func(cnt [3]int) bool {
		if cnt[1] == 0 {
			return false
		}
		cnt[1]--
		r := 1 + min(cnt[1], cnt[2])*2 + cnt[0]
		if cnt[1] > cnt[2] {
			cnt[1]--
			r++
		}
		return r%2 == 1 && cnt[1] != cnt[2]
	}
	return check(c1) || check(c2)
}

力扣原题 · Doocs 题解来源

2030. 含特定字母的最小子序列

困难1 种解法

标签：栈、贪心、字符串、单调栈

题目、示例与约束

给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。

返回 s 中长度为 k 且 字典序最小 的子序列，该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现 至少 repetition 次。

子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。

字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。

 

示例 1：

输入：s = "leet", k = 3, letter = "e", repetition = 1
输出："eet"
解释：存在 4 个长度为 3 ，且满足字母 'e' 出现至少 1 次的子序列：
- "lee"（"leet"）
- "let"（"leet"）
- "let"（"leet"）
- "eet"（"leet"）
其中字典序最小的子序列是 "eet" 。

示例 2：

输入：s = "leetcode", k = 4, letter = "e", repetition = 2
输出："ecde"
解释："ecde" 是长度为 4 且满足字母 "e" 出现至少 2 次的字典序最小的子序列。

示例 3：

输入：s = "bb", k = 2, letter = "b", repetition = 2
输出："bb"
解释："bb" 是唯一一个长度为 2 且满足字母 "b" 出现至少 2 次的子序列。

 

提示：

• 1 <= repetition <= k <= s.length <= 5 * 104
• s 由小写英文字母组成
• letter 是一个小写英文字母，在 s 中至少出现 repetition 次

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

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：维护候选字符队列，并记录队内与未读取部分的 letter 数量。读入更小字符时，从队尾移除更大字符；但若移除 letter 会导致剩余数量不足，就停止弹出。当扫描到必须开始确定答案的位置时，取队首字符；普通字符只有在剩余答案位置足以容纳所需 letter 时才选入，选入 letter 则减少尚需数量。

复杂度：设字符串长度为 n，答案长度为 k。每个字符最多入队、出队各一次，时间为 O(n)。候选队列最坏占 O(n)，答案占 O(k)，总辅助空间为 O(n+k)=O(n)。

import "strings"

// github.com/EndlessCheng/codeforces-go
func smallestSubsequence(s string, k int, letter byte, repetition int) string {
	ans := []byte{}
	unread := strings.Count(s, string(letter)) // 未遍历到的 letter 个数
	inQ := 0                                   // 在单调队列中的 letter 个数
	q := []byte{}
	for i, n := 0, len(s); len(ans) < k; i++ {
		// 将 s[i] 插入单调队列
		for i < n && len(q) > 0 && s[i] < q[len(q)-1] {
			if q[len(q)-1] == letter { // 特判队尾是 letter 的情况
				if inQ+unread <= repetition { // 弹出队尾会导致无法凑足 repetition 个 letter
					break
				}
				inQ--
			}
			q = q[:len(q)-1]
		}
		if i < n {
			if s[i] == letter {
				unread--
				inQ++
			}
			q = append(q, s[i])
		}

		if i >= n-k {
			// 从队首拿到字典序最小的字符
			if q[0] == letter {
				inQ--
				repetition--
				ans = append(ans, q[0])
			} else if len(ans)+repetition < k {
				ans = append(ans, q[0])
			}
			q = q[1:]
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

2037. 使每位学生都有座位的最少移动次数

简单1 种解法

标签：贪心、数组、计数排序、排序

题目、示例与约束

一个房间里有 n 个 空闲 座位和 n 名 站着的 学生，房间用一个数轴表示。给你一个长度为 n 的数组 seats ，其中 seats[i] 是第 i 个座位的位置。同时给你一个长度为 n 的数组 students ，其中 students[j] 是第 j 位学生的位置。

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

• 增加或者减少第 i 位学生的位置，每次变化量为 1 （也就是将第 i 位学生从位置 x 移动到 x + 1 或者 x - 1）

请你返回使所有学生都有座位坐的 最少移动次数 ，并确保没有两位学生的座位相同。

请注意，初始时有可能有多个座位或者多位学生在 同一 位置。

 

示例 1：

输入：seats = [3,1,5], students = [2,7,4]
输出：4
解释：学生移动方式如下：
- 第一位学生从位置 2 移动到位置 1 ，移动 1 次。
- 第二位学生从位置 7 移动到位置 5 ，移动 2 次。
- 第三位学生从位置 4 移动到位置 3 ，移动 1 次。
总共 1 + 2 + 1 = 4 次移动。

示例 2：

输入：seats = [4,1,5,9], students = [1,3,2,6]
输出：7
解释：学生移动方式如下：
- 第一位学生不移动。
- 第二位学生从位置 3 移动到位置 4 ，移动 1 次。
- 第三位学生从位置 2 移动到位置 5 ，移动 3 次。
- 第四位学生从位置 6 移动到位置 9 ，移动 3 次。
总共 0 + 1 + 3 + 3 = 7 次移动。

示例 3：

输入：seats = [2,2,6,6], students = [1,3,2,6]
输出：4
解释：学生移动方式如下：
- 第一位学生从位置 1 移动到位置 2 ，移动 1 次。
- 第二位学生从位置 3 移动到位置 6 ，移动 3 次。
- 第三位学生不移动。
- 第四位学生不移动。
总共 1 + 3 + 0 + 0 = 4 次移动。

 

提示：

• n == seats.length == students.length
• 1 <= n <= 100
• 1 <= seats[i], students[j] <= 100

方法一：排序 · Go 实现

思考

座位与学生一一匹配，总移动为对应位置差的绝对值和。交叉匹配不会更优：排序后第 $i$ 小座位配第 $i$ 小学生。

$n\le 100$，排序后对应相减求和即可。

将两个数组分别排序，然后遍历两个数组，计算每个学生的座位与其实际座位的距离，将所有距离相加即为答案。

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

func minMovesToSeat(seats []int, students []int) (ans int) {
	sort.Ints(seats)
	sort.Ints(students)
	for i, a := range seats {
		b := students[i]
		ans += abs(a - b)
	}
	return
}

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

力扣原题 · Doocs 题解来源

2038. 如果相邻两个颜色均相同则删除当前颜色

中等1 种解法

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

题目、示例与约束

总共有 n 个颜色片段排成一列，每个颜色片段要么是 'A' 要么是 'B' 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。

Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。

• 如果一个颜色片段为 'A' 且 相邻两个颜色 都是颜色 'A' ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 'B' 片段。
• 如果一个颜色片段为 'B' 且 相邻两个颜色 都是颜色 'B' ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 'A' 片段。
• Alice 和 Bob 不能 从字符串两端删除颜色片段。
• 如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。

假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。

 

示例 1：

输入：colors = "AAABABB"
输出：true
解释：
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 'A' ，这也是唯一一个相邻颜色片段都是 'A' 的 'A' 。

现在轮到 Bob 操作。
Bob 无法执行任何操作，因为没有相邻位置都是 'B' 的颜色片段 'B' 。
因此，Alice 获胜，返回 true 。

示例 2：

输入：colors = "AA"
输出：false
解释：
Alice 先操作。
只有 2 个 'A' 且它们都在字符串的两端，所以她无法执行任何操作。
因此，Bob 获胜，返回 false 。

示例 3：

输入：colors = "ABBBBBBBAAA"
输出：false
解释：
ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的选择是删除从右数起第二个 'A' 。

ABBBBBBBAA -> ABBBBBBAA
接下来轮到 Bob 操作。
他有许多选择，他可以选择任何一个 'B' 删除。

然后轮到 Alice 操作，她无法删除任何片段。
所以 Bob 获胜，返回 false 。

 

提示：

• 1 <= colors.length <= 105
• colors 只包含字母 'A' 和 'B'

方法一：计数 · Go 实现

思考

一次操作删除夹在两个同色之间的棋子，双方互不抢对方的片段。 $n\le {10}^5$，只需比较两人可操作次数。

连续段长度为 $\ell$ 时，该颜色可删 $max(\ell -2,0)$ 次。统计 'A' 与 'B' 的可删次数，先手胜当且仅当前者更大。

我们统计字符串 colors 中连续出现 $3$ 个 'A' 或 $3$ 个 'B' 的个数，分别记为 $a$ 和 $b$。

最后判断 $a$ 是否大于 $b$，是则返回 true，否则返回 false。

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

func winnerOfGame(colors string) bool {
	n := len(colors)
	a, b := 0, 0
	for i, j := 0, 0; i < n; i = j {
		for j < n && colors[j] == colors[i] {
			j++
		}
		m := j - i - 2
		if m > 0 {
			if colors[i] == 'A' {
				a += m
			} else {
				b += m
			}
		}
	}
	return a > b
}

力扣原题 · Doocs 题解来源

2064. 分配给商店的最多商品的最小值

中等1 种解法

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

题目、示例与约束

给你一个整数 n ，表示有 n 间零售商店。总共有 m 种商品，每种商品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。

你需要将 所有商品 分配到零售商店，并遵守这些规则：

• 一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
• 分配后，每间商店都会被分配一定数目的商品（可能为 0 件）。用 x 表示所有商店中分配商品数目的最大值，你希望 x 越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。

请你返回最小的可能的 x 。

 

示例 1：

输入：n = 6, quantities = [11,6]
输出：3
解释： 一种最优方案为：
- 11 件种类为 0 的商品被分配到前 4 间商店，分配数目分别为：2，3，3，3 。
- 6 件种类为 1 的商品被分配到另外 2 间商店，分配数目分别为：3，3 。
分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。

示例 2：

输入：n = 7, quantities = [15,10,10]
输出：5
解释：一种最优方案为：
- 15 件种类为 0 的商品被分配到前 3 间商店，分配数目为：5，5，5 。
- 10 件种类为 1 的商品被分配到接下来 2 间商店，数目为：5，5 。
- 10 件种类为 2 的商品被分配到最后 2 间商店，数目为：5，5 。
分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) = 5 。

示例 3：

输入：n = 1, quantities = [100000]
输出：100000
解释：唯一一种最优方案为：
- 所有 100000 件商品 0 都分配到唯一的商店中。
分配给所有商店的最大商品数目为 max(100000) = 100000 。

 

提示：

• m == quantities.length
• 1 <= m <= n <= 105
• 1 <= quantities[i] <= 105

方法一：二分查找 · Go 实现

思考

把各类商品分给 $n$ 家店，最小化单店件数上限 $x$。 $x$ 越大越容易分完，具有单调性。种类与 $n$ 均为 ${10}^5$，须 $O(m)$ 检验。

给定 $x$，第 $i$ 类需要 $\lceil q_i/x\rceil$ 家店，总和 $\le n$ 则可行。二分最小可行 $x$。

我们注意到，如果分配给任意商店商品数目的最大值为 $x$，且满足题目要求，那么 $x+1$ 也一定满足题目要求，这存在着单调性。因此我们可以通过二分查找，找到一个最小的 $x$，使得 $x$ 满足题目要求。

我们定义二分查找的左边界 $left=1$，右边界 $right={10}^5$。对于二分查找的每一步，我们取中间值 $mid$，判断是否存在一个分配方案，使得分配给任意商店商品数目的最大值为 $mid$，如果存在，那么我们将右边界 $right$ 移动到 $mid$，否则将左边界 $left$ 移动到 $mid+1$。

二分查找结束后，答案即为 $left$。

时间复杂度 $O(m\times \log M)$，空间复杂度 $O(1)$。其中 $m$ 为商品种类数，而 $M$ 为商品数目的最大值，本题中 $M\le {10}^5$。

func minimizedMaximum(n int, quantities []int) int {
	return 1 + sort.Search(1e5, func(x int) bool {
		x++
		cnt := 0
		for _, v := range quantities {
			cnt += (v + x - 1) / x
		}
		return cnt <= n
	})
}

力扣原题 · Doocs 题解来源

2071. 你可以安排的最多任务数目

困难1 种解法

标签：贪心、队列、数组、双指针、二分查找、排序、单调队列

题目、示例与约束

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。

给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。

 

示例 1：

输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）

示例 2：

输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）

示例 3：

输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）

示例 4：

输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）

 

提示：

• n == tasks.length
• m == workers.length
• 1 <= n, m <= 5 * 104
• 0 <= pills <= m
• 0 <= tasks[i], workers[j], strength <= 109

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

思考

完成任务数 $x$ 具有单调性： $x$ 能完成则更少也能。 $n,m\le 5\times {10}^4$，检验须近似线性。应把最难的 $x$ 个任务交给最强的 $x$ 个工人。

工人从弱到强（在这 $x$ 人内部）尝试：能不吃药则吃掉最易任务；否则对当前最难任务用药。用双端队列维护当前力所能及的任务。

二分最大可行 $x$。

将任务按照完成时间从小到大排序，将工人按照能力从小到大排序。

假设我们要安排的任务数为 $x$，那么我们可以贪心地将前 $x$ 个任务分配给力量值最大的 $x$ 个工人。假设能完成任务数为 $x$，那么也一定能完成任务数为 $x-1$， $x-2$， $x-3$，…， $1$， $0$ 的情况。因此，我们可以使用二分查找的方法，找到最大的 $x$，使得能够完成任务数为 $x$ 的情况。

我们定义一个函数 $check(x)$，表示是否能够完成任务数为 $x$ 的情况。

函数 $check(x)$ 的实现如下：

从小到大遍历力量值最大的 $x$ 个工人，记当前遍历到的工人为 $j$，那么当前可选任务必须满足 $tasks[i]\le workers[j]+strength$。

如果当前可选任务中要求力量值最小的一个 $task[i]$ 小于等于 $workers[j]$，那么第 $j$ 个工人不用吃药就可以完成任务 $task[i]$。否则，当前工人必须吃药，如果还有药丸，那么吃药，并且在当前可选任务中选择要求力量值最大的一个任务完成。否则，返回 false。

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

func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {
	sort.Ints(tasks)
	sort.Ints(workers)
	n, m := len(tasks), len(workers)
	left, right := 0, min(m, n)
	check := func(x int) bool {
		p := pills
		q := []int{}
		i := 0
		for j := m - x; j < m; j++ {
			for i < x && tasks[i] <= workers[j]+strength {
				q = append(q, tasks[i])
				i++
			}
			if len(q) == 0 {
				return false
			}
			if q[0] <= workers[j] {
				q = q[1:]
			} else if p == 0 {
				return false
			} else {
				p--
				q = q[:len(q)-1]
			}
		}
		return true
	}
	for left < right {
		mid := (left + right + 1) >> 1
		if check(mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

2078. 两栋颜色不同且距离最远的房子

简单1 种解法

标签：贪心、数组

题目、示例与约束

街上有 n 栋房子整齐地排成一列，每栋房子都粉刷上了漂亮的颜色。给你一个下标从 0 开始且长度为 n 的整数数组 colors ，其中 colors[i] 表示第  i 栋房子的颜色。

返回 两栋 颜色 不同 房子之间的 最大 距离。

第 i 栋房子和第 j 栋房子之间的距离是 abs(i - j) ，其中 abs(x) 是 x 的绝对值。

 

示例 1：

输入：colors = [1,1,1,6,1,1,1]
输出：3
解释：上图中，颜色 1 标识成蓝色，颜色 6 标识成红色。
两栋颜色不同且距离最远的房子是房子 0 和房子 3 。
房子 0 的颜色是颜色 1 ，房子 3 的颜色是颜色 6 。两栋房子之间的距离是 abs(0 - 3) = 3 。
注意，房子 3 和房子 6 也可以产生最佳答案。

示例 2：

输入：colors = [1,8,3,8,3]
输出：4
解释：上图中，颜色 1 标识成蓝色，颜色 8 标识成黄色，颜色 3 标识成绿色。
两栋颜色不同且距离最远的房子是房子 0 和房子 4 。
房子 0 的颜色是颜色 1 ，房子 4 的颜色是颜色 3 。两栋房子之间的距离是 abs(0 - 4) = 4 。

示例 3：

输入：colors = [0,1]
输出：1
解释：两栋颜色不同且距离最远的房子是房子 0 和房子 1 。
房子 0 的颜色是颜色 0 ，房子 1 的颜色是颜色 1 。两栋房子之间的距离是 abs(0 - 1) = 1 。

 

提示：

• n == colors.length
• 2 <= n <= 100
• 0 <= colors[i] <= 100
• 生成的测试数据满足 至少 存在 2 栋颜色不同的房子

方法一：贪心 · Go 实现

思考

$n\le 100$，枚举所有异色对可行，但最优解必有一端在数组端点：若两端同色，则与该色不同的最左、最右房子分别与另一端组成候选。

先比较 $colors[0]$ 与 $colors[-1]$；相同则向内找到第一个异色下标，取较大跨度。

我们可以发现，如果第一栋房子和最后一栋房子颜色不同，那么它们之间的距离就是最大的距离，即 $n-1$。

如果第一栋房子和最后一栋房子颜色相同，那么我们可以从左向右找到第一栋颜色不同的房子，记为 $i$，从右向左找到第一栋颜色不同的房子，记为 $j$，那么最大的距离就是 $max(n-i-1,j)$。

时间复杂度 $O(n)$，其中 $n$ 是房子的数量。空间复杂度 $O(1)$。

func maxDistance(colors []int) int {
	n := len(colors)
	if colors[0] != colors[n-1] {
		return n - 1
	}
	i, j := 1, n-2
	for colors[i] == colors[0] {
		i++
	}
	for colors[j] == colors[0] {
		j--
	}
	return max(n-i-1, j)
}

力扣原题 · Doocs 题解来源

2087. 网格图中机器人回家的最小代价

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你一个 m x n 的网格图，其中 (0, 0) 是最左上角的格子，(m - 1, n - 1) 是最右下角的格子。给你一个整数数组 startPos ，startPos = [startrow, startcol] 表示 初始 有一个 机器人 在格子 (startrow, startcol) 处。同时给你一个整数数组 homePos ，homePos = [homerow, homecol] 表示机器人的 家 在格子 (homerow, homecol) 处。

机器人需要回家。每一步它可以往四个方向移动：上，下，左，右，同时机器人不能移出边界。每一步移动都有一定代价。再给你两个下标从 0 开始的整数数组：长度为 m 的数组 rowCosts  和长度为 n 的数组 colCosts 。

• 如果机器人往 上 或者往 下 移动到第 r 行 的格子，那么代价为 rowCosts[r] 。
• 如果机器人往 左 或者往 右 移动到第 c 列 的格子，那么代价为 colCosts[c] 。

请你返回机器人回家需要的 最小总代价 。

 

示例 1：

输入：startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
输出：18
解释：一个最优路径为：
从 (1, 0) 开始
-> 往下走到 (2, 0) 。代价为 rowCosts[2] = 3 。
-> 往右走到 (2, 1) 。代价为 colCosts[1] = 2 。
-> 往右走到 (2, 2) 。代价为 colCosts[2] = 6 。
-> 往右走到 (2, 3) 。代价为 colCosts[3] = 7 。
总代价为 3 + 2 + 6 + 7 = 18

示例 2：

输入：startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
输出：0
解释：机器人已经在家了，所以不需要移动。总代价为 0 。

 

提示：

• m == rowCosts.length
• n == colCosts.length
• 1 <= m, n <= 105
• 0 <= rowCosts[r], colCosts[c] <= 104
• startPos.length == 2
• homePos.length == 2
• 0 <= startrow, homerow < m
• 0 <= startcol, homecol < n

方法一：贪心 · Go 实现

思考

每走进一行或一列支付该行/列代价，与路径折返无关：任意从起点到家的单调路径经过的行集合与列集合相同。绕路只会多付。

因此分别累加起点与家之间须穿过的那些行代价与列代价。起点所在行/列不付（尚未「走入」）。

我们不妨假设机器人的初始位置为 $(x_0,y_0)$，家所在的位置为 $(x_1,y_1)$。

如果 $x_0<x_1$，那么机器人需要往下走，需要经过的行是 $[x_0+1,x_1]$，总代价为 $\sum _{i=x_0+1}^{x_1}rowCosts[i]$；如果 $x_0>x_1$，那么机器人需要往上走，需要经过的行是 $[x_1,x_0-1]$，总代价为 $\sum _{i=x_1}^{x_0-1}rowCosts[i]$；如果 $x_0=x_1$，那么机器人不需要往上下走，总代价为 $0$。

同理，如果 $y_0<y_1$，那么机器人需要往右走，需要经过的列是 $[y_0+1,y_1]$，总代价为 $\sum _{j=y_0+1}^{y_1}colCosts[j]$；如果 $y_0>y_1$，那么机器人需要往左走，需要经过的列是 $[y_1,y_0-1]$，总代价为 $\sum _{j=y_1}^{y_0-1}colCosts[j]$；如果 $y_0=y_1$，那么机器人不需要往左右走，总代价为 $0$。

答案为上下走的总代价与左右走的总代价之和。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是 $rowCosts$ 和 $colCosts$ 的长度。空间复杂度 $O(1)$。

func minCost(startPos []int, homePos []int, rowCosts []int, colCosts []int) int {
	x0, y0 := startPos[0], startPos[1]
	x1, y1 := homePos[0], homePos[1]
	calc := func(nums []int, i int, j int) int {
		res := 0
		for k := i; k <= j; k++ {
			res += nums[k]
		}
		return res
	}
	dx := 0
	if x0 < x1 {
		dx = calc(rowCosts, x0+1, x1)
	} else {
		dx = calc(rowCosts, x1, x0-1)
	}
	dy := 0
	if y0 < y1 {
		dy = calc(colCosts, y0+1, y1)
	} else {
		dy = calc(colCosts, y1, y0-1)
	}
	return dx + dy
}

力扣原题 · Doocs 题解来源

2091. 从数组中移除最大值和最小值

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你一个下标从 0 开始的数组 nums ，数组由若干 互不相同 的整数组成。

nums 中有一个值最小的元素和一个值最大的元素。分别称为 最小值 和 最大值 。你的目标是从数组中移除这两个元素。

一次 删除 操作定义为从数组的 前面 移除一个元素或从数组的 后面 移除一个元素。

返回将数组中 最小值 和 最大值 都 移除需要的 最小 删除次数。

 

示例 1：

输入：nums = [2,10,7,5,4,1,8,6]
输出：5
解释：
数组中的最小元素是 nums[5] ，值为 1 。
数组中的最大元素是 nums[1] ，值为 10 。
将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。
结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。

示例 2：

输入：nums = [0,-4,19,1,8,-2,-3,5]
输出：3
解释：
数组中的最小元素是 nums[1] ，值为 -4 。
数组中的最大元素是 nums[2] ，值为 19 。
将最大值和最小值都移除需要从数组前面移除 3 个元素。
结果是 3 ，这是所有可能情况中的最小删除次数。 

示例 3：

输入：nums = [101]
输出：1
解释：
数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。
移除它只需要 1 次删除操作。

 

提示：

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• nums 中的整数 互不相同

方法一 · Go 实现

思考

每次只能删两端，要删掉最小值与最大值所在位置。三种策略：只从左删到更靠右的那个，只从右删到更靠左的那个，或两端各删一段。

先定位 $mi,mx$ 并令 $mi<mx$，再取 $mx+1$、 $n-mi$、 $mi+1+n-mx$ 的最小。一次遍历定位最值。

func minimumDeletions(nums []int) int {
	mi, mx, n := 0, 0, len(nums)
	for i, num := range nums {
		if num < nums[mi] {
			mi = i
		}
		if num > nums[mx] {
			mx = i
		}
	}
	if mi > mx {
		mi, mx = mx, mi
	}
	return min(min(mx+1, n-mi), mi+1+n-mx)
}

力扣原题 · Doocs 题解来源

2098. 长度为 K 的最大偶数和子序列 🔒

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。找出 nums 长度为 k 的所有子序列中的 最大偶数和 。
返回此总和，如果此总和不存在，则返回 -1。
子序列 是一个数组，可以通过删除一些元素或不删除任何元素而从另一个数组派生，而不改变其余元素的顺序。

 

示例 1：

输入: nums = [4,1,5,3,1], k = 3
输出: 12
解释:
具有最大可能偶数和的子序列是[4,5,3]。它的和为 4 + 5 + 3 = 12

示例 2:

输入: nums = [4,6,2], k = 3
输出: 12
解释:
具有最大可能偶数和的子序列是[4,6,2]。它的和为 4 + 6 + 2 = 12

示例 3:

输入: nums = [1,3,5], k = 1
输出: -1
解释:
长度为 1 的 NUM 的子序列没有偶数和。

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105
• 1 <= k <= nums.length

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

思考

子序列不要求连续，和的奇偶由奇数个数决定。先取最大的 $k$ 个数；若已为偶数则最优。否则须换一个数以改变奇偶，且尽量少损失。

两种替换：在已选中用最小偶数换未选最大奇数，或用最小奇数换未选最大偶数。取较大者；无法换成偶数则 $-1$。

我们注意到，题目选取的是子序列，因此我们可以考虑先对数组进行排序。

接下来，我们先贪心地选取最大的 $k$ 个数，如果这些数的和为偶数，则直接返回这个和 $ans$。

否则，我们有两种贪心策略：

1. 在最大的 $k$ 个数中，找到一个最小的偶数 $mi1$，然后在剩下的 $n-k$ 个数中，找到一个最大的奇数 $mx1$，将 $mi1$ 替换为 $mx1$，如果存在这样的替换，那么替换后的和 $ans-mi1+mx1$ 一定是偶数；
2. 在最大的 $k$ 个数中，找到一个最小的奇数 $mi2$，然后在剩下的 $n-k$ 个数中，找到一个最大的偶数 $mx2$，将 $mi2$ 替换为 $mx2$，如果存在这样的替换，那么替换后的和 $ans-mi2+mx2$ 一定是偶数。

我们取最大的偶数和作为答案。如果不存在偶数和，则返回 $-1$。

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

func largestEvenSum(nums []int, k int) int64 {
	sort.Ints(nums)
	ans := 0
	n := len(nums)
	for i := 0; i < k; i++ {
		ans += nums[n-1-i]
	}
	if ans%2 == 0 {
		return int64(ans)
	}
	const inf = 1 << 29
	mx1, mx2 := -inf, -inf
	for _, x := range nums[:n-k] {
		if x%2 == 1 {
			mx1 = x
		} else {
			mx2 = x
		}
	}
	mi1, mi2 := inf, inf
	for i := n - 1; i >= n-k; i-- {
		if nums[i]%2 == 1 {
			mi2 = nums[i]
		} else {
			mi1 = nums[i]
		}
	}
	ans = max(-1, max(ans-mi1+mx1, ans-mi2+mx2))
	if ans%2 < 0 {
		return -1
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2116. 判断一个括号字符串是否有效

中等1 种解法

标签：栈、贪心、字符串、括号序列

题目、示例与约束

一个括号字符串是只由 '(' 和 ')' 组成的 非空 字符串。如果一个字符串满足下面 任意 一个条件，那么它就是有效的：

• 字符串为 ().
• 它可以表示为 AB（A 与 B 连接），其中A 和 B 都是有效括号字符串。
• 它可以表示为 (A) ，其中 A 是一个有效括号字符串。

给你一个括号字符串 s 和一个字符串 locked ，两者长度都为 n 。locked 是一个二进制字符串，只包含 '0' 和 '1' 。对于 locked 中 每一个 下标 i ：

• 如果 locked[i] 是 '1' ，你 不能 改变 s[i] 。
• 如果 locked[i] 是 '0' ，你 可以 将 s[i] 变为 '(' 或者 ')' 。

如果你可以将 s 变为有效括号字符串，请你返回 true ，否则返回 false 。

 

示例 1：

输入：s = "))()))", locked = "010100"
输出：true
解释：locked[1] == '1' 和 locked[3] == '1' ，所以我们无法改变 s[1] 或者 s[3] 。
我们可以将 s[0] 和 s[4] 变为 '(' ，不改变 s[2] 和 s[5] ，使 s 变为有效字符串。

示例 2：

输入：s = "()()", locked = "0000"
输出：true
解释：我们不需要做任何改变，因为 s 已经是有效字符串了。

示例 3：

输入：s = ")", locked = "0"
输出：false
解释：locked 允许改变 s[0] 。
但无论将 s[0] 变为 '(' 或者 ')' 都无法使 s 变为有效字符串。

示例 4：

输入：s = "(((())(((())", locked = "111111010111"
输出：true
解释：locked 允许我们改变 s[6] 和 s[8]。
我们将 s[6] 和 s[8] 改为 ')' 使 s 变为有效字符串。

 

提示：

• n == s.length == locked.length
• 1 <= n <= 105
• s[i] 要么是 '(' 要么是 ')' 。
• locked[i] 要么是 '0' 要么是 '1' 。

方法一：贪心 + 两次遍历 · Go 实现

思考

可变括号可改成任一方向，锁定括号则不能改。奇数长度无法两两匹配，直接判否。若枚举每个可变位置的方向，状态数为指数级，不可行。

从左向右看，每个前缀中「可当作左括号的位置」不得少于右括号；从右向左对称。锁定的左括号必须向右匹配，锁定的右括号必须向左匹配，可变位置在对应方向上均可充当匹配方。

为此先排除奇数长度，再做两次扫描：向右时将 '(' 或未锁定位置计入余额，遇到锁定的 ')' 则消耗；向左时角色对调。任一次余额不足即无效。

我们观察发现，奇数长度的字符串一定不是有效的括号字符串，因为无论怎么匹配，都会剩下一个括号。因此，如果字符串 $s$ 的长度是奇数，提前返回 $\mathit{\text{false}}$。

接下来，我们进行两次遍历。

第一次从左到右，判断所有的 '(' 括号是否可以被 ')' 或者可变括号匹配，如果不可以，直接返回 $\mathit{\text{false}}$。

第二次从右到左，判断所有的 ')' 括号是否可以被 '(' 或者可变括号匹配，如果不可以，直接返回 $\mathit{\text{false}}$。

遍历结束，说明所有的括号都可以被匹配，字符串 $s$ 是有效的括号字符串，返回 $\mathit{\text{true}}$。

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

相似题目：

• 678. 有效的括号字符串

func canBeValid(s string, locked string) bool {
	n := len(s)
	if n%2 == 1 {
		return false
	}
	x := 0
	for i := range s {
		if s[i] == '(' || locked[i] == '0' {
			x++
		} else if x > 0 {
			x--
		} else {
			return false
		}
	}
	x = 0
	for i := n - 1; i >= 0; i-- {
		if s[i] == ')' || locked[i] == '0' {
			x++
		} else if x > 0 {
			x--
		} else {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

2126. 摧毁小行星

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。

 

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

 

提示：

• 1 <= mass <= 105
• 1 <= asteroids.length <= 105
• 1 <= asteroids[i] <= 105

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

思考

行星可吸收质量不超过自身的小行星并增加质量。若先打大的，可能因当前质量不足而失败，即使较小的本可先被吸收。质量总和与顺序都影响可行性。

先吸收较小者只会让质量单调变大，不会阻碍之后对更大者的比较，因而按质量升序贪心是安全的。 $n\le {10}^5$，排序后一次扫描即可。

将 $\mathit{\text{asteroids}}$ 排序，若途中出现 $mass<x$ 则失败，否则把 $x$ 加入 $mass$。

根据题目描述，我们可以将小行星按质量从小到大排序，然后依次遍历小行星，如果行星的质量小于小行星的质量，那么行星将被摧毁，返回 false，否则行星将获得这颗小行星的质量。

如果所有小行星都能被摧毁，返回 true。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是小行星的数量。

func asteroidsDestroyed(mass int, asteroids []int) bool {
	sort.Ints(asteroids)
	for _, x := range asteroids {
		if mass < x {
			return false
		}
		mass += x
	}
	return true
}

力扣原题 · Doocs 题解来源

2131. 连接两字母单词得到的最长回文串

中等1 种解法

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

题目、示例与约束

给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。

请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。

请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。

回文串 指的是从前往后和从后往前读一样的字符串。

 

示例 1：

输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。

示例 2：

输入：words = ["ab","ty","yt","lc","cl","ab"]
输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。

示例 3：

输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。

 

提示：

• 1 <= words.length <= 105
• words[i].length == 2
• words[i] 仅包含小写英文字母。

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

思考

回文由若干单词及其反串对称拼接，中心至多放一个形如 aa 的单词。若搜索拼接顺序，状态过多。每种单词只关心出现次数与其反串是否可配对。

哈希表统计频次后，ab 与 ba 可配 $min$ 次，各贡献 $4$ 个字符；aa 类可先按对用掉偶数个，余下一个奇数留给中心。

遍历计数表累加配对长度，若存在未用的对称单词再加 $2$。为避免 ab/ba 被计两次，对异色单词每次仍按 $min$ 累加（两侧各走一次，恰好得到 $2min\times 2$）。

我们先用一个哈希表 $\mathit{\text{cnt}}$ 统计每个单词出现的次数。

遍历 $\mathit{\text{cnt}}$ 中的每个单词 $k$ 以及其出现次数 $v$：

• 如果 $k$ 中两个字母相同，那么我们可以将 $\lfloor \frac{v}{2}\rfloor \times 2$ 个 $k$ 连接到回文串的前后，此时如果 $k$ 还剩余一个，那么我们可以先记录到 $x$ 中。

• 如果 $k$ 中两个字母不同，那么我们要找到一个单词 $k^{\prime }$，使得 $k^{\prime }$ 中的两个字母与 $k$ 相反，即 $k^{\prime }=k[1]+k[0]$。如果 $k^{\prime }$ 存在，那么我们可以将 $min(v,\mathit{\text{cnt}}[k^{\prime }])$ 个 $k$ 连接到回文串的前后。

遍历结束后，如果 $x$ 不为空，那么我们还可以将一个单词连接到回文串的中间。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为单词的数量。

func longestPalindrome(words []string) int {
	cnt := map[string]int{}
	for _, w := range words {
		cnt[w]++
	}
	ans, x := 0, 0
	for k, v := range cnt {
		if k[0] == k[1] {
			x += v & 1
			ans += v / 2 * 2 * 2
		} else {
			rk := string([]byte{k[1], k[0]})
			if y, ok := cnt[rk]; ok {
				ans += min(v, y) * 2
			}
		}
	}
	if x > 0 {
		ans += 2
	}
	return ans
}

力扣原题 · Doocs 题解来源