大家好，我是小彭。
上周末是 LeetCode 第 338 場周賽，你參加了嗎？這場周賽覆寫的知識點很多，第四題稱得上是近期幾場周賽的天花闆。
目錄
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/description/
題目描述
袋子中裝有一些物品，每個物品上都标記着數字 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/description/
題目描述
給你一個下标從 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,�(�)]，時間複雜度是 �(�)
3、計算所有小于 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 開始标記，而是直接從 x _ x 開始标記，因為 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-array-elements-equal
題目描述
給你一個正整數數組 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
有用請支援，你們的支援是我持續分享有價值内容的動力。