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