刷爆 LeetCode 双周赛 100，单方面宣布第一题最难-六虎

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。

大家好，我是小彭。

上周末是 LeetCode 第 100 场双周赛，你参加了吗？这场周赛全体没有 Hard 题，可是也没有 Easy 题。第一题国服前百名里超过一半人 wa，很少见。

周赛概览

2591.将钱分给最多的儿童（Easy）

题解一：模仿 $O (1)$
题解二：彻底背包 $O(childrenmoney^2)$

2592.最大化数组的巨大值（Medium）

题解一：贪心 / 田忌赛马 $O (n l g n)$
题解二：最大重复计数 $O (n)$

2593.符号一切元素后数组的分数（Medium）

题解一：排序 O $(n l g n)$
题解二：依照严厉递减字段分组 $O (n)$

2594.修车的最少时刻（Medium)

题解一：二分查找 $O(n + Ulog(mc^2))$
题解二：二分查找 + 计数优化 $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)$

题解二（彻底背包问题）

比赛中脑海闪现过背包问题的思路，但第一题暴力才是王道，赛后验证可行。

包裹：最多有 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[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(childrenmoney^2)$
空间杂乱度： $O (m o n ey)$

近期周赛背包问题：

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 尽可能小，即优先匹配 nums 数组的较小值。那么 $q$ 怎么挑选呢？有 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 (n l g n + n)$ 排序 + 线性遍历，其间 $n$ 是 $n u m s$ 数组长度；
空间杂乱度： $O (l g n)$ 排序递归栈空间。

题解二（最大重复计数）

比赛中从测试用例中观察到题解与最大重复数存在关系，例如：

用例 [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)$ 其间 $n$ 是 $n u m s$ 数组的长度；
空间杂乱度： $O (n)$ 其间 $n$ 是 $c n t s$ 散列表空间。

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 (n l g n)$ 堆排序时刻，其间 $n$ 是 $n u m s$ 数组长度；
空间杂乱度： $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)$ 其间 $n$ 是 $n u m s$ 数组的长度，每个元素最多访问 2 次；
空间杂乱度： $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(nlog(mc^2))$ 其间 $n$ 是 $r ank s$ 数组长度， $m$ 是 $r ank s$ 数组的最小值， $c$ 是车辆数量，二分的次数是 $O(log(mc^2))$ ，每次 $c h ec k$ 操作花费 $O (n)$ 时刻；
空间杂乱度： $O (1)$ 仅运用常量级别空间。

题解二（二分查找 + 计数优化）

咱们发现 $r ank s$ 的取值规模很小，一切能够用计数优化每次 $c h ec k$ 操作的时刻杂乱度：

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 + Ulog(mc^2))$ 其间 $n$ 是 $r ank s$ 数组长度， $m$ 是 $r ank s$ 数组的最小值， $U$ 是 $r ank s$ 数组的取值规模， $c$ 是车辆数量，二分的次数是 $O(log(mc^2))$ ，每次 $c h ec k$ 操作花费 $O (U)$ 时刻；
空间杂乱度： $O (U)$ $c n t s$ 计数数组空间。

近期周赛二分查找标题：

LeetCode 332 统计公平数对的数目（Medium）
LeetCode 334 在网格图中访问一个格子的最少时刻（Hard）

这场周赛就这么多，咱们下周见。

本文正在参加「金石计划」

刷爆 LeetCode 双周赛 100，单方面宣布第一题最难

周赛概览

2591.将钱分给最多的儿童（Easy）

标题地址

标题描绘

题解一（模仿）

题解二（彻底背包问题）

2592.最大化数组的巨大值（Medium）

标题地址

标题描绘

题解一（贪心 / 田忌赛马）

题解二（最大重复计数）

2593.符号一切元素后数组的分数（Medium）

标题地址

标题描绘

题解一（排序）

题解二（依照严厉递减字段分组）

2594.修车的最少时刻（Medium)

标题地址

标题描绘

题解（二分查找）

题解二（二分查找 + 计数优化）

相关文章

Spring源码解析-Spring AOP

[Unity] ③第一人称视角控制器——交互（学习笔记）

IntersectionObserver实现图片懒加载

Android 11 变更及适配攻略

作者信息