刷爆 LeetCode 双周赛 100，单方面宣布第一题最难 |
您所在的位置：网站首页 › 刷课的浏览器有哪些 › 刷爆 LeetCode 双周赛 100，单方面宣布第一题最难 |
刷爆 LeetCode 双周赛 100，单方面宣布第一题最难
|
本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 上周末是 LeetCode 第 100 场双周赛，你参加了吗？这场周赛整体没有 Hard 题，但是也没有 Easy 题。第一题国服前百名里超过一半人 wa，很少见。 2591. 将钱分给最多的儿童（Easy） 题解一：模拟 O(1)O(1)O(1) 题解二：完全背包 O(children⋅money2)O(children·money^2)O(children⋅money2)2592. 最大化数组的伟大值（Medium） 题解一：贪心 / 田忌赛马 O(nlgn)O(nlgn)O(nlgn) 题解二：最大重复计数 O(n)O(n)O(n)2593. 标记所有元素后数组的分数（Medium） 题解一：排序 O(nlgn)(nlgn)(nlgn) 题解二：按照严格递减字段分组 O(n)O(n)O(n)2594. 修车的最少时间（Medium) 题解一：二分查找 O(n+U⋅log(mc2))O(n + U·log(mc^2))O(n+U⋅log(mc2)) 题解二：二分查找 + 计数优化 O(n⋅log(mc2))O(n·log(mc^2))O(n⋅log(mc2)) 2591. 将钱分给最多的儿童（Easy） 题目地址leetcode.cn/problems/di… 题目描述给你一个整数 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 } } 复制代码复杂度分析： 时间复杂度：O(1)O(1)O(1) 空间复杂度：O(1)O(1)O(1) 题解二（完全背包问题）竞赛中脑海闪现过背包问题的思路，但第一题暴力才是王道，赛后验证可行。 包裹：最多有 children 人； 物品：每个金币价值为 1 且不可分割，最多物品数为 money 个； 目标：包裹价值恰好为 8 的最大个数； 限制条件：不允许包裹价值为 4，每个包裹至少装 1 枚金币。令 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] } 复制代码复杂度分析： 时间复杂度：O(children⋅money2)O(children·money^2)O(children⋅money2) 空间复杂度：O(money)O(money)O(money)近期周赛背包问题： LeetCode 周赛 333 · 无平方子集计数（Medium） LeetCode 周赛 335 · 获得分数的方法数（Hard） 2592. 最大化数组的伟大值（Medium） 题目地址leetcode.cn/problems/ma… 题目描述给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。 定义 nums 的 伟大值 为满足 0 nums[i] 的下标数目。 请你返回重新排列 nums 后的 最大 伟大值。 贪心思路：田忌赛马，以下赛马策略最优： 田忌的中等马对齐威王的下等马，田忌胜； 田忌的上等马对齐威王的中等马，田忌胜； 田忌的下等马对齐威王的下等马，齐威王胜。回到本题，考虑一组贡献伟大值的配对 (p,q)(p, q)(p,q)，其中 p 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 } } 复制代码 复杂度分析： 时间复杂度：O(nlgn)O(nlgn)O(nlgn) 堆排序时间，其中 nnn 是 numsnumsnums 数组长度； 空间复杂度：O(n)O(n)O(n) 堆空间。 题解二（按照严格递减字段分组）思路参考：灵茶山艾府的题解 按照严格递减字段分组，在找到坡底后间隔累加 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 } } 复制代码复杂度分析： 时间复杂度：O(n)O(n)O(n) 其中 nnn 是 numsnumsnums 数组的长度，每个元素最多访问 2 次； 空间复杂度：O(1)O(1)O(1) 只使用常数空间。 2594. 修车的最少时间（Medium) 题目地址leetcode.cn/problems/mi… 题目描述给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。 同时给你一个整数 cars ，表示总共需要修理的汽车数目。 请你返回修理所有汽车 最少 需要多少时间。 注意： 所有机械工可以同时修理汽车。 我们发现问题在时间 t 上存在单调性： 假设可以在 t 时间内修完所有车，那么大于 t 的时间都能修完； 如果不能在 t 时间内修完所有车，那么小于 t 的时间都无法修完。因此，我们可以用二分查找寻找 “可以修完的最小时间”： 二分的下界：1； 二分的上界：将所有的车交给能力值排序最高的工人，因为他的效率最高。 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 } } 复制代码复杂度分析： 时间复杂度：O(n⋅log(mc2))O(n·log(mc^2))O(n⋅log(mc2)) 其中 nnn 是 ranksranksranks 数组长度，mmm 是 ranksranksranks 数组的最小值，ccc 是车辆数量，二分的次数是 O(log(mc2))O(log(mc^2))O(log(mc2))，每次 checkcheckcheck 操作花费 O(n)O(n)O(n) 时间； 空间复杂度：O(1)O(1)O(1) 仅使用常量级别空间。 题解二（二分查找 + 计数优化）我们发现 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 } } 复制代码复杂度分析： 时间复杂度：O(n+U⋅log(mc2))O(n + U·log(mc^2))O(n+U⋅log(mc2)) 其中 nnn 是 ranksranksranks 数组长度，mmm 是 ranksranksranks 数组的最小值，UUU 是 ranksranksranks 数组的取值范围，ccc 是车辆数量，二分的次数是 O(log(mc2))O(log(mc^2))O(log(mc2))，每次 checkcheckcheck 操作花费 O(U)O(U)O(U) 时间； 空间复杂度：O(U)O(U)O(U) cntscntscnts 计数数组空间。近期周赛二分查找题目： LeetCode 332 · 统计公平数对的数目（Medium） LeetCode 334 · 在网格图中访问一个格子的最少时间（Hard）这场周赛就这么多，我们下周见。 本文正在参加「金石计划」 |
【本文地址】
今日新闻 |
推荐新闻 |