本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 发问。
大家好,我是小彭。
上周末是 LeetCode 第 100 场双周赛,你参加了吗?这场周赛全体没有 Hard 题,可是也没有 Easy 题。第一题国服前百名里超过一半人 wa,很少见。
周赛概览
2591.将钱分给最多的儿童(Easy)
- 题解一:模仿 O(1)O(1)
- 题解二:彻底背包 O(children⋅money2)O(childrenmoney^2)
2592.最大化数组的巨大值(Medium)
- 题解一:贪心 / 田忌赛马 O(nlgn)O(nlgn)
- 题解二:最大重复计数 O(n)O(n)
2593.符号一切元素后数组的分数(Medium)
- 题解一:排序 O(nlgn)(nlgn)
- 题解二:依照严厉递减字段分组 O(n)O(n)
2594.修车的最少时刻(Medium)
- 题解一:二分查找 O(n+U⋅log(mc2))O(n + Ulog(mc^2))
- 题解二:二分查找 + 计数优化 O(n⋅log(mc2))O(nlog(mc^2))
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)
题解二(彻底背包问题)
比赛中脑海闪现过背包问题的思路,但第一题暴力才是王道,赛后验证可行。
- 包裹:最多有
children
人; - 物品:每个金币价值为 1 且不可分割,最多物品数为
money
个; - 目标:包裹价值刚好为 8 的最大个数;
- 约束条件:不允许包裹价值为 4,每个包裹至少装 1 枚金币。
令 dp[i][j]
表明分配到 i
个人停止,且分配总金额为 j
元时的最大价值,则有:
- 递推关系:
- 初始状况
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(childrenmoney^2)
- 空间杂乱度:O(money)O(money)
近期周赛背包问题:
- LeetCode 周赛 333 无平方子集计数(Medium)
- LeetCode 周赛 335 取得分数的方法数(Hard)
2592.最大化数组的巨大值(Medium)
标题地址
leetcode.cn/problems/ma…
标题描绘
给你一个下标从 0 开端的整数数组nums
。你需求将nums
重新排列成一个新的数组perm
。
定义nums
的巨大值为满意0 <= i < nums.length
且perm[i] > nums[i]
的下标数目。
请你回来重新排列nums
后的最大巨大值。
题解一(贪心 / 田忌赛马)
贪心思路:田忌赛马,以下赛马战略最优:
- 田忌的中等马对齐威王的劣等马,田忌胜;
- 田忌的上等马对齐威王的中等马,田忌胜;
- 田忌的劣等马对齐威王的劣等马,齐威王胜。
回到本题,考虑一组奉献巨大值的配对 (p,q)(p, q),其间 p<qp < q。因为越小的值越匹配到更大值,为了让结果最优,应该让 p 尽可能小,即优先匹配 nums 数组的较小值。那么 qq 怎么挑选呢?有 2 种战略:
- 战略 1 – 优先匹配最大值:无法得到最优解,因为会消耗了较大的 q 值,可能导致部分 p 值无法匹配(如果田忌用上等马对齐威王的劣等马,最终将是齐威王生出);
- 战略 2- 优先匹配最接近的更大值:最优解,即田忌赛马战略,以 [1,1,1,2,3,3,5] 为例:
- 初始状况 i = 0,j = 0;
- i = 0,j = 0,无法奉献巨大值,j 自增 1(寻觅最接近的更大值);
- i = 0,j = 1, 无法奉献巨大值,j 自增 1;
- i = 0,j = 2, 无法奉献巨大值,j 自增 1;
- i = 0,j = 3, 奉献巨大值,j 自增 1,i 自增 1;
- i = 1,j = 4, 奉献巨大值,j 自增 1,i 自增 1;
- i = 2,j = 5, 奉献巨大值,j 自增 1,i 自增 1;
- i = 3,j = 6, 奉献巨大值,j 自增 1,i 自增 1;
- 退出循环,i = 4;正好等于巨大值 4。
class Solution {
fun maximizeGreatness(nums: IntArray): Int {
nums.sort()
// i:参加匹配的指针
var i = 0
for (num in nums) {
// 奉献巨大值
if (num > nums[i]) i++
}
return i
}
}
杂乱度剖析:
- 时刻杂乱度:O(nlgn+n)O(nlgn + n) 排序 + 线性遍历,其间 nn 是 numsnums 数组长度;
- 空间杂乱度:O(lgn)O(lgn) 排序递归栈空间。
题解二(最大重复计数)
比赛中从测试用例中观察到题解与最大重复数存在关系,例如:
- 用例 [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 指针的最大错开距离取决于数组重复呈现次数最多的元素,只要错开这个距离,不管数组后续部分有多长,都能够匹配上。
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
}
}
杂乱度剖析:
- 时刻杂乱度:O(n)O(n) 其间 nn 是 numsnums 数组的长度;
- 空间杂乱度:O(n)O(n) 其间 nn 是 cntscnts 散列表空间。
2593.符号一切元素后数组的分数(Medium)
标题地址
leetcode.cn/problems/fi…
标题描绘
给你一个数组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
}
}
杂乱度剖析:
- 时刻杂乱度:O(nlgn)O(nlgn) 堆排序时刻,其间 nn 是 numsnums 数组长度;
- 空间杂乱度: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) 其间 nn 是 numsnums 数组的长度,每个元素最多访问 2 次;
- 空间杂乱度: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(nlog(mc^2)) 其间 nn 是 ranksranks 数组长度,mm 是 ranksranks 数组的最小值,cc 是车辆数量,二分的次数是 O(log(mc2))O(log(mc^2)),每次 checkcheck 操作花费 O(n)O(n) 时刻;
- 空间杂乱度:O(1)O(1) 仅运用常量级别空间。
题解二(二分查找 + 计数优化)
咱们发现 ranksranks 的取值规模很小,一切能够用计数优化每次 checkcheck 操作的时刻杂乱度:
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 + Ulog(mc^2)) 其间 nn 是 ranksranks 数组长度,mm 是 ranksranks 数组的最小值,UU 是 ranksranks 数组的取值规模,cc 是车辆数量,二分的次数是 O(log(mc2))O(log(mc^2)),每次 checkcheck 操作花费 O(U)O(U) 时刻;
- 空间杂乱度:O(U)O(U) cntscnts 计数数组空间。
近期周赛二分查找标题:
- LeetCode 332 统计公平数对的数目(Medium)
- LeetCode 334 在网格图中访问一个格子的最少时刻(Hard)
这场周赛就这么多,咱们下周见。
本文正在参加「金石计划」