LeetCode Go · 贪心（3）

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

来源与许可

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

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

991. 坏了的计算器

中等1 种解法

标签：贪心、数学

题目、示例与约束

在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作：

• 双倍（Double）：将显示屏上的数字乘 2；
• 递减（Decrement）：将显示屏上的数字减 1 。

给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。

 

示例 1：

输入：startValue = 2, target = 3
输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.

示例 2：

输入：startValue = 5, target = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.

示例 3：

输入：startValue = 3, target = 10
输出：3
解释：先双倍，然后递减，再双倍 {3 -> 6 -> 5 -> 10}.

 

提示：

• 1 <= startValue, target <= 109

方法一：逆向计算 · Go 实现

思考

只能对当前值乘 $2$ 或减 $1$，从 $\mathit{\text{startValue}}$ 变到 $\mathit{\text{target}}$，次数最少。两数可达 ${10}^9$，正向搜索空间过大。倒推时偶数必除以 $2$，奇数只可能由减一的逆运算（加一）而来，直到不大于起点，再补上减法次数。

我们可以采用逆向计算的方式，从 $\mathit{\text{target}}$ 开始，如果 $\mathit{\text{target}}$ 是奇数，那么 $\mathit{\text{target}}=\mathit{\text{target}}+1$，否则 $\mathit{\text{target}}=\mathit{\text{target}}/2$，累加操作次数，直到 $\mathit{\text{target}}\le \mathit{\text{startValue}}$，此时的操作次数加上 $\mathit{\text{startValue}}-\mathit{\text{target}}$ 即为最终结果。

时间复杂度 $O(\log n)$，其中 $n$ 为 $\mathit{\text{target}}$。空间复杂度 $O(1)$。

func brokenCalc(startValue int, target int) (ans int) {
	for startValue < target {
		if target&1 == 1 {
			target++
		} else {
			target >>= 1
		}
		ans++
	}
	ans += startValue - target
	return
}

力扣原题 · Doocs 题解来源

1005. K 次取反后最大化的数组和

简单1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

 

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

 

提示：

• 1 <= nums.length <= 104
• -100 <= nums[i] <= 100
• 1 <= k <= 104

方法一：贪心 + 计数 · Go 实现

思考

每次取当前最小元素取反并重复 $k$ 次可以得到最优解， $n$ 与 $k$ 均不超过 ${10}^4$，但反复找最小值需要额外的选择结构。元素范围只有 $[-100,100]$，不必在原数组上排序。

为使总和最大，应优先把绝对值最大的负数翻成正数；若次数用尽后仍剩奇数次且没有 $0$，则必须再翻一次最小的正数。

用计数数组按 $-100$ 到 $-1$ 依次消耗翻转次数，再在必要时对最小正数补一次翻转，最后按频次加权求和。

我们观察发现，要使得数组的和尽可能大，就应该尽可能地将数组中的最小负数变成正数。

而题目中元素的范围为 $[-100,100]$，因此，我们可以先用哈希表 $\mathit{\text{cnt}}$ 统计数组 $\mathit{\text{nums}}$ 中每个元素出现的次数。接着从 $-100$ 开始遍历 $x$，如果哈希表中存在 $x$，那么我们取 $m=min(cnt[x],k)$ 作为元素 $x$ 取反的个数，然后我们将 $\mathit{\text{cnt}}[x]$ 减去 $m$，将 $\mathit{\text{cnt}}[-x]$ 加上 $m$，并将 $k$ 减去 $m$。如果 $k$ 为 $0$，说明操作已经结束，直接退出循环即可。

如果 $k$ 仍然为奇数，且 $\mathit{\text{cnt}}[0]=0$，那么我们还需要取 $\mathit{\text{cnt}}$ 中最小的一个正数 $x$，将 $\mathit{\text{cnt}}[x]$ 减去 $1$，将 $\mathit{\text{cnt}}[-x]$ 加上 $1$。

最后，我们遍历哈希表 $\mathit{\text{cnt}}$，将 $x$ 与 $\mathit{\text{cnt}}[x]$ 相乘的结果累加，即为答案。

时间复杂度 $O(n+M)$，空间复杂度 $O(M)$。其中 $n$ 和 $M$ 分别为数组 $\mathit{\text{nums}}$ 的长度和 $\mathit{\text{nums}}$ 的数据范围大小。

func largestSumAfterKNegations(nums []int, k int) (ans int) {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for x := -100; x < 0 && k > 0; x++ {
		if cnt[x] > 0 {
			m := min(k, cnt[x])
			cnt[x] -= m
			cnt[-x] += m
			k -= m
		}
	}
	if k&1 == 1 && cnt[0] == 0 {
		for x := 1; x <= 100; x++ {
			if cnt[x] > 0 {
				cnt[x]--
				cnt[-x]++
				break
			}
		}
	}
	for x, v := range cnt {
		ans += x * v
	}
	return
}

力扣原题 · Doocs 题解来源

1007. 行相等的最少多米诺旋转

中等1 种解法

标签：贪心、数组

题目、示例与约束

在一排多米诺骨牌中，tops[i] 和 bottoms[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）

我们可以旋转第 i 张多米诺，使得 tops[i] 和 bottoms[i] 的值交换。

返回能使 tops 中所有值或者 bottoms 中所有值都相同的最小旋转次数。

如果无法做到，返回 -1.

 

示例 1：

输入：tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
输出：2
解释： 
图一表示：在我们旋转之前， tops 和 bottoms 给出的多米诺牌。 
如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。 

示例 2：

输入：tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
输出：-1
解释： 在这种情况下，不可能旋转多米诺牌使一行的值相等。

 

提示：

• 2 <= tops.length <= 2 * 104
• bottoms.length == tops.length
• 1 <= tops[i], bottoms[i] <= 6

方法一：贪心 · Go 实现

思考

点数只有 $1$ 到 $6$，对每个候选值检查能否通过旋转铺满一行即可，长度为 $2\times {10}^4$ 时线性扫描足够。六个候选里多数会因某一列上下都不是该值而失败。

若存在一种统一的点数，它必须出现在第一列的 $tops[0]$ 或 $bottoms[0]$ 上，否则该列无法变成这个值。

因此只需对这两个候选计算 $f(x)$：任一列都不含 $x$ 则不可能；否则旋转次数为 $n$ 减去该值在上或下出现次数的较大者，取两次结果的较小值。

根据题目描述，我们知道，要使得 $tops$ 中所有值或者 $bottoms$ 中所有值都相同，那么这个值必须是 $tops[0]$ 或者 $bottoms[0]$ 中的一个。

因此，我们设计一个函数 $f(x)$，表示将所有的值都变成 $x$ 的最小旋转次数，那么答案就是 $min\{f(\mathit{\text{tops}}[0]),f(\mathit{\text{bottoms}}[0])\}$。

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

我们用两个变量 $cnt1$ 和 $cnt2$ 统计 $tops$ 和 $bottoms$ 中等于 $x$ 的个数，用 $n$ 减去它们的最大值，就是将所有值都变成 $x$ 的最小旋转次数。注意，如果 $tops$ 和 $bottoms$ 中没有等于 $x$ 的值，那么 $f(x)$ 的值就是一个很大的数，我们用 $n+1$ 表示这个数。

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

func minDominoRotations(tops []int, bottoms []int) int {
	n := len(tops)
	f := func(x int) int {
		cnt1, cnt2 := 0, 0
		for i, a := range tops {
			b := bottoms[i]
			if a != x && b != x {
				return n + 1
			}
			if a == x {
				cnt1++
			}
			if b == x {
				cnt2++
			}
		}
		return n - max(cnt1, cnt2)
	}
	ans := min(f(tops[0]), f(bottoms[0]))
	if ans > n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

1013. 将数组分成和相等的三个部分

简单1 种解法

标签：贪心、数组

题目、示例与约束

给你一个整数数组 arr，只有可以将其划分为三个和相等的 非空 部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i + 1 < j 且满足 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) 就可以将数组三等分。

 

示例 1：

输入：arr = [0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：arr = [0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例 3：

输入：arr = [3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

 

提示：

• 3 <= arr.length <= 5 * 104
• -104 <= arr[i] <= 104

方法一：遍历求和 · Go 实现

思考

枚举两处切割点使三段和相等需要 $O(n^2)$，数组长度通常达 ${10}^4$ 量级，应当避免双重扫描。三段相等当且仅当总和能被 $3$ 整除，且存在至少三段各自累加到 $s=\mathit{\text{sum}}/3$。

从左到右累加，每达到一次 $s$ 就重置并计数。多出来的段可以并入最后一部分，因此计数不少于 $3$ 即可，而不必恰好切在两个固定下标。

先判断总和模 $3$，再用一次遍历维护当前段和与段数。

我们先求出整个数组的和，然后判断和是否能被 3 整除，如果不能，直接返回 $\mathit{\text{false}}$。

否则，我们记 $\mathit{\text{s}}$ 表示每部分的和，用一个变量 $\mathit{\text{cnt}}$ 记录当前已经找到的部分数，另一个变量 $\mathit{\text{t}}$ 记录当前部分的和。初始时 $\mathit{\text{cnt}}=0$, $t=0$。

然后我们遍历数组，对于每个元素 $x$，我们将 $t$ 加上 $x$，如果 $t$ 等于 $s$，说明找到了一部分，将 $\mathit{\text{cnt}}$ 加一，然后将 $t$ 置为 0。

最后判断 $\mathit{\text{cnt}}$ 是否大于等于 3 即可。

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

func canThreePartsEqualSum(arr []int) bool {
	s := 0
	for _, x := range arr {
		s += x
	}
	if s%3 != 0 {
		return false
	}
	s /= 3
	cnt, t := 0, 0
	for _, x := range arr {
		t += x
		if t == s {
			cnt++
			t = 0
		}
	}
	return cnt >= 3
}

力扣原题 · Doocs 题解来源

1029. 两地调度

中等1 种解法

标签：贪心、数组、匈牙利算法、排序、SSP 算法

题目、示例与约束

公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。

返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

 

示例 1：

输入：costs = [[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 a 市，费用为 10。
第二个人去 a 市，费用为 30。
第三个人去 b 市，费用为 50。
第四个人去 b 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

示例 2：

输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
输出：1859

示例 3：

输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
输出：3086

 

提示：

• 2 * n == costs.length
• 2 <= costs.length <= 100
• costs.length 为偶数
• 1 <= aCosti, bCosti <= 1000

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

思考

从 $2n$ 人中选 $n$ 个去 $A$、其余去 $B$，子集枚举不可行。先让所有人去 $B$，再改派 $n$ 人去 $A$，总费用的变化是 $aCost-bCost$。

减少量越大（差值越小）的人越应该改去 $A$。按 $aCost-bCost$ 升序排序后，前 $n$ 人去 $A$、后 $n$ 人去 $B$，即为最优分配。

排序后对半求和即可。

我们不妨先假设所有人都去 $b$ 市，然后我们要从中选出 $n$ 个人去 $a$ 市，使得总费用最小。如果一个人去 $a$ 市的费用比去 $b$ 市的费用小，我们把这个人从 $b$ 市调到 $a$ 市，这样总费用就会减少。因此，我们可以将所有人按照去 $a$ 市的费用与去 $b$ 市的费用的差值从小到大排序，然后选出前 $n$ 个人去 $a$ 市，剩下的人去 $b$ 市，这样总费用就是最小的。

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

相似题目：

• 2611. 老鼠和奶酪

func twoCitySchedCost(costs [][]int) (ans int) {
	sort.Slice(costs, func(i, j int) bool {
		return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
	})
	n := len(costs) >> 1
	for i, a := range costs[:n] {
		ans += a[0] + costs[i+n][1]
	}
	return
}

力扣原题 · Doocs 题解来源

1053. 交换一次的先前排列

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。

如果无法这么操作，就请返回原数组。

 

示例 1：

输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1

示例 2：

输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列

示例 3：

输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7

 

提示：

• 1 <= arr.length <= 104
• 1 <= arr[i] <= 104

方法一：贪心 · Go 实现

思考

只允许交换一次，要得到字典序最大的更小排列。从右往左找第一处下降 $arr[i-1]>arr[i]$，该处左边的值偏大，应换成右侧某个更小的数。

为使结果尽量大，应换成右侧小于 $arr[i-1]$ 的最大数；若有重复，取最靠左的那一个，故从右扫描时跳过与前一位置相同的值。

找到后交换并返回；若无下降则已是最小排列。

我们先从右到左遍历数组，找到第一个满足 $arr[i-1]>arr[i]$ 的下标 $i$，此时 $arr[i-1]$ 就是我们要交换的数字，我们再从右到左遍历数组，找到第一个满足 $arr[j]<arr[i-1]$ 且 $arr[j]\ne arr[j-1]$ 的下标 $j$，此时我们交换 $arr[i-1]$ 和 $arr[j]$ 后返回即可。

如果遍历完数组都没有找到满足条件的下标 $i$，说明数组已经是最小排列，直接返回原数组即可。

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

func prevPermOpt1(arr []int) []int {
	n := len(arr)
	for i := n - 1; i > 0; i-- {
		if arr[i-1] > arr[i] {
			for j := n - 1; j > i-1; j-- {
				if arr[j] < arr[i-1] && arr[j] != arr[j-1] {
					arr[i-1], arr[j] = arr[j], arr[i-1]
					return arr
				}
			}
		}
	}
	return arr
}

力扣原题 · Doocs 题解来源

1054. 距离相等的条形码

中等1 种解法

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

题目、示例与约束

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

 

示例 1：

输入：barcodes = [1,1,1,2,2,2]
输出：[2,1,2,1,2,1]

示例 2：

输入：barcodes = [1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]

 

提示：

• 1 <= barcodes.length <= 10000
• 1 <= barcodes[i] <= 10000

方法一：计数 + 排序 · Go 实现

思考

相邻不能相同，出现次数最多的值不超过 $\lceil n/2\rceil$ 时一定有解。把高频值尽量隔开放，先铺偶数下标再铺奇数下标即可错开。

按频次降序、值升序排列，使相同数相邻且高频在前，再把前一半写入偶数位、后一半写入奇数位。

这样最频繁的值优先占据相隔的偶数槽，不会与自己相邻。

我们先用哈希表或数组 $cnt$ 统计数组 $barcodes$ 中各个数出现的次数，然后将 $barcodes$ 中的数按照它们在 $cnt$ 中出现的次数从大到小排序，如果出现次数相同，那么就按照数的大小从小到大排序（确保相同的数相邻）。

接下来，我们创建一个长度为 $n$ 的答案数组 $ans$，然后遍历排好序的 $barcodes$，将元素依次填入答案数组的 $0,2,4,\cdots$ 等偶数下标位置，然后将剩余元素依次填入答案数组的 $1,3,5,\cdots$ 等奇数下标位置即可。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(M)$。其中 $n$ 和 $M$ 分别是数组 $barcodes$ 的长度以及数组 $barcodes$ 中的最大值。

func rearrangeBarcodes(barcodes []int) []int {
	mx := slices.Max(barcodes)
	cnt := make([]int, mx+1)
	for _, x := range barcodes {
		cnt[x]++
	}
	sort.Slice(barcodes, func(i, j int) bool {
		a, b := barcodes[i], barcodes[j]
		if cnt[a] == cnt[b] {
			return a < b
		}
		return cnt[a] > cnt[b]
	})
	n := len(barcodes)
	ans := make([]int, n)
	for k, j := 0, 0; k < 2; k++ {
		for i := k; i < n; i, j = i+2, j+1 {
			ans[i] = barcodes[j]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1055. 形成字符串的最短路径 🔒

中等1 种解法

标签：贪心、双指针、字符串、二分查找

题目、示例与约束

对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的 子序列 。(例如，“ace” 是 “abcde” 的子序列，而 “aec” 不是)。

给定源字符串 source 和目标字符串 target，返回 源字符串 source 中能通过串联形成目标字符串 target 的 子序列 的最小数量 。如果无法通过串联源字符串中的子序列来构造目标字符串，则返回 -1。

 

示例 1：

输入：source = "abc", target = "abcbc"
输出：2
解释：目标字符串 "abcbc" 可以由 "abc" 和 "bc" 形成，它们都是源字符串 "abc" 的子序列。

示例 2：

输入：source = "abc", target = "acdbc"
输出：-1
解释：由于目标字符串中包含字符 "d"，所以无法由源字符串的子序列构建目标字符串。

示例 3：

输入：source = "xyz", target = "xzyxz"
输出：3
解释：目标字符串可以按如下方式构建： "xz" + "y" + "xz"。

 

提示：

• 1 <= source.length, target.length <= 1000
• source 和 target 仅包含英文小写字母。

方法一：双指针 · Go 实现

思考

把 $target$ 拆成最少段，每段都是 $source$ 的子序列。 $m,n\le 1000$，可对每一段在 $source$ 上走一遍双指针。

从 $target$ 的当前位置 $j$ 出发，在 $source$ 上尽量多匹配；若一轮结束后 $j$ 没有前进，则 $source$ 缺少某个字符，无解。否则段数加一，继续。

直到 $j$ 走到 $n$。

我们可以使用双指针的方法，用指针 $j$ 指向目标字符串 target，然后遍历源字符串 source，用指针 $i$ 指向源字符串 source，如果 $source[i]=target[j]$，则 $i$ 和 $j$ 同时向后移动一位，否则只移动 $i$ 指针。当指针 $i$ 和 $j$ 都到达字符串末尾时，如果没有找到相等的字符，则返回 $-1$，否则子序列数量加一，然后将指针 $i$ 置为 $0$，继续遍历。

遍历结束后，返回子序列数量即可。

时间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别为字符串 source 和 target 的长度。空间复杂度 $O(1)$。

func shortestWay(source string, target string) int {
	m, n := len(source), len(target)
	ans, j := 0, 0
	for j < n {
		ok := false
		for i := 0; i < m && j < n; i++ {
			if source[i] == target[j] {
				ok = true
				j++
			}
		}
		if !ok {
			return -1
		}
		ans++
	}
	return ans
}

力扣原题 · Doocs 题解来源

1058. 最小化舍入误差以满足目标 🔒

中等1 种解法

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

题目、示例与约束

给定一系列价格 [p1,p2...,pn] 和一个目标 target，将每个价格 pi 舍入为 Roundi(pi) 以使得舍入数组 [Round1(p1),Round2(p2)...,Roundn(pn)] 之和达到给定的目标值 target。每次舍入操作 Roundi(pi) 可以是向下舍 Floor(pi) 也可以是向上入 Ceil(pi)。

如果舍入数组之和无论如何都无法达到目标值 target，就返回字符串 "-1"。否则，以保留到小数点后三位的字符串格式返回最小的舍入误差，其定义为 Σ |Roundi(pi) - (pi)|（ i 从 1 到 n ）。

 

示例 1：

输入：prices = ["0.700","2.800","4.900"], target = 8
输出："1.000"
解释： 
使用 Floor，Ceil 和 Ceil 操作得到 (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 。

示例 2：

输入：prices = ["1.500","2.500","3.500"], target = 10
输出："-1"
解释：
达到目标是不可能的。

示例 3：

输入：prices = ["1.500","2.500","3.500"], target = 9
输出："1.500"

 

提示：

• 1 <= prices.length <= 500
• 表示价格的每个字符串 prices[i] 都代表一个介于 [0.0, 1000.0] 之间的实数，并且正好有 3 个小数位。
• target 介于 0 和 1000000 之间。

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

思考

每个价格可下取整或（小数非零时）上取整，误差为与原价的距离。全部下取整之和为 $\mathit{\text{mi}}$，可上取整的个数为小数非零的个数，目标必须落在该闭区间内。

需要上取整 $d=\mathit{\text{target}}-\mathit{\text{mi}}$ 个。上取整误差为 $1-\{p\}$，下取整误差为 $\{p\}$，因此应优先给小数部分最大的 $d$ 个做上取整。

把小数部分降序排序后按此计算总误差，保留三位小数。

遍历价格数组 prices，先将每个价格 $p$ 向下舍入，累加到 mi 中，同时将每个价格的小数点部分添加到数组 arr 中。

遍历结束后，判断 target 是否在 mi 和 mi + arr.length 之间，如果不在，直接返回 "-1"。

接下来，我们计算 target - mi，即需要向上入的价格个数，然后将 arr 从大到小排序，从前往后遍历，将前 target - mi 个价格向上入，其余价格向下舍入，累计到 ans 中。

时间复杂度 $O(n\log n)$。其中 $n$ 为 prices 的长度。

func minimizeError(prices []string, target int) string {
	arr := []float64{}
	mi := 0
	for _, p := range prices {
		price, _ := strconv.ParseFloat(p, 64)
		mi += int(math.Floor(price))
		d := price - float64(math.Floor(price))
		if d > 0 {
			arr = append(arr, d)
		}
	}
	if target < mi || target > mi+len(arr) {
		return "-1"
	}
	d := target - mi
	sort.Float64s(arr)
	ans := float64(d)
	for i := 0; i < d; i++ {
		ans -= arr[len(arr)-i-1]
	}
	for i := d; i < len(arr); i++ {
		ans += arr[len(arr)-i-1]
	}
	return fmt.Sprintf("%.3f", ans)
}

力扣原题 · Doocs 题解来源

1081. 不同字符的最小子序列

中等1 种解法

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

题目、示例与约束

返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

 

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

 

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

 

注意：该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同

方法一：栈 · Go 实现

思考

要在保持相对顺序的前提下让每种字符各出现一次且字典序最小。 $n\le 1000$，可用单调栈：后面还会再出现的较大栈顶可以弹出。

记下每个字符最后出现下标。从左扫描，已在栈中则跳过；否则弹出栈顶中「比当前大且后面还有」的字符，再压入当前字符。

用集合记录栈内字符，避免重复入栈。栈中顺序即为答案。

我们用一个数组 $last$ 记录字符串 $s$ 每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 $vis$ 或者一个整型变量 $mask$ 记录当前字符是否在栈中。

遍历字符串 $s$，对于每个字符 $c$，如果 $c$ 不在栈中，我们就需要判断栈顶元素是否大于 $c$，如果大于 $c$，且栈顶元素在后面还会出现，我们就将栈顶元素弹出，将 $c$ 压入栈中。

最后将栈中元素拼接成字符串作为结果返回。

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

func smallestSubsequence(s string) string {
	last := make([]int, 26)
	for i, c := range s {
		last[c-'a'] = i
	}
	stk := []rune{}
	vis := make([]bool, 128)
	for i, c := range s {
		if vis[c] {
			continue
		}
		for len(stk) > 0 && stk[len(stk)-1] > c && last[stk[len(stk)-1]-'a'] > i {
			vis[stk[len(stk)-1]] = false
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, c)
		vis[c] = true
	}
	return string(stk)
}

力扣原题 · Doocs 题解来源

1090. 受标签影响的最大值

中等1 种解法

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

题目、示例与约束

以两个整数数组  values 和 labels 给定 n 个项的值和标签，并且给出两个整数 numWanted 和 useLimit 。

你的任务是从这些项中找到一个值的和 最大 的子集使得：

• 项的数量 最多 为 numWanted。
• 相同标签的项的数量 最多 为 useLimit。

返回最大的和。

 

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1

输出：9

解释：

选择的子集是第一个、第三个和第五个项，其值之和为 5 + 3 + 1。

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2

输出：12

解释：

选择的子集是第一个、第二个和第三个项，其值之和为 5 + 4 + 3。

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1

输出：16

解释：

选择的子集是第一个和第四个项，其值之和为 9 + 7。

 

提示：

• n == values.length == labels.length
• 1 <= n <= 2 * 104
• 0 <= values[i], labels[i] <= 2 * 104
• 1 <= numWanted, useLimit <= n

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

思考

子集大小不超过 $\mathit{\text{numWanted}}$，同一标签至多 $\mathit{\text{useLimit}}$ 次，要值和最大。应优先取数值大的项，并用计数卡住标签配额。 $n\le 2\times {10}^4$，排序后线性挑选即可。

把 $(value,label)$ 按值降序，扫描时若该标签未达上限则选入，直到选满 $\mathit{\text{numWanted}}$。

哈希表 $cnt$ 记录各标签已用次数。

根据题目描述，我们需要从 $n$ 个元素的集合中选出一个子集，子集元素个数不超过 $numWanted$，且子集中最多有相同标签的 $useLimit$ 项，使得子集的值之和最大。因此，我们应该贪心地选择集合中值较大的元素，同时记录每个标签出现的次数，当某个标签出现的次数达到 $useLimit$ 时，我们就不能再选择该标签对应的元素了。

具体地，我们先将集合中的元素按照值从大到小进行排序，然后从前向后遍历排序后的元素。在遍历的过程中，我们使用一个哈希表 $cnt$ 记录每个标签出现的次数，如果某个标签出现的次数达到了 $useLimit$，那么我们就跳过该元素，否则我们就将该元素的值加到最终的答案中，并将该标签出现的次数加 $1$。同时，我们用一个变量 $num$ 记录当前子集中的元素个数，当 $num$ 达到 $numWanted$ 时，我们就可以结束遍历了。

遍历结束后，我们就得到了最大的分数。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是集合中的元素个数。

func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) (ans int) {
	n := len(values)
	pairs := make([][2]int, n)
	for i := 0; i < n; i++ {
		pairs[i] = [2]int{values[i], labels[i]}
	}
	sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] > pairs[j][0] })
	cnt := map[int]int{}
	for i, num := 0, 0; i < n && num < numWanted; i++ {
		v, l := pairs[i][0], pairs[i][1]
		if cnt[l] < useLimit {
			cnt[l]++
			num++
			ans += v
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1144. 递减元素使数组呈锯齿状

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

• 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
• 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

 

示例 1：

输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。

示例 2：

输入：nums = [9,6,1,6,2]
输出：4

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

方法一：枚举 + 贪心 · Go 实现

思考

只能减小元素，锯齿有「偶数位较小」与「奇数位较小」两种形态，二者互斥，分别计算后取较小操作次数。对需要变小的位置，操作次数由它与左右邻居的差值决定，取能同时低于两侧的最小值即可，互不影响。

我们可以分别枚举偶数位和奇数位作为“比相邻元素小”的元素，然后计算需要的操作次数。取两者的最小值即可。

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

func movesToMakeZigzag(nums []int) int {
	ans := [2]int{}
	n := len(nums)
	for i := 0; i < 2; i++ {
		for j := i; j < n; j += 2 {
			d := 0
			if j > 0 {
				d = max(d, nums[j]-nums[j-1]+1)
			}
			if j < n-1 {
				d = max(d, nums[j]-nums[j+1]+1)
			}
			ans[i] += d
		}
	}
	return min(ans[0], ans[1])
}

力扣原题 · Doocs 题解来源

1167. 连接木棍的最低费用 🔒

中等1 种解法

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

题目、示例与约束

你有一些长度为正整数的木棍。这些长度以数组 sticks 的形式给出， sticks[i] 是第 i 个木棍的长度。

你可以通过支付 x + y 的成本将任意两个长度为 x 和 y 的木棍连接成一个木棍。你必须连接所有的木棍，直到剩下一个木棍。

返回以这种方式将所有给定的木棍连接成一个木棍的 最小成本 。

 

示例 1：

输入：sticks = [2,4,3]
输出：14
解释：从 sticks = [2,4,3] 开始。
1. 连接 2 和 3 ，费用为 2 + 3 = 5 。现在 sticks = [5,4]
2. 连接 5 和 4 ，费用为 5 + 4 = 9 。现在 sticks = [9]
所有木棍已经连成一根，总费用 5 + 9 = 14

示例 2：

输入：sticks = [1,8,3,5]
输出：30
解释：从 sticks = [1,8,3,5] 开始。
1. 连接 1 和 3 ，费用为 1 + 3 = 4 。现在 sticks = [4,8,5]
2. 连接 4 和 5 ，费用为 4 + 5 = 9 。现在 sticks = [9,8]
3. 连接 9 和 8 ，费用为 9 + 8 = 17 。现在 sticks = [17]
所有木棍已经连成一根，总费用 4 + 9 + 17 = 30

示例 3：

输入：sticks = [5]
输出：0
解释：只有一根木棍，不必再连接。总费用 0

 

提示：

• 1 <= sticks.length <= 104
• 1 <= sticks[i] <= 104

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

思考

合并两根木棍的费用等于长度之和，且新棍会再次参与合并，较长的棍被反复计入。每次选当前最短的两根合并，可使大长度少出现在后续和中。小根堆维护当前长度，弹出两根、压入其和，直到剩一根，累加每次合并费用。

我们可以使用贪心的思路，每次选择最短的两根棍子进行拼接，这样可以保证拼接的代价最小。

因此，我们可以使用优先队列（小根堆）来维护当前棍子的长度，每次从优先队列中取出两根棍子进行拼接，再将拼接后的棍子放回优先队列中，直到优先队列中只剩下一根棍子为止。

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

func connectSticks(sticks []int) (ans int) {
	hp := &hp{sticks}
	heap.Init(hp)
	for hp.Len() > 1 {
		x, y := heap.Pop(hp).(int), heap.Pop(hp).(int)
		ans += x + y
		heap.Push(hp, x+y)
	}
	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
}

力扣原题 · Doocs 题解来源

1183. 矩阵中 1 的最大数量 🔒

困难1 种解法

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

题目、示例与约束

现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。

而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。

请你设计一个算法，计算矩阵中最多可以有多少个 1。

 

示例 1：

输入：width = 3, height = 3, sideLength = 2, maxOnes = 1
输出：4
解释：
题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。
最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：
[1,0,1]
[0,0,0]
[1,0,1]

示例 2：

输入：width = 3, height = 3, sideLength = 2, maxOnes = 2
输出：6
解释：
[1,0,1]
[1,0,1]
[1,0,1]

 

提示：

• 1 <= width, height <= 100
• 1 <= sideLength <= width, height
• 0 <= maxOnes <= sideLength * sideLength

方法一：统计等效位置 · Go 实现

思考

矩阵由 $sideLength\times sideLength$ 的图案平铺，且每个图案中 $1$ 的个数不超过 $maxOnes$。位置 $(i,j)$ 与 $(imodx,jmodx)$ 同步，该 residual 在全图中出现的次数即放 $1$ 的收益。统计 $x^2$ 个 residual 的出现次数，取最大的 $maxOnes$ 个之和。

为了方便说明，我们不妨令 $x=sideLength$。

考虑一个 $x\times x$ 的正方形，我们需要在正方形里面取最多 $maxOnes$ 个点，将其置为 1。注意到当坐标 $(i,j)$ 处的点被选取后，所有坐标为 $(i\pm k_1\times x,j\pm k_2\times x)$ 的点都可以等效地置为 1。因此，我们算出坐标 $(i,j)$ 在矩阵中的等效位置的数量，取数量最多的前 $maxOnes$ 个即可。

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

func maximumNumberOfOnes(width int, height int, sideLength int, maxOnes int) int {
	x := sideLength
	cnt := make([]int, x*x)
	for i := 0; i < width; i++ {
		for j := 0; j < height; j++ {
			k := (i%x)*x + (j % x)
			cnt[k]++
		}
	}
	sort.Ints(cnt)
	ans := 0
	for i := range cnt[:maxOnes] {
		ans += cnt[len(cnt)-i-1]
	}
	return ans
}

力扣原题 · Doocs 题解来源

1196. 最多可以买到的苹果数量 🔒

简单1 种解法

标签：贪心、数组、排序

题目、示例与约束

你有一些苹果和一个可以承载 5000 单位重量的篮子。

给定一个整数数组 weight ，其中 weight[i] 是第 i 个苹果的重量，返回 你可以放入篮子的最大苹果数量 。

 

示例 1：

输入：weight = [100,200,150,1000]
输出：4
解释：所有 4 个苹果都可以装进去，因为它们的重量之和为 1450。

示例 2：

输入：weight = [900,950,800,1000,700,800]
输出：5
解释：6 个苹果的总重量超过了 5000，所以我们只能从中任选 5 个。

 

提示：

• 1 <= weight.length <= 103
• 1 <= weight[i] <= 103

方法一：贪心 · Go 实现

思考

篮重上限 $5000$，个数最多则应优先装更轻的苹果。排序后从小到大累加，一旦超过上限返回已装个数；全部能装下则返回 $n$。

要使得苹果数量最多，那么就要使得苹果的重量尽可能的小，因此我们可以对苹果的重量进行排序，然后从小到大依次放入篮子中，直到篮子的重量超过 $5000$ 为止，返回此时放入篮子的苹果数量。

如果所有的苹果都能放入篮子中，那么就返回苹果的数量。

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

func maxNumberOfApples(weight []int) int {
	sort.Ints(weight)
	s := 0
	for i, x := range weight {
		s += x
		if s > 5000 {
			return i
		}
	}
	return len(weight)
}

力扣原题 · Doocs 题解来源

1199. 建造街区的最短时间 🔒

困难1 种解法

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

题目、示例与约束

你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第  i 个街区需要 t 个单位的时间来建造。

由于一个街区只能由一个工人来完成建造。

所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。

一个工人再召唤一个工人所花费的时间由整数 split 给出。

注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。

最开始的时候只有 一个 工人，请你最后输出建造完所有街区所需要的最少时间。

 

示例 1：

输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。

示例 2：

输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7

示例 3：

输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4

 

提示：

1. 1 <= blocks.length <= 1000
2. 1 <= blocks[i] <= 10^5
3. 1 <= split <= 100

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

思考

工人可分裂，分裂耗时 $split$ 后两人并行。正向枚举分裂方案不易。逆向把两座街区合并：新街区耗时为 $split+max(t_i,t_j)$，等价于先分裂再并行建造。每次合并当前最短的两座，使大耗时少参与后续 $split$，小根堆重复该过程直至剩一座，其时间即为最少工期。

先考虑只有一个街区的情况，此时不需要分裂工人，直接让他去建造街区，时间花费为 $\mathit{\text{block}}[0]$。

如果有两个街区，此时需要把工人分裂为两个，然后让他们分别去建造街区，时间花费为 $\mathit{\text{split}}+max(\mathit{\text{block}}[0],\mathit{\text{block}}[1])$。

如果有超过两个街区，此时每一步都需要考虑将几个工人进行分裂，正向思维不好处理。

我们不妨采用逆向思维，不分裂工人，而是将街区进行合并。我们选取任意两个街区 $i$, $j$ 进行合并，建造一个新的街区的时间为 $\mathit{\text{split}}+max(\mathit{\text{block}}[i],\mathit{\text{block}}[j])$。

为了让耗时长的街区尽可能少参与到合并中，我们可以每次贪心地选取耗时最小的两个街区进行合并。因此，我们可以维护一个小根堆，每次取出最小的两个街区进行合并，直到只剩下一个街区。最后剩下的这个街区的建造时间就是答案。

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

func minBuildTime(blocks []int, split int) int {
	q := hp{}
	for _, v := range blocks {
		heap.Push(&q, v)
	}
	for q.Len() > 1 {
		heap.Pop(&q)
		heap.Push(&q, heap.Pop(&q).(int)+split)
	}
	return q.IntSlice[0]
}

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 题解来源

1217. 玩筹码

简单1 种解法

标签：贪心、数组、数学

题目、示例与约束

有 n 个筹码。第 i 个筹码的位置是 position[i] 。

我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:

• position[i] + 2 或 position[i] - 2 ，此时 cost = 0
• position[i] + 1 或 position[i] - 1 ，此时 cost = 1

返回将所有筹码移动到同一位置上所需要的 最小代价 。

 

示例 1：

输入：position = [1,2,3]
输出：1
解释：第一步:将位置3的筹码移动到位置1，成本为0。
第二步:将位置2的筹码移动到位置1，成本= 1。
总成本是1。

示例 2：

输入：position = [2,2,2,3,3]
输出：2
解释：我们可以把位置3的两个筹码移到位置2。每一步的成本为1。总成本= 2。

示例 3:

输入：position = [1,1000000000]
输出：1

 

提示：

• 1 <= position.length <= 100
• 1 <= position[i] <= 10^9

方法一：脑筋急转弯 · Go 实现

思考

移动 $2$ 步代价为 $0$，故所有偶数位互通、所有奇数位互通，且互迁代价为 $0$。真正要付费的只有奇偶之间的一步移动，代价为 $1$。

因此只需把所有筹码先免费聚到某个偶数位和某个奇数位，再把较少的一堆移到另一堆。答案即奇数个数与偶数个数的较小者。

将所有偶数下标的芯片移动到 0 号位置，所有奇数下标的芯片移动到 1 号位置，所有的代价为 0，接下来只需要在 0/1 号位置中选择其中一个较小数量的芯片，移动到另一个位置。所需的最小代价就是那个较小的数量。

时间复杂度 $O(n)$，其中 $n$ 为芯片的数量。空间复杂度 $O(1)$。

func minCostToMoveChips(position []int) int {
	a := 0
	for _, p := range position {
		a += p & 1
	}
	b := len(position) - a
	if a < b {
		return a
	}
	return b
}

力扣原题 · Doocs 题解来源

1221. 分割平衡字符串

简单1 种解法

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

题目、示例与约束

平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：

• 每个子字符串都是平衡字符串。

返回可以通过分割得到的平衡字符串的 最大数量 。

 

示例 1：

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 2：

输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR" 。

 

提示：

• 2 <= s.length <= 1000
• s[i] = 'L' 或 'R'
• s 是一个 平衡 字符串

方法一：贪心 · Go 实现

思考

题目保证整串平衡，并求最多切成多少个平衡子串。尽可能早地切开不会妨碍后面再切：每多切一刀答案加一，且剩余后缀仍是平衡串。

用计数器记录 $L$ 与 $R$ 的差额，归零即得到一段平衡前缀，计入答案并继续。贪心切分与计数器同步，一遍线性完成。

我们用变量 $l$ 维护当前字符串的平衡度，即 $l$ 的值为当前字符串中 $L$ 的数量减去 $R$ 的数量。当 $l$ 的值为 0 时，我们就找到了一个平衡字符串。

遍历字符串 $s$，当遍历到第 $i$ 个字符时，如果 $s[i]=L$，则 $l$ 的值加 1，否则 $l$ 的值减 1。当 $l$ 的值为 0 时，我们将答案加 1。

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

func balancedStringSplit(s string) int {
	ans, l := 0, 0
	for _, c := range s {
		if c == 'L' {
			l++
		} else {
			l--
		}
		if l == 0 {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1247. 交换字符使得字符串相同

中等1 种解法

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

题目、示例与约束

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

 

示例 1：

输入：s1 = "xx", s2 = "yy"
输出：1
解释：
交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：

输入：s1 = "xy", s2 = "yx"
输出：2
解释：
交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：

输入：s1 = "xx", s2 = "xy"
输出：-1

 

提示：

• 1 <= s1.length, s2.length <= 1000
• s1.length == s2.length
• s1, s2 只包含 'x' 或 'y'。

方法一：贪心 · Go 实现

思考

对应位置相同则无需交换。错位只有 $xy$ 与 $yx$ 两种。两次同类错位一次交换即可对调；一奇一偶的一对需要两次交换；总数为奇数则无解。

统计两类个数，奇偶性不合法返回 $-1$，否则答案为各自折半再加上至多一对跨类交换。贪心配对不依赖具体位置。

根据题目描述，两个字符串 $s_1$ 和 $s_2$ 都只包含字符 $x$ 和 $y$，且长度相同，因此可以将 $s_1$ 和 $s_2$ 中的字符一一对应起来，即 $s_1[i]$ 和 $s_2[i]$。

如果 $s_1[i]=s_2[i]$，则不需要交换，直接跳过即可。如果 $s_1[i]\ne s_2[i]$，则需要交换，我们统计 $s_1[i]$ 和 $s_2[i]$ 的组合情况，即 $s_1[i]=x$ 且 $s_2[i]=y$ 的情况，记为 $xy$，对于 $s_1[i]=y$ 且 $s_2[i]=x$ 的情况，记为 $yx$。

如果 $xy+yx$ 为奇数，则无法完成交换，返回 $-1$。如果 $xy+yx$ 为偶数，则需要交换的次数为 $\lfloor \frac{x}{2}\rfloor$ + $\lfloor \frac{y}{2}\rfloor$ + $xymod2$ + $yxmod2$。

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

func minimumSwap(s1 string, s2 string) int {
	xy, yx := 0, 0
	for i := range s1 {
		if s1[i] < s2[i] {
			xy++
		}
		if s1[i] > s2[i] {
			yx++
		}
	}
	if (xy+yx)%2 == 1 {
		return -1
	}
	return xy/2 + yx/2 + xy%2 + yx%2
}

力扣原题 · Doocs 题解来源

1253. 重构 2 行二进制矩阵

中等1 种解法

标签：贪心、数组、矩阵

题目、示例与约束

给你一个 2 行 n 列的二进制数组：

• 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
• 第 0 行的元素之和为 upper。
• 第 1 行的元素之和为 lower。
• 第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。

如果有多个不同的答案，那么任意一个都可以通过本题。

如果不存在符合要求的答案，就请返回一个空的二维数组。

 

示例 1：

输入：upper = 2, lower = 1, colsum = [1,1,1]
输出：[[1,1,0],[0,0,1]]
解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。

示例 2：

输入：upper = 2, lower = 3, colsum = [2,2,1,1]
输出：[]

示例 3：

输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

 

提示：

• 1 <= colsum.length <= 10^5
• 0 <= upper, lower <= colsum.length
• 0 <= colsum[i] <= 2

方法一：贪心 · Go 实现

思考

两行矩阵的列和给定，且两行 $1$ 的个数分别为 $upper$、 $lower$。 $n\le {10}^5$，回溯不可行。列为 $2$ 时两行都只能填 $1$；为 $0$ 时都填 $0$；为 $1$ 时必须把仅剩的 $1$ 给当前余额更多的那一行，否则稍后可能不够用。

从左到右按此规则填写，余额变负或结束时两行余额未用尽则无解。贪心把 $1$ 留给更紧的行，局部选择不增加全局冲突。

我们先创建一个答案数组 $ans$，其中 $ans[0]$ 和 $ans[1]$ 分别表示矩阵的第一行和第二行。

接下来，从左到右遍历数组 $colsum$，对于当前遍历到的元素 $colsum[j]$，我们有以下几种情况：

• 如果 $colsum[j]=2$，那么我们将 $ans[0][j]$ 和 $ans[1][j]$ 都置为 $1$。此时 $upper$ 和 $lower$ 都减去 $1$。
• 如果 $colsum[j]=1$，那么我们将 $ans[0][j]$ 或 $ans[1][j]$ 置为 $1$。如果 $upper>lower$，那么我们优先将 $ans[0][j]$ 置为 $1$，否则我们优先将 $ans[1][j]$ 置为 $1$。此时 $upper$ 或 $lower$ 减去 $1$。
• 如果 $colsum[j]=0$，那么我们将 $ans[0][j]$ 和 $ans[1][j]$ 都置为 $0$。
• 如果 $upper<0$ 或 $lower<0$，那么说明无法构造出满足要求的矩阵，我们返回一个空数组。

遍历结束，如果 $upper$ 和 $lower$ 都为 $0$，那么我们返回 $ans$，否则我们返回一个空数组。

时间复杂度 $O(n)$，其中 $n$ 是数组 $colsum$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
	n := len(colsum)
	ans := make([][]int, 2)
	for i := range ans {
		ans[i] = make([]int, n)
	}
	for j, v := range colsum {
		if v == 2 {
			ans[0][j], ans[1][j] = 1, 1
			upper--
			lower--
		}
		if v == 1 {
			if upper > lower {
				upper--
				ans[0][j] = 1
			} else {
				lower--
				ans[1][j] = 1
			}
		}
		if upper < 0 || lower < 0 {
			break
		}
	}
	if upper != 0 || lower != 0 {
		return [][]int{}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1282. 用户分组

中等1 种解法

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

题目、示例与约束

有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一ID 。

给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。

返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。

每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。

 

示例 1：

输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释：
第一组是 [5]，大小为 1，groupSizes[5] = 1。
第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。 
其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。

示例 2：

输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]

 

提示：

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

方法一：哈希表或数组 · Go 实现

思考

同一组大小的人必须恰好填满若干组。 $n\le 500$，按 $groupSize$ 把人收集到哈希表，再把每张名单切成该大小的连续片段。题目保证有解，切分即可。

我们用一个哈希表 $g$ 来存放每个 $groupSize$ 都有哪些人。然后对每个 $groupSize$ 中的人划分为 $k$ 等份，每一等份有 $groupSize$ 个人。

由于题目中的 $n$ 范围较小，我们也可以直接创建一个大小为 $n+1$ 的数组来存放数据，运行效率较高。

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

func groupThePeople(groupSizes []int) [][]int {
	n := len(groupSizes)
	g := make([][]int, n+1)
	for i, v := range groupSizes {
		g[v] = append(g[v], i)
	}
	ans := [][]int{}
	for i, v := range g {
		for j := 0; j < len(v); j += i {
			ans = append(ans, v[j:j+i])
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1296. 划分数组为连续数字的集合

中等2 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
如果可以，请返回 true；否则，返回 false。

 

示例 1：

输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

示例 2：

输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

示例 4：

输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。

 

提示：

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

 

注意：此题目与 846 重复：https://leetcode.cn/problems/hand-of-straights/

方法一：哈希表 + 排序 · Go 实现

思考

要把数组分成若干长度为 $k$ 的连续段。长度不能被 $k$ 整除则无解。 $n\le {10}^5$，从最小剩余值开始贪心取 $k$ 个连续数：若某值次数不够则失败。

计数后按值排序扫描，遇到仍有剩余的 $x$ 就对 $[x,x+k)$ 各减一。排序保证每次从当前最小缺口开始，避免打乱后续段。

我们首先判断数组 $\mathit{\text{nums}}$ 的长度是否能被 $\mathit{\text{k}}$ 整除，如果不能整除，说明无法将数组划分成若干个长度为 $\mathit{\text{k}}$ 的子数组，直接返回 $\text{false}$。

接下来，我们用一个哈希表 $\mathit{\text{cnt}}$ 统计数组 $\mathit{\text{nums}}$ 中每个数字出现的次数，然后对数组 $\mathit{\text{nums}}$ 进行排序。

然后，我们遍历排序后的数组 $\mathit{\text{nums}}$，对于每个数字 $x$，如果 $\mathit{\text{cnt}}[x]$ 不为 $0$，我们枚举 $x$ 到 $x+\mathit{\text{k}}-1$ 的每个数字 $y$，如果 $\mathit{\text{cnt}}[y]$ 为 $0$，说明无法将数组划分成若干个长度为 $\mathit{\text{k}}$ 的子数组，直接返回 $\text{false}$。否则，我们将 $\mathit{\text{cnt}}[y]$ 减 $1$。

遍历结束后，说明可以将数组划分成若干个长度为 $\mathit{\text{k}}$ 的子数组，返回 $\text{true}$。

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

func isPossibleDivide(nums []int, k int) bool {
	if len(nums)%k != 0 {
		return false
	}
	sort.Ints(nums)
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for _, x := range nums {
		if cnt[x] > 0 {
			for y := x; y < x+k; y++ {
				if cnt[y] == 0 {
					return false
				}
				cnt[y]--
			}
		}
	}
	return true
}

方法二：有序集合 · Go 实现

思考

方法一排序整阵并反复查哈希。有序字典按键维护剩余次数，每次取最小键开新段，次数降到零则删除。不必对重复元素排序，取最小是 $O(\log n)$。

与方法一类似，我们首先判断数组 $\mathit{\text{nums}}$ 的长度是否能被 $\mathit{\text{k}}$ 整除，如果不能整除，说明无法将数组划分成若干个长度为 $\mathit{\text{k}}$ 的子数组，直接返回 $\text{false}$。

接下来，我们用一个有序集合 $\mathit{\text{sd}}$ 统计数组 $\mathit{\text{nums}}$ 中每个数字出现的次数。

然后，我们循环取出有序集合中的最小值 $x$，然后枚举 $x$ 到 $x+\mathit{\text{k}}-1$ 的每个数字 $y$，如果这些数字在有序集合中出现的次数都不为 $0$，则我们将这些数字的出现次数减 $1$，如果出现次数减 $1$ 后为 $0$，则将该数字从有序集合中删除，否则说明无法将数组划分成若干个长度为 $\mathit{\text{k}}$ 的子数组，返回 $\text{false}$。如果可以将数组划分成若干个长度为 $\mathit{\text{k}}$ 的子数组，则遍历结束后返回 $\text{true}$。

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

func isPossibleDivide(nums []int, k int) bool {
	if len(nums)%k != 0 {
		return false
	}
	tm := treemap.NewWithIntComparator()
	for _, x := range nums {
		if v, ok := tm.Get(x); ok {
			tm.Put(x, v.(int)+1)
		} else {
			tm.Put(x, 1)
		}
	}
	for !tm.Empty() {
		x, _ := tm.Min()
		for y := x.(int); y < x.(int)+k; y++ {
			if v, ok := tm.Get(y); ok {
				if v.(int) == 1 {
					tm.Remove(y)
				} else {
					tm.Put(y, v.(int)-1)
				}
			} else {
				return false
			}
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1323. 6 和 9 组成的最大数字

简单1 种解法

标签：贪心、数学

题目、示例与约束

给你一个仅由数字 6 和 9 组成的正整数 num。

你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。

请返回你可以得到的最大数字。

 

示例 1：

输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。

示例 2：

输入：num = 9996
输出：9999
解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。

示例 3：

输入：num = 9999
输出：9999
解释：无需改变就已经是最大的数字了。

 

提示：

• 1 <= num <= 10^4
• num 每一位上的数字都是 6 或者 9 。

方法一：贪心 · Go 实现

思考

只能把 $6$ 改成 $9$，改一处后要让数值最大。高位的提升大于低位，因此把最左边的 $6$ 换成 $9$ 即可；若没有 $6$，原数已是最大。字符串上只替换首次出现的 '6' 与这一观察一致。

我们将数组转换为字符串，然后从左到右遍历字符串，找到第一个出现的 $6$，将其替换为 $9$，然后返回转换后的字符串对应的整数即可。

时间复杂度 $O(\log \mathit{\text{num}})$，空间复杂度 $O(\log \mathit{\text{num}})$。其中 $\mathit{\text{num}}$ 为给定的整数。

func maximum69Number(num int) int {
	s := strings.Replace(strconv.Itoa(num), "6", "9", 1)
	ans, _ := strconv.Atoi(s)
	return ans
}

力扣原题 · Doocs 题解来源

1328. 破坏回文串

中等1 种解法

标签：贪心、字符串

题目、示例与约束

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

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

方法一：贪心 · Go 实现

思考

改动恰好一个字符，使结果不是回文且字典序最小；长度为 $1$ 时无法做到。在前半段把某个非 'a' 改成 'a' 既破坏对称，又尽量靠左、尽量变小。若前半全是 'a'，只能把最后一个字符改成 'b'，否则改完仍是回文。

我们先判断字符串的长度是否为 $1$，若是则直接返回空串。

否则，我们从左到右遍历字符串的前半部分，找到第一个不为 'a' 的字符，将其改为 'a' 即可。如果不存在这样的字符，那么我们将最后一个字符改为 'b' 即可。

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

func breakPalindrome(palindrome string) string {
	n := len(palindrome)
	if n == 1 {
		return ""
	}
	i := 0
	s := []byte(palindrome)
	for i < n/2 && s[i] == 'a' {
		i++
	}
	if i == n/2 {
		s[n-1] = 'b'
	} else {
		s[i] = 'a'
	}
	return string(s)
}

力扣原题 · Doocs 题解来源

1330. 翻转子数组得到最大的数组值

困难1 种解法

标签：贪心、数组、数学

题目、示例与约束

给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。

你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。

请你找到可行的最大 数组值 。

 

示例 1：

输入：nums = [2,3,1,5,4]
输出：10
解释：通过翻转子数组 [3,1,5] ，数组变成 [2,5,1,3,4] ，数组值为 10 。

示例 2：

输入：nums = [2,4,9,24,2,1,10]
输出：68

 

提示：

• 2 <= nums.length <= 3*104
• -105 <= nums[i] <= 105
• 答案保证在 32 位整数范围内。

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

思考

数组值为相邻差的绝对值之和，允许翻转一段。 $n\le 3\times {10}^4$，枚举左右端为平方级。翻转只改动与翻转边界相邻的那几条边。

不翻转的和记为 $s$。翻转贴着左端或右端时，枚举另一端即可 $O(n)$ 更新。内部翻转把相邻对看成 $(x,y)$，增量写成四个线性组合的最大差，对各组合维护 $a-b$ 的最大与 $a+b$ 的最小，一次扫描得到最优增量。

根据题目描述，我们需要求出：在翻转一次子数组的情况下，数组值 $\sum _{i=0}^{n-2}|a_i-a_{i+1}|$ 的最大值。

接下来，我们分以下几种情况讨论：

1. 不翻转子数组
2. 翻转子数组，且子数组“包含”第一个元素
3. 翻转子数组，且子数组“包含”最后一个元素
4. 翻转子数组，且子数组“不包含”第一个元素和最后一个元素

我们记不翻转子数组时的数组值为 $s$，此时有 $s=\sum _{i=0}^{n-2}|a_i-a_{i+1}|$。我们可以将答案 $ans$ 初始化为 $s$。

如果翻转子数组，且子数组包含第一个元素，我们可以枚举翻转的子数组的最后一个元素 $a_i$，其中 $0\le i<n-1$，此时有 $ans=max(ans,s+|a_0-a_{i+1}|-|a_i-a_{i+1}|)$。

<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1300-1399/1330.Reverse Subarray To Maximize Array Value/images/1-drawio.png&quot; /></p>

同理，如果翻转子数组，且子数组包含最后一个元素，我们可以枚举翻转的子数组的第一个元素 $a_{i+1}$，其中 $0\le i<n-1$，此时有 $ans=max(ans,s+|a_{n-1}-a_i|-|a_i-a_{i+1}|)$。

<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1300-1399/1330.Reverse Subarray To Maximize Array Value/images/2-drawio.png&quot; /></p>

如果翻转子数组，且子数组不包含第一个元素和最后一个元素，我们将数组任意两个相邻元素视为一个点对 $(x,y)$，记翻转的第一个元素为 $y_1$，其左侧相邻元素为 $x_1$；翻转的最后一个元素为 $x_2$，其右侧相邻元素为 $y_2$。

<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1300-1399/1330.Reverse Subarray To Maximize Array Value/images/3-drawio.png&quot; /></p>

此时相比较于不翻转子数组，数组值的变化量为 $|x_1-x_2|+|y_1-y_2|-|x_1-y_1|-|x_2-y_2|$，其中，前两项可以表示为：

$$|x_1-x_2|+|y_1-y_2|=max\{\begin{array}{l}(x_1+y_1)-(x_2+y_2)\\ (x_1-y_1)-(x_2-y_2)\\ (-x_1+y_1)-(-x_2+y_2)\\ (-x_1-y_1)-(-x_2-y_2)\end{array}$$

那么数组值变化量为：

$$|x_1-x_2|+|y_1-y_2|-|x_1-y_1|-|x_2-y_2|=max\{\begin{array}{l}(x_1+y_1)-|x_1-y_1|-((x_2+y_2)+|x_2-y_2|)\\ (x_1-y_1)-|x_1-y_1|-((x_2-y_2)+|x_2-y_2|)\\ (-x_1+y_1)-|x_1-y_1|-((-x_2+y_2)+|x_2-y_2|)\\ (-x_1-y_1)-|x_1-y_1|-((-x_2-y_2)+|x_2-y_2|)\end{array}$$

因此，我们只要求出 $k_1\times x+k_2\times y$ 的最大值 $mx$，其中 $k_1,k_2\in \{-1,1\}$，以及对应的 $|x-y|$ 的最小值 $mi$，那么数组值变化量的最大值为 $mx-mi$。答案为 $ans=max(ans,s+max(0,mx-mi))$。

在代码实现上，我们定义了一个长度为 $5$ 的数组 $dirs=[1,-1,-1,1,1]$，每次取数组相邻两个元素作为 $k_1,k_2$ 的值，这样可以覆盖 $k_1,k_2\in \{-1,1\}$ 的所有情况。

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

相似题目：

• 1131. 绝对值表达式的最大值

func maxValueAfterReverse(nums []int) int {
	s, n := 0, len(nums)
	for i, x := range nums[:n-1] {
		y := nums[i+1]
		s += abs(x - y)
	}
	ans := s
	for i, x := range nums[:n-1] {
		y := nums[i+1]
		ans = max(ans, s+abs(nums[0]-y)-abs(x-y))
		ans = max(ans, s+abs(nums[n-1]-x)-abs(x-y))
	}
	dirs := [5]int{1, -1, -1, 1, 1}
	const inf = 1 << 30
	for k := 0; k < 4; k++ {
		k1, k2 := dirs[k], dirs[k+1]
		mx, mi := -inf, inf
		for i, x := range nums[:n-1] {
			y := nums[i+1]
			a := k1*x + k2*y
			b := abs(x - y)
			mx = max(mx, a-b)
			mi = min(mi, a+b)
		}
		ans = max(ans, s+max(mx-mi, 0))
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

1338. 数组大小减半

中等1 种解法

标签：贪心、数组、哈希表、排序、堆（优先队列）

题目、示例与约束

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= arr.length <= 105
• arr.length 为偶数
• 1 <= arr[i] <= 105

方法一：计数 + 排序 · Go 实现

思考

删掉尽量少的不同数值，使剩下的元素不超过一半。贪心应优先删出现最多的值。计数后按频次降序累加，直到覆盖至少一半元素，所用不同值的个数即为答案。

我们可以用哈希表或数组 $cnt$ 统计数组 $\mathit{\text{arr}}$ 中每个数字出现的次数，然后将 $cnt$ 中的数字从大到小排序，从大到小遍历 $\mathit{\text{cnt}}$，每次遍历将当前数字 $x$ 加入答案，并将 $m$ 加上 $x$，如果 $m\ge \frac{n}{2}$，则返回答案。

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

func minSetSize(arr []int) (ans int) {
	mx := slices.Max(arr)
	cnt := make([]int, mx+1)
	for _, x := range arr {
		cnt[x]++
	}
	sort.Ints(cnt)
	for i, m := mx, 0; ; i-- {
		if cnt[i] > 0 {
			m += cnt[i]
			ans++
			if m >= len(arr)/2 {
				return
			}
		}
	}
}

力扣原题 · Doocs 题解来源

1353. 最多可以参加的会议数目

中等1 种解法

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

题目、示例与约束

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。

 

示例 1：

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。

示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4

 

提示：​​​​​​

• 1 <= events.length <= 105
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 105

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

思考

每天只能参加一场，区间 $[s,e]$ 内任选一天。 $n$ 与天数均可达 ${10}^5$，按结束时间排序再暴力占天会偏慢。按天扫描：把当日开始的会议结束时间放入小根堆，弹出已过期的，再取出最早结束的一场参加。这样每天都留给剩余期限最短的会议。

我们用一个哈希表 $\mathit{\text{g}}$ 记录每个会议的开始和结束时间。键为会议的开始时间，值为一个列表，包含所有在该开始时间开始的会议的结束时间。用两个变量 $\mathit{\text{l}}$ 和 $\mathit{\text{r}}$ 分别记录会议的最小开始时间和最大结束时间。

对于从小到大每个在 $\mathit{\text{l}}$ 到 $\mathit{\text{r}}$ 的时间点 $s$，我们需要做以下操作：

1. 从优先队列中移除所有结束时间小于当前时间 $s$ 的会议。
2. 将所有开始时间等于当前时间 $s$ 的会议的结束时间加入优先队列中。
3. 如果优先队列不为空，则取出结束时间最小的会议，累加答案数，并从优先队列中移除该会议。

这样，我们可以确保在每个时间点 $s$，我们都能参加结束时间最早的会议，从而最大化参加的会议数。

时间复杂度 $O(M\times \log n)$，空间复杂度 $O(n)$，其中 $M$ 和 $n$ 分别为会议的最大结束时间和会议的数量。

func maxEvents(events [][]int) (ans int) {
	g := map[int][]int{}
	l, r := math.MaxInt32, 0
	for _, event := range events {
		s, e := event[0], event[1]
		g[s] = append(g[s], e)
		l = min(l, s)
		r = max(r, e)
	}

	pq := &hp{}
	heap.Init(pq)
	for s := l; s <= r; s++ {
		for pq.Len() > 0 && pq.IntSlice[0] < s {
			heap.Pop(pq)
		}
		for _, e := range g[s] {
			heap.Push(pq, e)
		}
		if pq.Len() > 0 {
			heap.Pop(pq)
			ans++
		}
	}
	return
}

type hp struct{ sort.IntSlice }

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

力扣原题 · Doocs 题解来源

1383. 最大的团队表现值

困难1 种解法

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

题目、示例与约束

给定两个整数 n 和 k，以及两个长度为 n 的整数数组 speed 和 efficiency。现有 n 名工程师，编号从 1 到 n。其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。

从这 n 名工程师中最多选择 k 名不同的工程师，使其组成的团队具有最大的团队表现值。

团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

请你返回该团队的​​​​​​最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。

 

示例 1：

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出：60
解释：
我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。

示例 2：

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出：68
解释：
此示例与第一个示例相同，除了 k = 3 。我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。

示例 3：

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出：72

 

提示：

• 1 <= k <= n <= 10^5
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^8

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

思考

至多 $k$ 人，表现值为速度和乘以效率最小值。 $n\le {10}^5$，枚举子集不可行。按效率从高到低加入：当前效率即团队效率下界，只需在已加入的人中保留速度最大的至多 $k$ 个。小根堆在人数达到 $k$ 时弹出最慢者，同时维护速度和，用和乘当前效率更新答案。

本题是求“速度和”与“效率最小值”乘积的最大值。变量有两个，我们可以从大到小枚举 efficiency[i] 作为效率最小值，在所有效率大于等于 efficiency[i] 的工程师中选取不超过 $k-1$ 个，让他们速度和最大。

时间复杂度 $O(n\log n)$。

相似题目：

• 857. 雇佣 K 名工人的最低成本

func maxPerformance(n int, speed []int, efficiency []int, k int) int {
	t := make([][]int, n)
	for i, s := range speed {
		t[i] = []int{s, efficiency[i]}
	}
	sort.Slice(t, func(i, j int) bool { return t[i][1] > t[j][1] })
	var mod int = 1e9 + 7
	ans, tot := 0, 0
	pq := hp{}
	for _, x := range t {
		s, e := x[0], x[1]
		tot += s
		ans = max(ans, tot*e)
		heap.Push(&pq, s)
		if pq.Len() == k {
			tot -= heap.Pop(&pq).(int)
		}
	}
	return ans % mod
}

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

力扣原题 · Doocs 题解来源

1386. 安排电影院座位

中等1 种解法

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

题目、示例与约束

如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。

给定一个二维数组 reservedSeats ，其中 reservedSeats[i] = [rowi, seati] 表示第 rowi 行的座位 seati 已经被预定。

四人小组必须被安排在同一排的四个座位上。该小组可以坐在以下座位块之一：

• 座位 2, 3, 4, 5
• 座位 4, 5, 6, 7
• 座位 6, 7, 8, 9

只有当该块中的所有座位都 没有 被预订时，才能使用该块。每个座位 最多 只能分配给一个小组。

返回一个整数，表示可以分配的 最大 四人小组数量。

 

示例 1：

输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
输出：4
解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。

示例 2：

输入：n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
输出：2

示例 3：

输入：n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
输出：4

 

提示：

• 1 <= n <= 109
• 1 <= reservedSeats.length <= min(10 * n, 104)
• reservedSeats[i] == [rowi, seati]
• 1 <= rowi <= n
• 1 <= seati <= 10
• 所有 reservedSeats[i] 都是互不相同的。

方法一：哈希表 + 状态压缩 · Go 实现

思考

每行 $10$ 座，家庭占连续 $4$ 座（ $2$– $5$、 $4$– $7$、 $6$– $9$）， $n$ 可达 ${10}^9$ 但不能扫空行。无预约的行可坐两家，先计入 $2(n-|d|)$。有预约的行把座位压成十位掩码，依次尝试三个四座窗口，能放下就占上并加一，避免同一座位分给两家。

我们用哈希表 $d$ 来存储所有已经被预约的座位，其中键为行号，值为该行上已经被预约的座位的状态，即一个二进制数，第 $j$ 位为 $1$ 表示第 $j$ 个座位已经被预约，为 $0$ 表示第 $j$ 个座位尚未被预约。

我们遍历 $reservedSeats$，对于每个座位 $(i,j)$，将第 $j$ 个座位（对应低位的第 $10-j$ 位）的状态加入到 $d[i]$ 中即可。

对于没有出现在哈希表 $d$ 中的行，我们可以任意安排 $2$ 个家庭，因此，初始答案为 $(n-len(d))\times 2$。

接下来，我们遍历哈希表中每一行的状态，对于每一行，我们依次尝试安排 $1234,5678,3456$ 这几种情况，如果某种情况可以安排，我们就将答案加 $1$。

遍历结束后，我们就得到了最终的答案。

时间复杂度 $O(m)$，空间复杂度 $O(m)$，其中 $m$ 是 $reservedSeats$ 的长度。

func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
	d := map[int]int{}
	for _, e := range reservedSeats {
		i, j := e[0], e[1]
		d[i] |= 1 << (10 - j)
	}
	ans := (n - len(d)) * 2
	masks := [3]int{0b0111100000, 0b0000011110, 0b0001111000}
	for _, x := range d {
		for _, mask := range masks {
			if x&mask == 0 {
				x |= mask
				ans++
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1400. 构造 K 个回文字符串

中等1 种解法

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

题目、示例与约束

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。

如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

 

示例 1：

输入：s = "annabelle", k = 2
输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

示例 2：

输入：s = "leetcode", k = 3
输出：false
解释：无法用 s 中所有字符构造 3 个回文串。

示例 3：

输入：s = "true", k = 4
输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

 

提示：

• 1 <= s.length <= 105
• s 中所有字符都是小写英文字母。
• 1 <= k <= 105

方法一：计数 · Go 实现

思考

若枚举将 $s$ 划分成 $k$ 段并逐段验证回文，划分方案数随 $n$ 指数增长。 $n,k\le {10}^5$，因此只能依据回文的计数性质直接判定可否构造。

每个回文串至多有一个出现奇数次的字符作为中心，其余字符必须成对出现。 $k$ 个回文串至多消耗 $k$ 个奇数字符；同时每个回文至少占用一个字符，故 $|s|<k$ 时必然不可行。

为此先比较长度与 $k$，再用哈希表统计各字符频次，判断奇数频次的个数是否不超过 $k$。偶对可任意拆分到各串中，不必真正构造。

我们先判断字符串 $s$ 的长度是否小于 $k$，如果是，那么一定无法构造出 $k$ 个回文串，可以直接返回 false。

否则，我们用一个哈希表或数组 $cnt$ 统计字符串 $s$ 中每个字符出现的次数。最后，我们只需要统计 $cnt$ 中奇数次数的字符个数 $x$，如果 $x$ 大于 $k$，那么一定无法构造出 $k$ 个回文串，返回 false；否则，返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是字符串 $s$ 的长度；而 $C$ 是字符集大小，这里 $C=26$。

func canConstruct(s string, k int) bool {
	if len(s) < k {
		return false
	}
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	x := 0
	for _, v := range cnt {
		x += v & 1
	}
	return x <= k
}

力扣原题 · Doocs 题解来源