上周末是 LeetCode 第 100 场双周赛，你参加了吗？这场周赛整体没有 Hard 题，但是也没有 Easy 题。第一题国服前百名里超过一半人 wa，很少见。
小彭的技术交流群 02 群来了，公众号回复 “加群” 加入我们~
周赛概览
2591. 将钱分给最多的儿童（Easy）
题目地址
https://leetcode.cn/problems/distribute-money-to-maximum-children/description/
题目描述
给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。
你需要按照如下规则分配：
请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 **8 美元。如果没有任何分配方案，返回 -1 。
题解一（模拟）
这道题搞数字迷信？发发发 888？
简单模拟题，但是错误率很高，提交通过率仅 19%。
classSolution{
fundistMoney(money: Int, children: Int): Int {
var left = money
// 每人至少分配 1 元
left -= children
// 违反规则 2if (left < 0) return -1// 1、完美：正好所有人可以分配 8 元if (left == children * 7) return children
// 2、溢出：所有人可以分配 8 元有结余，需要选择 1 个人分配结余的金额if (left > children * 7) return children - 1// 3、不足：尽可能分配 8 元var sum = left / 7// 结余金额
left -= sum * 7// 如果结余 3 元，并且剩下 1 人分配了 1 元，需要破坏一个 8 元避免出现分配 4 美元if (left == 3 && children - sum == 1) return sum - 1return sum
}
}
复杂度分析：
题解二（完全背包问题）
竞赛中脑海闪现过背包问题的思路，但第一题暴力才是王道，赛后验证可行。
令 dp[i][j] 表示分配到 i 个人为止，且分配总金额为 j 元时的最大价值，则有：
$$
dp[i][j]=\sum_{k=1}^{j,k!=4} dp[i-1][j-k] + I(k==8)
$$
classSolution{
fundistMoney(money: Int, children: Int): Int {
var left = money
// 每人至少分配 1 元
left -= children
// 违反规则 2if (left < 0) return -1val dp = Array(children + 1) { IntArray(left + 1) { -1 } }
dp[0][0] = 0// i：枚举包裹for (i in1..children) {
// j：枚举金额for (j in0..left) {
// k：枚举选项for (k in0..j) {
// 不允许选择 3if (k == 3) continue// 子状态违反规则if (-1 == dp[i - 1][j - k]) continue// 子状态 + 当前包裹状态val cnt = dp[i - 1][j - k] + if (k == 7) 1else0
dp[i][j] = Math.max(dp[i][j], cnt)
}
}
}
return dp[children][left]
}
}
滚动数组优化：
classSolution{
fundistMoney(money: Int, children: Int): Int {
var left = money
// 每人至少分配 1 元
left -= children
// 违反规则 2if (left < 0) return -1val dp = IntArray(left + 1) { -1 }
dp[0] = 0// i：枚举包裹for (i in1..children) {
// j：枚举金额for (j in left downTo 0) {
// k：枚举选项for (k in0..j) {
// 不允许选择 3if (k == 3) continue// 子状态违反规则if (-1 == dp[j - k]) continue// 子状态 + 当前包裹状态val cnt = dp[j - k] + if (k == 7) 1else0
dp[j] = Math.max(dp[j], cnt)
}
}
}
return dp[left]
}
复杂度分析：
近期周赛背包问题：
2592. 最大化数组的伟大值（Medium）
题目地址
https://leetcode.cn/problems/maximize-greatness-of-an-array/
题目描述
给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。
定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。
请你返回重新排列 nums 后的 最大 伟大值。
题解一（贪心 / 田忌赛马）
贪心思路：田忌赛马，以下赛马策略最优：
回到本题，考虑一组贡献伟大值的配对 $(p, q)$，其中 $p < q$。由于越小的值越匹配到更大值，为了让结果最优，应该让 p 尽可能小，即优先匹配 nums 数组的较小值。那么 $q$ 如何选择呢？有 2 种策略：
策略 2- 优先匹配最接近的更大值：最优解，即田忌赛马策略，以 [1,1,1,2,3,3,5] 为例：
classSolution{
funmaximizeGreatness(nums: IntArray): Int {
nums.sort()
// i：参与匹配的指针var i = 0for (num in nums) {
// 贡献伟大值if (num > nums[i]) i++
}
return i
}
}
复杂度分析：
题解二（最大重复计数）
竞赛中从测试用例中观察到题解与最大重复数存在关系，例如：
用例 [1,1,1,2,3,3,5]：最大重复数为 3，一个最优方案为 [2,3,3,5,x,x,x]，最大伟大值为 7 - 3 = 4，其中 7 是数组长度；
用例 [1,2,2,2,2,3,5]：最大重复数为 4，一个最优方案为 [2,3,5,x,x,x,x]，最大伟大值为 7 - 4 = 3，其中 7 是数组长度；
用例 [1,1,2,2,2,2,3,3,5]，最大重复数为 4，一个最优方案为 [2,2,3,3,5,x,x,x,x]，最大伟大值为 9 - 4 = 5，其中 9 是数组长度。
我们发现题目的瓶颈在于数字最大重复出现计数。最大伟大值正好等于 数组长度 - 最大重复计数。
如何证明？关键在于 i 指针和 j 指针的最大距离：
当 i 指针指向重复元素的首个元素时（例如下标为 0、2、6 的位置），j 指针必须移动到最接近的较大元素（例如下标为 2，6，8 的位置）。而 i 指针和 j 指针的最大错开距离取决于数组重复出现次数最多的元素，只要错开这个距离，无论数组后续部分有多长，都能够匹配上。
classSolution{
funmaximizeGreatness(nums: IntArray): Int {
var maxCnt = 0val cnts = HashMap<Int, Int>()
for (num in nums) {
cnts[num] = cnts.getOrDefault(num, 0) + 1
maxCnt = Math.max(maxCnt, cnts[num]!!)
}
return nums.size - maxCnt
}
}
复杂度分析：
2593. 标记所有元素后数组的分数（Medium）
题目地址
https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/
题目描述
给你一个数组 nums ，它包含若干正整数。
一开始分数 score = 0 ，请你按照下面算法求出最后分数：
请你返回执行上述算法后最后的分数。
题解一（排序）
这道题犯了大忌，没有正确理解题意。一开始以为 “相邻的元素” 是指未标记的最相邻元素，花了很多时间思考如何快速找到左右未标记的数。其实题目没有这么复杂，就是标记数组上的相邻元素。
如此这道题只能算 Medium 偏 Easy 难度。
classSolution{
funfindScore(nums: IntArray): Long {
// 小顶堆（索引）val heap = PriorityQueue<Int>() { i1, i2 ->
if (nums[i1] != nums[i2]) nums[i1] - nums[i2] else i1 - i2
}.apply {
for (index in nums.indices) {
offer(index)
}
}
var sum = 0Lwhile (!heap.isEmpty()) {
val index = heap.poll()
if (nums[index] == 0) continue// 标记
sum += nums[index]
nums[index] = 0// 标记相邻元素if (index > 0) nums[index - 1] = 0if (index < nums.size - 1) nums[index + 1] = 0
}
return sum
}
}
复杂度分析：
题解二（按照严格递减字段分组）
思路参考：灵茶山艾府的题解
按照严格递减字段分组，在找到坡底后间隔累加 nums[i]，nums[i - 2]，nums[i - 4]，并从 i + 2 开始继续寻找坡底。
classSolution{
funfindScore(nums: IntArray): Long {
val n = nums.size
var sum = 0Lvar i = 0while (i < nums.size) {
val i0 = i // 坡顶while (i + 1 < n && nums[i] > nums[i + 1]) i++ // 寻找坡底for (j in i downTo i0 step 2) { // 间隔累加
sum += nums[j]
}
i += 2// i + 1 不能选
}
return sum
}
}
复杂度分析：
2594. 修车的最少时间（Medium)
题目地址
https://leetcode.cn/problems/minimum-time-to-repair-cars/
题目描述
给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars ，表示总共需要修理的汽车数目。
请你返回修理所有汽车 最少 需要多少时间。
注意： 所有机械工可以同时修理汽车。
题解（二分查找）
我们发现问题在时间 t 上存在单调性：
因此，我们可以用二分查找寻找 “可以修完的最小时间”：
classSolution{
funrepairCars(ranks: IntArray, cars: Int): Long {
// 寻找能力值排序最高的工人var minRank = Integer.MAX_VALUE
for (rank in ranks) {
minRank = Math.min(minRank, rank)
}
var left = 1Lvar right = 1L * minRank * cars * cars
// 二分查找while (left < right) {
val mid = (left + right) ushr 1if (check(ranks, cars, mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
// return 能否在 t 时间内修完所有车privatefuncheck(ranks: IntArray, cars: Int, t: Long): Boolean {
// 计算并行修车 t 时间能修完的车（由于 t 的上界较大，carSum 会溢出 Int）var carSum = 0Lfor (rank in ranks) {
carSum += Math.sqrt(1.0 * t / rank).toLong()
}
return carSum >= cars
}
}
复杂度分析：
题解二（二分查找 + 计数优化）
我们发现 $ranks$ 的取值范围很小，所有可以用计数优化每次 $check$ 操作的时间复杂度：
classSolution{
funrepairCars(ranks: IntArray, cars: Int): Long {
// 寻找能力值排序最高的工人val cnts = IntArray(101)
var minRank = Integer.MAX_VALUE
for (rank in ranks) {
minRank = Math.min(minRank, rank)
cnts[rank]++
}
var left = 1Lvar right = 1L * minRank * cars * cars
// 二分查找while (left < right) {
val mid = (left + right) ushr 1if (check(ranks, cars, cnts, minRank, mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
// return 能否在 t 时间内修完所有车privatefuncheck(ranks: IntArray, cars: Int, cnts: IntArray, minRank: Int, t: Long): Boolean {
// 计算并行修车 t 时间能修完的车（由于 t 的上界较大，carSum 会溢出 Int）var carSum = 0Lfor (rank in minRank..100) {
if (cnts[rank] == 0) continue
carSum += cnts[rank] * Math.sqrt(1.0 * t / rank).toLong()
}
return carSum >= cars
}
}
复杂度分析：
近期周赛二分查找题目：
