共计 8836 个字符,预计需要花费 23 分钟才能阅读完成。
本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 发问。
大家好,我是小彭。
上周末是 LeetCode 第 338 场周赛,你加入了吗?这场周赛笼罩的知识点很多,第四题称得上是近期几场周赛的天花板。
小彭的技术交换群 02 群来了,公众号回复“加群”退出咱们~
目录
2599. K 件物品的最大和(Easy)
- 贪婪、模仿 $O(1)$
2600. 质数减法运算(Medium)
- 题解一:暴力枚举 + 二分查找 $O(U\sqrt{U} + nlgU)$
- 题解二:Eratosthenes 埃氏筛 + 二分查找 $O(UlgU + nlgU)$
- 题解三:Euler 欧氏线性筛 + 二分查找 $O(U + nlgU)$
2601. 使数组元素全副相等的起码操作次数
- 前缀和 + 二分查找 $O(nlgn + qlgn)$
2602. 收集树中金币(Hard)
- 拓扑排序 + 模仿 $O(n)$
2599. K 件物品的最大和(Easy)
题目地址
https://leetcode.cn/problems/k-items-with-the-maximum-sum/des…
题目形容
袋子中装有一些物品,每个物品上都标记着数字 1
、0
或 -1
。
给你四个非负整数 numOnes
、numZeros
、numNegOnes
和 k
。
袋子最后蕴含:
numOnes
件标记为1
的物品。numZeroes
件标记为0
的物品。numNegOnes
件标记为1
的物品。
现打算从这些物品中恰好选出 k
件物品。返回所有可行计划中,物品上所标记数字之和的最大值。
题解(贪婪 + 模仿)
简略模拟题,优先选择 1,其次 0,最初 -1。
class Solution {fun kItemsWithMaximumSum(numOnes: Int, numZeros: Int, numNegOnes: Int, k: Int): Int {
var x = k
// 1
val oneCnt = Math.min(numOnes, x)
x -= oneCnt
if (x == 0) return oneCnt
// 0
x -= Math.min(numZeros, x)
if (x == 0) return oneCnt
// -1
return oneCnt - x
}
}
复杂度剖析:
- 工夫复杂度:$O(1)$
- 空间复杂度:$O(1)$
2600. 质数减法运算(Medium)
题目地址
https://leetcode.cn/problems/prime-subtraction-operation/desc…
题目形容
给你一个下标从 0 开始的整数数组 nums
,数组长度为 n
。
你能够执行有限次下述运算:
- 抉择一个之前未选过的下标
i
,并抉择一个 严格小于nums[i]
的质数p
,从nums[i]
中减去p
。
如果你能通过上述运算使得 nums
成为严格递增数组,则返回 true
;否则返回 false
。
严格递增数组 中的每个元素都严格大于其后面的元素。
准备常识
这道题如果相熟质数筛就是简略二分查找问题。
1、质数定义:
- 质数 / 素数:只能被 1 和自身整除的数,例如 3,5,7;
- 合数:除了能被 1 和自身整除外,还能被其余数整除的数。也能够了解为由多个不为 1 的质数相乘组成的数,例如 4 = 2 2,6 = 2 3。
- 1 既不是质数也不是合数。
2、判断 x 是否为质数:
能够枚举 [2,n-1] 的所有数,查看是否是 x 的因数,工夫复杂度是 O(n)。事实上并不需要枚举到 n-1:以 n = 17 为例,假如从 2 枚举到 4 都没有发现因子,咱们发现 5 也没必要查看。
能够用反证法证实:如果 17 可能被 5 整除,那么肯定存在 17 可能被 17/5 的另一个数整除。而因为 17/5 < 5
与后面验证过 [2,4] 不存在因子的前提矛盾。因而 5 不可能是因子。
由此得出,如果存在整除关系 n/x = y,咱们只须要查看 x 和 y 之间的较小值。所有的较小值最大不会超过 n 的平方根。所以咱们能够放大查看范畴,只查看 $[1, O(\sqrt{x})]$,工夫复杂度是 $O(\sqrt{x})$
3、计算所有小于 n 的质数,有三种算法:
- 暴力枚举: 枚举每个数,判断它是不是质数,整体工夫复杂度是 $O(n\sqrt{n})$
- Eratosthenes 埃氏筛: 如果 x 不是质数,则从 x*x 开始将成倍的数字标记为非质数,整体工夫复杂度是 O(UlgU);
- Euler 欧氏线性筛: 标记 x 与“小于等于 x 的最小质因子的质数”的乘积为非质数,保障每个合数只被标记最小的质因子标记。
题解一(暴力枚举质数 + 二分查找)
为了取得严格递增数组,显然数组的末位元素的束缚是最弱的,甚至是没有束缚的。所以咱们抉择从后往前解决,最初一个数不须要解决。
显然如果靠后的元素尽可能大,那么靠前的元素越容易满足条件。因而,咱们能够找到贪婪思路:从后往前解决,每解决一个数字时,咱们尽可能减去满足题目要求的最小质数,减缓数字变小的速度,给靠前的数字留出空间。
容易发现,“满足题目要求的最小质数”存在枯燥性能够用二分查找解决。因而咱们的题解分为 2 局部:
- 1、预处理题目数据范畴内的所有质数,即小于 1000 的质数列表,能够用预置常识中的两种;
- 2、应用二分查找寻找“满足题目要求的最小质数”。
class Solution {
companion object {
// 1000 以内的质数列表
private val primes = getPrimes(1000)
// 暴力求质数
private fun getPrimes(max: Int): IntArray {val primes = LinkedList<Int>()
for (num in 2..max) {if (isPrime(num)) primes.add(num)
}
return primes.toIntArray()}
// 质数判断
private fun isPrime(num: Int): Boolean {
var x = 2
while (x * x <= num) {if (num % x == 0) return false
x++
}
return true
}
}
fun primeSubOperation(nums: IntArray): Boolean {for (index in nums.size - 2 downTo 0) {if (nums[index] < nums[index + 1]) continue
// 二分查找:寻找严格小于 nums[index] 且减去后造成递增的最小质数
var left = 0
var right = primes.size - 1
while (left < right) {val mid = (left + right) ushr 1
if (primes[mid] >= nums[index] || nums[index] - primes[mid] < nums[index + 1]) {right = mid} else {left = mid + 1}
}
if (primes[left] >= nums[index] || nums[index] - primes[left] >= nums[index + 1]) return false
nums[index] -= primes[left]
}
return true
}
}
复杂度剖析:
- 工夫复杂度:$O(U·\sqrt{U} + nlgU)$ 其中 $n$ 是 $nums$ 数组的长度,$U$ 是输出数据范畴,$U$ 为常数 $1000$;
- 空间复杂度:$O(1)$ 疏忽预处理质数空间,仅应用常数级别空间。
题解二(Eratosthenes 埃氏筛 + 二分查找)
计算质数的局部能够用经典埃氏筛。
筛法求质数的思路是:如果 x 是质数,那么 x 的整数倍 2x、3x 肯定不是质数。咱们设 isPrime[i]
示意 i 是否为质数,从小开始遍历,如果 i 是质数,则同时将所有倍数标记为合数。事实上,咱们不用从 x 开始标记,而是间接从 xx 开始标记,因为 x 2, x * 3 曾经在之前被标记过,会反复标记。
class Solution {
companion object {
// 1000 以内的质数列表
private val primes = getPrimes(1000)
// 埃氏筛求质数
private fun getPrimes(max: Int): IntArray {val primes = LinkedList<Int>()
val isPrime = BooleanArray(max + 1) {true}
for (num in 2..max) {// 查看是否为质数,这里不须要调用 isPrime() 函数判断是否质数,因为它没被小于它的数标记过,那么肯定不是合数
if (!isPrime[num]) continue
primes.add(num)
// 标记
var x = num * num
while (x <= max) {isPrime[x] = false
x += num
}
}
return primes.toIntArray()}
}
fun primeSubOperation(nums: IntArray): Boolean {
val n = nums.size
if (n <= 1) return true
for (index in n - 2 downTo 0) {if (nums[index] < nums[index + 1]) continue
// 二分查找
var left = 0
var right = primes.size - 1
while (left < right) {val mid = (left + right) ushr 1
if (primes[mid] >= nums[index] || nums[index] - primes[mid] < nums[index + 1]) {right = mid} else {left = mid + 1}
}
if (primes[left] >= nums[index] || nums[index] - primes[left] >= nums[index + 1]) return false
nums[index] -= primes[left]
}
return true
}
}
复杂度剖析:
- 工夫复杂度:$O(U·lgU + nlgU)$ 其中 $n$ 是 $nums$ 数组的长度,$U$ 是输出数据范畴,$U$ 为常数 $1000$;
- 空间复杂度:$O(1)$ 疏忽预处理质数空间,仅应用常数级别空间。
题解三(Euler 欧氏线性筛 + 二分查找)
只管咱们从 x * x 开始标记来缩小反复标记,但 Eratosthenes 筛选法还是会反复标记一个合数。举个例子,400 这个数不仅会被 2 标记一遍,还会被 5 标记,这就导致了大量的反复计算。
为了防止反复标记,咱们应用欧氏筛,它与埃氏筛不同的是:
- 标记过程不再仅对质数 prime 标记,而是对每个数 x 标记;
- 不再标记所有 x* x 的整数倍,而是标记 x 与“小于等于 x 的最小质因子的质数”的乘积,保障每个合数只被标记最小的质因子标记。
class Solution {
companion object {
// 1000 以内的质数列表
private val primes = getPrimes(1000)
// 线性筛求质数
private fun getPrimes(max: Int): IntArray {val primes = LinkedList<Int>()
val isPrime = BooleanArray(max + 1) {true}
for (num in 2..max) {// 查看是否为质数,这里不须要调用 isPrime() 函数判断是否质数,因为它没被小于它的数标记过,那么肯定不是合数
if (isPrime[num]) {primes.add(num)
}
// 标记
for (prime in primes) {if (num * prime > max) break
isPrime[num * prime] = false
if (num % prime == 0) break
}
}
return primes.toIntArray()}
}
fun primeSubOperation(nums: IntArray): Boolean {
val n = nums.size
if (n <= 1) return true
for (index in n - 2 downTo 0) {if (nums[index] < nums[index + 1]) continue
// 二分查找
var left = 0
var right = primes.size - 1
while (left < right) {val mid = (left + right) ushr 1
if (primes[mid] >= nums[index] || nums[index] - primes[mid] < nums[index + 1]) {right = mid} else {left = mid + 1}
}
if (primes[left] >= nums[index] || nums[index] - primes[left] >= nums[index + 1]) return false
nums[index] -= primes[left]
}
return true
}
}
复杂度剖析:
- 工夫复杂度:$O(U + nlgU)$ 其中 $n$ 是 $nums$ 数组的长度,$U$ 是输出数据范畴,$U$ 为常数 $1000$;
- 空间复杂度:$O(1)$ 疏忽预处理质数空间,仅应用常数级别空间。
类似题目:
- 204. 计数质数
- 2523. 范畴内最靠近的两个质数
2601. 使数组元素全副相等的起码操作次数(Medium)
题目地址
https://leetcode.cn/problems/minimum-operations-to-make-all-a…
题目形容
给你一个正整数数组 nums
。
同时给你一个长度为 m
的整数数组 queries
。第 i
个查问中,你须要将 nums
中所有元素变成 queries[i]
。你能够执行以下操作 任意 次:
- 将数组里一个元素 增大 或者 减小
1
。
请你返回一个长度为 m
的数组 answer
,其中 answer[i]
是将 nums
中所有元素变成 queries[i]
的 起码 操作次数。
留神,每次查问后,数组变回最开始的值。
题解(前缀和 + 二分查找)
一道题很显著有前缀和问题,难点也正是如何把原问题转换为前缀和问题。
如果用暴力解法,咱们只须要计算每个元素到 queries[i] 的绝对值之和,单词查问操作的工夫复杂度是 O(n),咱们不思考。
为了优化工夫复杂度,咱们剖析数据的特色:
以 nums = [3,1,6,8], query = 5
为例,小于 5 的 3 和 1 须要增大能力变为 5,大于 5 的 6 和 8 须要减小能力变为 5。因而咱们尝试将数组分为两局部 [3,1, | 6,8],须要执行加法的次数为 [+2,+4, | -1,-3]。
然而,咱们不须要累加这 n 个差值的绝对值,而是应用前缀和在 O(1) 工夫内疾速计算。如图所示,小于 5 的局部能够用“小于 5 的数字个数 5”–“小于 5 的数字之和”取得,大于 5 的局部能够用“大于 5 的数字之和”–“大于 5 的数字个数 5”计算:
而“小于 5 的数字之和”与“大于 5 的数字之和”是显著的区间求和,能够用前缀和数组在 O(1) 工夫复杂度解决。至此,咱们胜利将原问题转换为前缀和问题。
那么,剩下的问题是如何将数组拆分为两局部?
咱们发现对于单次查问来说,咱们能够应用疾速抉择算法在 O(lgn) 工夫内找到。然而题目不仅只有一次,所以咱们能够先对整个数组排序,再用二分查找找到枚举的宰割点。
最初一个细节,因为数组的输出范畴很大,所以前缀和数组要定义为 long 数组类型。
class Solution {fun minOperations(nums: IntArray, queries: IntArray): List<Long> {
val n = nums.size
// 排序
nums.sort()
// 前缀和
val preSums = LongArray(n + 1)
for (index in nums.indices) {preSums[index + 1] = nums[index] + preSums[index]
}
val ret = LinkedList<Long>()
for (target in queries) {
// 二分查找寻找大于等于 target 的第一个元素
var left = 0
var right = n - 1
while (left < right) {val mid = (left + right) ushr 1
if (nums[mid] < target) {left = mid + 1} else {right = mid}
}
val index = if (nums[left] >= target) left - 1 else left
val leftSum = 1L * (index + 1) * target - preSums[index + 1]
val rightSum = preSums[n] - preSums[index + 1] - 1L * (n - 1 - index) * target
ret.add(leftSum + rightSum)
}
return ret
}
}
复杂度剖析:
- 工夫复杂度:$O(nlgn + qlgn)$ 其中 $n$ 是 $nums$ 数组的长度,$q$ 是 $queries$ 数组的长度。总共会执行 $q$ 次查问操作,每次查问操作的工夫复杂度是 $O(lgn)$;
- 空间复杂度:$O(n)$ 前缀和数组空间。
近期周赛前缀和问题:
- 周赛 336. 统计漂亮子数组数目(Medium)
2602. 收集树中金币(Hard)
题目地址
https://leetcode.cn/problems/collect-coins-in-a-tree/
题目形容
给你一个 n
个节点的无向无根树,节点编号从 0
到 n - 1
。给你整数 n
和一个长度为 n - 1
的二维整数数组 edges
,其中 edges[i] = [ai, bi]
示意树中节点 ai
和 bi
之间有一条边。再给你一个长度为 n
的数组 coins
,其中 coins[i]
可能为 0
也可能为 1
,1
示意节点 i
处有一个金币。
一开始,你须要抉择树中任意一个节点登程。你能够执行下述操作任意次:
- 收集间隔以后节点间隔为
2
以内的所有金币,或者 - 挪动到树中一个相邻节点。
你须要收集树中所有的金币,并且回到登程节点,请你返回起码通过的边数。
如果你屡次通过一条边,每一次通过都会给答案加一。
准备常识
- 拓扑排序:
给定一个蕴含 n 个节点的有向图 G,咱们给出它的节点编号的一种排列,如果满足:对于图 G 中的任意一条有向边 (u,v),u 在排列中都呈现在 v 的后面。 那么称该排列是图 G 的「拓扑排序」。
- 拓扑排序的实现思路:
拓扑排序的惯例实现是 Kahn 拓扑排序算法,基于 BFS 搜寻和贪婪思维:每次从图中删除没有前驱的节点(入度为 0),并批改它指向的节点的入度,直到 BFS 队列为空完结。
题解(拓扑排序 + 模仿)
- 察看示例 1:从节点 2 登程,收集节点 0 处的金币,挪动到节点 3,收集节点 5 处的金币,而后挪动回节点 2。
- 察看示例 2:从节点 0 登程,收集节点 4 和 3 处的金币,挪动到节点 2 处,收集节点 7 处的金币,挪动回节点 0。
联合题目规定(收集间隔以后节点间隔为 2 以内的所有金币)和这 2 个示例剖析:最优门路必然不须要触达图的边缘,而只须要在图的外围局部来回试探(如示例 1 的节点 2 和节点 3,示例 2 的节点 0 和节点 2)。
- 1、拜访无金币的子树没有意义,咱们将整个子树剪枝;
- 2、叶子节点和间隔叶子节点间隔为 1 的节点都没有必要拜访,咱们将这些点剪枝;
剩下的点就是必须通过的外围点。再联合题目规定(你须要收集树中所有的金币,并且回到登程节点),且题目保障输出数据是非法的树,因而答案正好就是剩下局部边的数目 * 2。
class Solution {fun collectTheCoins(coins: IntArray, edges: Array<IntArray>): Int {
val n = coins.size
// 入度表
val inDegrees = IntArray(n)
// 领接表
val graph = HashMap<Int, MutableList<Int>>()
for (edge in edges) {graph.getOrPut(edge[0]) {LinkedList<Int>() }.add(edge[1])
graph.getOrPut(edge[1]) {LinkedList<Int>() }.add(edge[0])
inDegrees[edge[0]]++
inDegrees[edge[1]]++
}
// 残余的边
var left_edge = edges.size // n - 1
// 1、拓扑排序剪枝无金币子树
val queue = LinkedList<Int>()
for (node in 0 until n) {
// 题目是无向图,所以叶子结点的入度也是 1
if (inDegrees[node] == 1 && coins[node] == 0) {queue.offer(node)
}
}
while (!queue.isEmpty()) {
// 删除叶子结点
val node = queue.poll()
left_edge -= 1
// 批改相邻节点
for (edge in graph[node]!!) {if (--inDegrees[edge] == 1 && coins[edge] == 0) queue.offer(edge)
}
}
// 2、拓扑排序剪枝与叶子结点间隔不大于 2 的节点(裁剪 2 层)// 叶子节点
for (node in 0 until n) {if (inDegrees[node] == 1 && coins[node] == 1) {queue.offer(node)
}
}
for (node in queue) {
// 2.1 删除叶子结点
left_edge -= 1
// 2.2 删除到叶子结点间隔为 1 的节点
for (edge in graph[node]!!) {if (--inDegrees[edge] == 1) left_edge -= 1
}
}
// println(inDegrees.joinToString())
// coins=[0,0],edges=[[0,1]] 会减去所有节点导致呈现正数
return Math.max(left_edge * 2, 0)
}
}
复杂度剖析:
- 工夫复杂度:$O(n)$ 其中 $n$ 是 $coins$ 数组的长度;
- 空间复杂度:$O(n)$。
类似题目:
- 207. 课程表
- 2050. 并行课程 III
有用请反对,你们的反对是我继续分享有价值内容的能源。