大家好漫雕，我是小彭。
上周末是 LeetCode 第 338 場周賽纫骑，你參加了嗎蝎亚？這場周賽覆蓋的知識點(diǎn)很多，第四題稱得上是近期幾場周賽的天花板先馆。
目錄
2599. K 件物品的最大和（Easy）
- 貪心发框、模擬
2600. 質(zhì)數(shù)減法運(yùn)算（Medium）
- 題解一：暴力枚舉 + 二分查找
- 題解二：Eratosthenes 埃氏篩 + 二分查找
- 題解三：Euler 歐氏線性篩 + 二分查找
2601. 使數(shù)組元素全部相等的最少操作次數(shù)
- 前綴和 + 二分查找
2602. 收集樹中金幣（Hard）
- 拓?fù)渑判?+ 模擬
2599. K 件物品的最大和（Easy）
題目地址
https://leetcode.cn/problems/k-items-with-the-maximum-sum/description/
題目描述
袋子中裝有一些物品，每個物品上都標(biāo)記著數(shù)字 1 、0 或 -1 梅惯。
給你四個非負(fù)整數(shù) numOnes 宪拥、numZeros 、numNegOnes 和 k 铣减。
袋子最初包含：
-
numOnes件標(biāo)記為1的物品她君。 -
numZeroes件標(biāo)記為0的物品。 -
numNegOnes件標(biāo)記為1的物品葫哗。
現(xiàn)計(jì)劃從這些物品中恰好選出 k 件物品缔刹。返回所有可行方案中，物品上所標(biāo)記數(shù)字之和的最大值劣针。
題解（貪心 + 模擬）
簡單模擬題校镐，優(yōu)先選擇 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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
2600. 質(zhì)數(shù)減法運(yùn)算（Medium）
題目地址
https://leetcode.cn/problems/prime-subtraction-operation/description/
題目描述
給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums ，數(shù)組長度為 n 襟己。
你可以執(zhí)行無限次下述運(yùn)算：
- 選擇一個之前未選過的下標(biāo)
i引谜，并選擇一個 嚴(yán)格小于nums[i]的質(zhì)數(shù)p，從nums[i]中減去p擎浴。
如果你能通過上述運(yùn)算使得 nums 成為嚴(yán)格遞增數(shù)組员咽，則返回 true ；否則返回 false 退客。
嚴(yán)格遞增數(shù)組 中的每個元素都嚴(yán)格大于其前面的元素骏融。
預(yù)備知識
這道題如果熟悉質(zhì)數(shù)篩就是簡單二分查找問題。
1萌狂、質(zhì)數(shù)定義：
- 質(zhì)數(shù) / 素?cái)?shù)：只能被 1 和本身整除的數(shù)，例如 3怀泊，5茫藏，7；
- 合數(shù)：除了能被 1 和本身整除外霹琼，還能被其他數(shù)整除的數(shù)务傲。也可以理解為由多個不為 1 的質(zhì)數(shù)相乘組成的數(shù)，例如 4 = 2 _ 2枣申，6 = 2 _ 3售葡。
- 1 既不是質(zhì)數(shù)也不是合數(shù)。
2忠藤、判斷 x 是否為質(zhì)數(shù)：
可以枚舉 [2,n-1] 的所有數(shù)挟伙，檢查是否是 x 的因數(shù)，時間復(fù)雜度是 O(n)模孩。事實(shí)上并不需要枚舉到 n-1：以 n = 17 為例尖阔，假設(shè)從 2 枚舉到 4 都沒有發(fā)現(xiàn)因子贮缅，我們發(fā)現(xiàn) 5 也沒必要檢查。
可以用反證法證明：如果 17 能夠被 5 整除介却，那么一定存在 17 能夠被 17/5 的另一個數(shù)整除谴供。而由于 17/5 < 5 與前面驗(yàn)證過 [2,4] 不存在因子的前提矛盾。因此 5 不可能是因子齿坷。
由此得出桂肌，如果存在整除關(guān)系 n/x = y，我們只需要檢查 x 和 y 之間的較小值永淌。所有的較小值最大不會超過 n 的平方根轴或。所以我們可以縮小檢查范圍，只檢查 仰禀，時間復(fù)雜度是
3照雁、計(jì)算所有小于 n 的質(zhì)數(shù)，有三種算法：
-
暴力枚舉： 枚舉每個數(shù)答恶，判斷它是不是質(zhì)數(shù)饺蚊，整體時間復(fù)雜度是
- Eratosthenes 埃氏篩： 如果 x 不是質(zhì)數(shù)，則從 x*x 開始將成倍的數(shù)字標(biāo)記為非質(zhì)數(shù)悬嗓，整體時間復(fù)雜度是 O(UlgU)污呼；
- Euler 歐氏線性篩： 標(biāo)記 x 與 “小于等于 x 的最小質(zhì)因子的質(zhì)數(shù)” 的乘積為非質(zhì)數(shù)，保證每個合數(shù)只被標(biāo)記最小的質(zhì)因子標(biāo)記包竹。
題解一（暴力枚舉質(zhì)數(shù) + 二分查找）
為了獲得嚴(yán)格遞增數(shù)組燕酷，顯然數(shù)組的末位元素的約束是最弱的，甚至是沒有約束的周瞎。所以我們選擇從后往前處理苗缩，最后一個數(shù)不需要處理。
顯然如果靠后的元素盡可能大声诸，那么靠前的元素越容易滿足條件酱讶。因此，我們可以找到貪心思路：從后往前處理彼乌，每處理一個數(shù)字時泻肯，我們盡可能減去滿足題目要求的最小質(zhì)數(shù)，減緩數(shù)字變小的速度慰照，給靠前的數(shù)字留出空間灶挟。
容易發(fā)現(xiàn)，“滿足題目要求的最小質(zhì)數(shù)” 存在單調(diào)性可以用二分查找解決毒租。因此我們的題解分為 2 部分：
- 1稚铣、預(yù)處理題目數(shù)據(jù)范圍內(nèi)的所有質(zhì)數(shù)，即小于 1000 的質(zhì)數(shù)列表，可以用預(yù)置知識中的兩種榛泛；
- 2蝌蹂、使用二分查找尋找 “滿足題目要求的最小質(zhì)數(shù)”。
class Solution {
companion object {
// 1000 以內(nèi)的質(zhì)數(shù)列表
private val primes = getPrimes(1000)
// 暴力求質(zhì)數(shù)
private fun getPrimes(max: Int): IntArray {
val primes = LinkedList<Int>()
for (num in 2..max) {
if (isPrime(num)) primes.add(num)
}
return primes.toIntArray()
}
// 質(zhì)數(shù)判斷
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
// 二分查找：尋找嚴(yán)格小于 nums[index] 且減去后形成遞增的最小質(zhì)數(shù)
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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
是
數(shù)組的長度曹锨，
是輸入數(shù)據(jù)范圍孤个，
；
- 空間復(fù)雜度：
忽略預(yù)處理質(zhì)數(shù)空間沛简，僅使用常數(shù)級別空間齐鲤。
題解二（Eratosthenes 埃氏篩 + 二分查找）
計(jì)算質(zhì)數(shù)的部分可以用經(jīng)典埃氏篩。
篩法求質(zhì)數(shù)的思路是：如果 x 是質(zhì)數(shù)椒楣，那么 x 的整數(shù)倍 2x给郊、3x 一定不是質(zhì)數(shù)。我們設(shè) isPrime[i] 表示 i 是否為質(zhì)數(shù)捧灰，從小開始遍歷淆九，如果 i 是質(zhì)數(shù)，則同時將所有倍數(shù)標(biāo)記為合數(shù)毛俏。事實(shí)上炭庙，我們不必從 x 開始標(biāo)記，而是直接從 x*x 開始標(biāo)記煌寇，因?yàn)?x * 2, x * 3 已經(jīng)在之前被標(biāo)記過焕蹄，會重復(fù)標(biāo)記。
class Solution {
companion object {
// 1000 以內(nèi)的質(zhì)數(shù)列表
private val primes = getPrimes(1000)
// 埃氏篩求質(zhì)數(shù)
private fun getPrimes(max: Int): IntArray {
val primes = LinkedList<Int>()
val isPrime = BooleanArray(max + 1) { true }
for (num in 2..max) {
// 檢查是否為質(zhì)數(shù)阀溶，這里不需要調(diào)用 isPrime() 函數(shù)判斷是否質(zhì)數(shù)腻脏，因?yàn)樗鼪]被小于它的數(shù)標(biāo)記過，那么一定不是合數(shù)
if (!isPrime[num]) continue
primes.add(num)
// 標(biāo)記
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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
- 空間復(fù)雜度：
題解三（Euler 歐氏線性篩 + 二分查找）
盡管我們從 x * x 開始標(biāo)記來減少重復(fù)標(biāo)記，但 Eratosthenes 篩選法還是會重復(fù)標(biāo)記一個合數(shù)掉弛。舉個例子，400 這個數(shù)不僅會被 2 標(biāo)記一遍喂走，還會被 5 標(biāo)記殃饿，這就導(dǎo)致了大量的重復(fù)計(jì)算。
為了避免重復(fù)標(biāo)記芋肠，我們使用歐氏篩乎芳，它與埃氏篩不同的是：
- 標(biāo)記過程不再僅對質(zhì)數(shù) prime 標(biāo)記，而是對每個數(shù) x 標(biāo)記；
- 不再標(biāo)記所有 x* x 的整數(shù)倍奈惑，而是標(biāo)記 x 與 “小于等于 x 的最小質(zhì)因子的質(zhì)數(shù)” 的乘積吭净，保證每個合數(shù)只被標(biāo)記最小的質(zhì)因子標(biāo)記。
class Solution {
companion object {
// 1000 以內(nèi)的質(zhì)數(shù)列表
private val primes = getPrimes(1000)
// 線性篩求質(zhì)數(shù)
private fun getPrimes(max: Int): IntArray {
val primes = LinkedList<Int>()
val isPrime = BooleanArray(max + 1) { true }
for (num in 2..max) {
// 檢查是否為質(zhì)數(shù)肴甸，這里不需要調(diào)用 isPrime() 函數(shù)判斷是否質(zhì)數(shù)寂殉，因?yàn)樗鼪]被小于它的數(shù)標(biāo)記過，那么一定不是合數(shù)
if (isPrime[num]) {
primes.add(num)
}
// 標(biāo)記
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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
- 空間復(fù)雜度：
相似題目：
2601. 使數(shù)組元素全部相等的最少操作次數(shù)（Medium）
題目地址
https://leetcode.cn/problems/minimum-operations-to-make-all-array-elements-equal
題目描述
給你一個正整數(shù)數(shù)組 nums 。
同時給你一個長度為 m 的整數(shù)數(shù)組 queries 浮庐。第 i 個查詢中甚负，你需要將 nums 中所有元素變成 queries[i] 。你可以執(zhí)行以下操作 任意 次：
- 將數(shù)組里一個元素 增大 或者 減小
1审残。
請你返回一個長度為 m 的數(shù)組 **answer 梭域，其中 **answer[i]是將 nums 中所有元素變成 queries[i] 的 最少 操作次數(shù)。
注意维苔，每次查詢后碰辅，數(shù)組變回最開始的值。
題解（前綴和 + 二分查找）
一道題很明顯有前綴和問題介时，難點(diǎn)也正是如何把原問題轉(zhuǎn)換為前綴和問題没宾。
如果用暴力解法，我們只需要計(jì)算每個元素到 queries[i] 的絕對值之和沸柔，單詞查詢操作的時間復(fù)雜度是 O(n)循衰，我們不考慮。
為了優(yōu)化時間復(fù)雜度褐澎，我們分析數(shù)據(jù)的特征：
以 nums = [3,1,6,8], query = 5 為例会钝，小于 5 的 3 和 1 需要增大才能變?yōu)?5，大于 5 的 6 和 8 需要減小才能變?yōu)?5工三。因此我們嘗試將數(shù)組分為兩部分 [3,1, | 6,8]迁酸，需要執(zhí)行加法的次數(shù)為 [+2,+4, | -1,-3]。
然而俭正，我們不需要累加這 n 個差值的絕對值奸鬓，而是使用前綴和在 O(1) 時間內(nèi)快速計(jì)算。如圖所示掸读，小于 5 的部分可以用 “小于 5 的數(shù)字個數(shù) _ 5” - “小于 5 的數(shù)字之和” 獲得串远，大于 5 的部分可以用 “大于 5 的數(shù)字之和” - “大于 5 的數(shù)字個數(shù) _ 5” 計(jì)算：
而 “小于 5 的數(shù)字之和” 與 “大于 5 的數(shù)字之和” 是明顯的區(qū)間求和宏多，可以用前綴和數(shù)組在 O(1) 時間復(fù)雜度解決。至此澡罚，我們成功將原問題轉(zhuǎn)換為前綴和問題伸但。
那么，剩下的問題是如何將數(shù)組拆分為兩部分留搔？
我們發(fā)現(xiàn)對于單次查詢來說更胖，我們可以使用快速選擇算法在 O(lgn) 時間內(nèi)找到。但是題目不僅只有一次催式，所以我們可以先對整個數(shù)組排序函喉，再用二分查找找到枚舉的分割點(diǎn)。
最后一個細(xì)節(jié)荣月，由于數(shù)組的輸入范圍很大管呵，所以前綴和數(shù)組要定義為 long 數(shù)組類型和簸。
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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
是
數(shù)組的長度似谁〕冢總共會執(zhí)行
窑业；
- 空間復(fù)雜度：
前綴和數(shù)組空間撤嫩。
近期周賽前綴和問題：
2602. 收集樹中金幣（Hard）
題目地址
https://leetcode.cn/problems/collect-coins-in-a-tree/
題目描述
給你一個 n 個節(jié)點(diǎn)的無向無根樹配名，節(jié)點(diǎn)編號從 0 到 n - 1 生年。給你整數(shù) n 和一個長度為 n - 1 的二維整數(shù)數(shù)組 edges 婴程，其中 edges[i] = [ai, bi] 表示樹中節(jié)點(diǎn) ai 和 bi 之間有一條邊。再給你一個長度為 n 的數(shù)組 coins 抱婉，其中 coins[i] 可能為 0 也可能為 1 档叔，1 表示節(jié)點(diǎn) i 處有一個金幣。
一開始蒸绩，你需要選擇樹中任意一個節(jié)點(diǎn)出發(fā)衙四。你可以執(zhí)行下述操作任意次：
- 收集距離當(dāng)前節(jié)點(diǎn)距離為
2以內(nèi)的所有金幣，或者 - 移動到樹中一個相鄰節(jié)點(diǎn)患亿。
你需要收集樹中所有的金幣传蹈，并且回到出發(fā)節(jié)點(diǎn)，請你返回最少經(jīng)過的邊數(shù)步藕。
如果你多次經(jīng)過一條邊惦界，每一次經(jīng)過都會給答案加一。
預(yù)備知識
- 拓?fù)渑判颍?/strong>
給定一個包含 n 個節(jié)點(diǎn)的有向圖 G咙冗，我們給出它的節(jié)點(diǎn)編號的一種排列表锻，如果滿足： 對于圖 G 中的任意一條有向邊 (u,v)，u 在排列中都出現(xiàn)在 v 的前面乞娄。 那么稱該排列是圖 G 的「拓?fù)渑判颉埂?/p>
- 拓?fù)渑判虻膶?shí)現(xiàn)思路：
拓?fù)渑判虻某Ｒ?guī)實(shí)現(xiàn)是 Kahn 拓?fù)渑判蛩惴ㄋ惭罚?BFS 搜索和貪心思想：每次從圖中刪除沒有前驅(qū)的節(jié)點(diǎn)（入度為 0），并修改它指向的節(jié)點(diǎn)的入度仪或，直到 BFS 隊(duì)列為空結(jié)束确镊。
題解（拓?fù)渑判?+ 模擬）
- 觀察示例 1：從節(jié)點(diǎn) 2 出發(fā)，收集節(jié)點(diǎn) 0 處的金幣范删，移動到節(jié)點(diǎn) 3 蕾域，收集節(jié)點(diǎn) 5 處的金幣，然后移動回節(jié)點(diǎn) 2到旦。
- 觀察示例 2：從節(jié)點(diǎn) 0 出發(fā)旨巷，收集節(jié)點(diǎn) 4 和 3 處的金幣，移動到節(jié)點(diǎn) 2 處添忘，收集節(jié)點(diǎn) 7 處的金幣采呐，移動回節(jié)點(diǎn) 0。
結(jié)合題目規(guī)則（收集距離當(dāng)前節(jié)點(diǎn)距離為 2 以內(nèi)的所有金幣）和這 2 個示例分析： 最優(yōu)路徑必然不需要觸達(dá)圖的邊緣搁骑，而只需要在圖的核心部分來回試探 （如示例 1 的節(jié)點(diǎn) 2 和節(jié)點(diǎn) 3斧吐，示例 2 的節(jié)點(diǎn) 0 和節(jié)點(diǎn) 2）。
- 1仲器、訪問無金幣的子樹沒有意義煤率，我們將整個子樹剪枝；
- 2乏冀、葉子節(jié)點(diǎn)和距離葉子節(jié)點(diǎn)距離為 1 的節(jié)點(diǎn)都沒有必要訪問蝶糯，我們將這些點(diǎn)剪枝；
剩下的點(diǎn)就是必須經(jīng)過的核心點(diǎn)辆沦。再結(jié)合題目規(guī)則（你需要收集樹中所有的金幣昼捍，并且回到出發(fā)節(jié)點(diǎn)），且題目保證輸入數(shù)據(jù)是合法的樹众辨，因此答案正好就是剩下部分邊的數(shù)目 * 2端三。
class Solution {
fun collectTheCoins(coins: IntArray, edges: Array<IntArray>): Int {
val n = coins.size
// 入度表
val inDegrees = IntArray(n)
// 領(lǐng)接表
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、拓?fù)渑判蚣糁o金幣子樹
val queue = LinkedList<Int>()
for (node in 0 until n) {
// 題目是無向圖鹃彻，所以葉子結(jié)點(diǎn)的入度也是 1
if (inDegrees[node] == 1 && coins[node] == 0) {
queue.offer(node)
}
}
while (!queue.isEmpty()) {
// 刪除葉子結(jié)點(diǎn)
val node = queue.poll()
left_edge -= 1
// 修改相鄰節(jié)點(diǎn)
for (edge in graph[node]!!) {
if (--inDegrees[edge] == 1 && coins[edge] == 0) queue.offer(edge)
}
}
// 2郊闯、拓?fù)渑判蚣糁εc葉子結(jié)點(diǎn)距離不大于 2 的節(jié)點(diǎn)（裁剪 2 層）
// 葉子節(jié)點(diǎn)
for (node in 0 until n) {
if (inDegrees[node] == 1 && coins[node] == 1) {
queue.offer(node)
}
}
for (node in queue) {
// 2.1 刪除葉子結(jié)點(diǎn)
left_edge -= 1
// 2.2 刪除到葉子結(jié)點(diǎn)距離為 1 的節(jié)點(diǎn)
for (edge in graph[node]!!) {
if (--inDegrees[edge] == 1) left_edge -= 1
}
}
// println(inDegrees.joinToString())
// coins=[0,0],edges=[[0,1]] 會減去所有節(jié)點(diǎn)導(dǎo)致出現(xiàn)負(fù)數(shù)
return Math.max(left_edge * 2, 0)
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
數(shù)組的長度；
- 空間復(fù)雜度：
相似題目：
有用請支持团赁，你們的支持是我持續(xù)分享有價值內(nèi)容的動力。
