LeetCode 周賽 336，多少人直接 CV？
本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。
大家好，我是小彭。
今天早上是 LeetCode 第 336 場周賽，你參加了嗎？這場周賽整體質量比較高，但是最后一題是老題，CV 能過。但是輸入數據范圍被降低了，這操作也是沒誰了。
2587. 統計范圍內的元音字符串數（Easy）
題目地址
https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/
題目描述
給你一個下標從 0 開始的字符串數組 words 和兩個整數：left 和 right 。
如果字符串以元音字母開頭并以元音字母結尾，那么該字符串就是一個 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。
返回 words[i] 是元音字符串的數目，其中 i 在閉區間 [left, right] 內。
題解（模擬）
簡單模擬題。
class Solution {
fun vowelStrings(words: Array<String>, left: Int, right: Int): Int {
val set = hashSetOf('a', 'e', 'i', 'o', 'u')
var count = 0
for (index in left..right) {
val word = words[index]
if (set.contains(word[0]) && set.contains(word[word.length - 1])) count++
}
return count
}
}
復雜度分析：
- 時間復雜度：$O(n)$
- 空間復雜度：$O(1)$
2588. 重排數組以得到最大前綴分數（Medium）
題目地址
https://leetcode.cn/problems/rearrange-array-to-maximize-prefix-score/
題目描述
給你一個下標從 0 開始的整數數組 nums 。你可以將 nums 中的元素按 任意順序 重排（包括給定順序）。
令 prefix 為一個數組，它包含了 nums 重新排列后的前綴和。換句話說，prefix[i] 是 nums 重新排列后下標從 0 到 i 的元素之和。nums 的 分數 是 prefix 數組中正整數的個數。
返回可以得到的最大分數。
題解（貪心）
貪心思路：負數會降低前綴和，為了延緩前綴和變小的速度，正權值應該放在盡可能前的位置，負權值放在盡可能后的位置，即對數組降序排序。
class Solution {
fun maxScore(nums: IntArray): Int {
// 3 2 1 0 -1 -3 -3
// 3 5 6 6 5 2 -1
nums.sortDescending()
var preSum = 0L
for (index in nums.indices) {
preSum += nums[index]
if (preSum <= 0L) return index
}
return nums.size
}
}
復雜度分析：
- 時間復雜度：$O(nlgn + n)$ 排序加線性遍歷；
- 空間復雜度：$O(lgn)$ 排序遞歸?？臻g。
2589. 統計美麗子數組數目（Medium）
題目地址
https://leetcode.cn/problems/count-the-number-of-beautiful-subarrays/
題目描述
給你一個下標從 0 開始的整數數組nums 。每次操作中，你可以：
- 選擇兩個滿足
0 <= i, j < nums.length的不同下標i和j。 - 選擇一個非負整數
k，滿足nums[i]和nums[j]在二進制下的第k位（下標編號從 0 開始）是1。 - 將
nums[i]和nums[j]都減去2k。
如果一個子數組內執行上述操作若干次后，該子數組可以變成一個全為 0 的數組，那么我們稱它是一個 美麗 的子數組。
請你返回數組 nums 中 美麗子數組 的數目。
子數組是一個數組中一段連續 非空 的元素序列。
題解一（滑動窗口）
分析題目操作：當兩個數在某一位都是 1 時，可以執行一次消除操作。因此，在滿足題目要去的子數組中，所有位上 1 出現的次數要么是 0，要么是大于 0 的偶數，符合異或的性質。于是，我們可以將題目轉換為求 “異或值為 0 的子數組” 個數，與以下題目類似：
樸素的解法我們考慮枚舉所有子數組：
class Solution {
fun beautifulSubarrays(nums: IntArray): Long {
val n = nums.size
var count = 0L
for (left in 0 until n) {
var xorSum = 0
for (right in left until n) {
xorSum = xorSum xor nums[right]
if (xorSum == 0) count++
}
}
return count
}
}
復雜度分析：
- 時間復雜度：$O(n^2)$ 其中 $n$ 是 $nums$ 數組的長度，在這道題中將超出時間限制；
- 空間復雜度：$O(1)$。
題解二（前綴和 + 散列表）
“和為 k 的子數組” 有 $O(n)$ 的解法：
class Solution {
fun beautifulSubarrays(nums: IntArray): Long {
val n = nums.size
var count = 0L
// xorSun - index
val xorSumMap = HashMap<Int, Int>().apply {
this[0] = 1
}
var preXorSum = 0
for (num in nums) {
preXorSum = preXorSum xor num
if (xorSumMap.containsKey(preXorSum)) {
count += xorSumMap[preXorSum]!!
}
xorSumMap[preXorSum] = xorSumMap.getOrDefault(preXorSum, 0) + 1
}
return count
}
}
復雜度分析：
- 時間復雜度：$O(n)$ 線性遍歷；
- 空間復雜度：$O(n)$ 散列表空間。
2590. 完成所有任務的最少時間（Hard）
題目地址
https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/
題目描述
你有一臺電腦，它可以 同時 運行無數個任務。給你一個二維整數數組 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 個任務需要在 閉區間 時間段 [starti, endi] 內運行 durationi 個整數時間點（但不需要連續）。
當電腦需要運行任務時，你可以打開電腦，如果空閑時，你可以將電腦關閉。
請你返回完成所有任務的情況下，電腦最少需要運行多少秒。
題解一（貪心）
這道題其實是 LCP 原題：LCP 32. 批量處理任務
區間任務問題一般有按照 “開始時間” 排序或 “結束時間” 排序兩種排序方法：
- 按照開始時間排序： 對于任務 task，我們無法判斷應該優選選擇較早點時間還是較晚的時間。
- 按照結束時間排序： 對于任務 task，如果優先選擇越晚的開始時間（推遲開機），那么越有可能被后續任務覆蓋?？梢杂梅醋C法證明：假設推遲到最晚時間 $task_{end}$ 不是最優解，即存在非最晚時間 $task_{end - 1}$ 是最優解，那么對于下一個任務來說，如果它的開始時間晚于 $task_{end - 1}$，那么它就錯過了一次開機時間，說明 $task_{end - 1}$ 不可能是最優解。
另外，由于任務的開機時間允許不連續，所以我們需要用一個額外的數組存儲開機時間。在處理每個任務時，我們先講已開始時間去掉，再將剩下的時間安排在盡可能晚的時間。
class Solution {
fun findMinimumTime(tasks: Array<IntArray>): Int {
// 按照結束時間排序
Arrays.sort(tasks) { e1, e2 ->
e1[1] - e2[1]
}
val used = BooleanArray(2001)
var time = 0
for (task in tasks) {
var count = task[2]
// 消除已開機時間
for (index in task[0]..task[1]) {
if (used[index]) count--
}
if (count <= 0) continue
time += count
// 推遲最晚開機時間
for (index in task[1] downTo task[0]) {
if (used[index]) continue
used[index] = true
if (--count == 0) break
}
}
return time
}
}
復雜度分析：
- 時間復雜度：$O(nlgn + nm)$ 其中 n 是任務個數，m 是任務的平均時間；
- 空間復雜度：$O(lgn + U)$ 其中 $U$ 是數據范圍 2000，排序遞歸?？臻g + $used$ 數組空間。
題解二（樸素線段樹）
回顧題解一中的 2個關鍵操作：
- 1、消除已開機時間： 計算 [start, end] 之間為 true 的時間點個數（等價于區間和）；
- 2、推遲最晚開機時間： 逆序將 [start, end] 中最后 count 個時間點標記為 true（等價于區間更新）。
因此，我們發現題目可能存在線段樹、樹狀數組之類優化手段：類似的區間求和問題，我們先回顧一下解決方案：
- 1、靜態數組求區間和：「前綴和數組」、「樹狀數組」、「線段樹」
- 2、頻繁單點更新，求區間和：「樹狀數組」、「線段樹」
- 3、頻繁區間更新，求具體位置：「差分數組」
- 4、頻繁區間更新，求區間和：「線段樹 + 懶更新」
這道題涉及 “區間更新” 和 “區間求和”，所以屬于線段樹的覆蓋范圍。相對于在函數中重復傳遞節點所代表的區間范圍（例如 update(i: int, l: int, r: int, L: int, R: int)），使用 Node 節點記錄更為方便。
class Solution {
fun findMinimumTime(tasks: Array<IntArray>): Int {
// 按照結束時間排序
Arrays.sort(tasks) { e1, e2 ->
e1[1] - e2[1]
}
// 線段樹
val tree = SegmentTree(2001)
for (task in tasks) {
// 消除已開機時間
val count = task[2] - tree.query(task[0], task[1])
if (count <= 0) continue
// 推遲最晚開機時間
tree.update(task[0], task[1], count)
}
// 根節點即為所有開機時間
return tree.query(1, 2000)
}
private class SegmentTree(private val n: Int) {
// 線段樹節點（區間范圍與區間值）
private class Node(val left: Int, val right: Int, var value: Int)
// 線段樹數組
private val tree = Array<Node?>(n * 4) { null } as Array<Node>
// 左子節點索引
private val Int.left get() = 2 * this + 1
// 右子節點索引
private val Int.right get() = 2 * this + 2
init {
// 建樹
buildNode(0, 0, n - 1)
}
private fun buildNode(index: Int, left: Int, right: Int) {
// 葉子節點
if (left == right) {
tree[index] = Node(left, right, 0)
return
}
val mid = (left + right) ushr 1
// 構建左子節點
buildNode(index.left, left, mid)
// 構建右子節點
buildNode(index.right, mid + 1, right)
// 合并左右子節點
tree[index] = Node(left, right, tree[index.left].value + tree[index.right].value)
}
// 開機（推遲到最晚時間）
fun update(left: Int, right: Int, count: Int) {
update(0, left, right, count)
}
// return：有效修改個數
private fun update(index: Int, left: Int, right: Int, count: Int): Int {
// 1、當前節點不處于區間內
if (tree[index].left > right || tree[index].right < left) return 0
// 2、葉子結點
if (tree[index].left == tree[index].right) {
// 開機
if (0 == tree[index].value) {
tree[index].value = 1
return 1
} else {
return 0
}
}
// 3、更新右子樹（貪心思路：推遲開機）
var realUpdate = update(index.right, left, right, count)
if (count - realUpdate > 0) {
// 4、更新左子樹
realUpdate += update(index.left, left, right, count - realUpdate)
}
// 5、合并左右子節點
tree[index].value = tree[index.left].value + tree[index.right].value
return realUpdate
}
// 查詢
fun query(left: Int, right: Int): Int {
return query(0, left, right)
}
private fun query(index: Int, left: Int, right: Int): Int {
// 1、當前節點不處于區間范圍內
if (tree[index].left > right || tree[index].right < left) return 0
// 2、當前節點完全處于區間范圍內
if (tree[index].left >= left && tree[index].right <= right) return tree[index].value
// 3、合并左右子節點
return query(index.left, left, right) + query(index.right, left, right)
}
}
}
復雜度分析：
- 時間復雜度：$O(nlgn + U + nU + nlgU)$ 線段樹單次區間和操作是 $O(lgU)$，單次區間更新是 $O(U)$。其中 $O(nlgn)$ 是排序時間，$O(U)$ 是建樹時間，$O(nU)$ 是 $n$ 次區間更新，$O(nlgU)$ 是 $n$ 次區間查詢；
- 空間復雜度：$O(lgn + U)$ 排序遞歸?？臻g + 線段樹空間。
題解三（線段樹 + Lazy）
樸素線段樹的性能瓶頸在于：區間更新需要改動從根節點到葉子節點中所有與目標區間有交集的節點，因此單次區間更新操作的時間復雜度是 $O(n)$。
懶更新線段樹的核心思想是：當一個節點代表的區間完全包含于目標區間內時，我們沒有必要繼續向下遞歸更新，而是在當前節點上標記 Lazy Tag 。只有將來更新該節點的某個子區間時，才會將懶更新 pushdown 到子區間。
class Solution {
fun findMinimumTime(tasks: Array<IntArray>): Int {
// 按照結束時間排序
Arrays.sort(tasks) { e1, e2 ->
e1[1] - e2[1]
}
// 線段樹
val tree = SegmentTree(2001)
for (task in tasks) {
// 消除已開機時間
val count = task[2] - tree.query(task[0], task[1])
if (count <= 0) continue
// 推遲最晚開機時間
tree.update(task[0], task[1], count)
}
// 根節點即為所有開機時間
return tree.query(1, 2000)
}
private class SegmentTree(private val n: Int) {
// 線段樹節點（區間范圍與區間值）
private class Node(val left: Int, val right: Int, var value: Int, var lazy: Boolean = false)
// 線段樹數組
private val tree = Array<Node?>(n * 4) { null } as Array<Node>
// 左子節點索引
private val Int.left get() = 2 * this + 1
// 右子節點索引
private val Int.right get() = 2 * this + 2
init {
// 建樹
buildNode(0, 0, n - 1)
}
private fun buildNode(index: Int, left: Int, right: Int) {
// 葉子節點
if (left == right) {
tree[index] = Node(left, right, 0)
return
}
val mid = (left + right) ushr 1
// 構建左子節點
buildNode(index.left, left, mid)
// 構建右子節點
buildNode(index.right, mid + 1, right)
// 合并左右子節點
tree[index] = Node(left, right, tree[index.left].value + tree[index.right].value)
}
// 開機（推遲到最晚時間）
fun update(left: Int, right: Int, count: Int) {
update(0, left, right, count)
}
// return：有效修改個數
private fun update(index: Int, left: Int, right: Int, count: Int): Int {
// 1、當前節點不處于區間內
if (tree[index].left > right || tree[index].right < left) return 0
val size = tree[index].right - tree[index].left + 1
val unUsedSize = size - tree[index].value
if (unUsedSize == 0) return 0 // 整個區間已開機
// 2、當前節點完全處于區間范圍之內
if (tree[index].left >= left && tree[index].right <= right && unUsedSize <= count) {
// 整個區間可以改為開機
lazyUpdate(index)
return unUsedSize
}
// pushdown
if (tree[index].lazy) {
lazyUpdate(index.left)
lazyUpdate(index.right)
tree[index].lazy = false
}
// 3、更新右子樹（貪心思路：推遲開機）
var realUpdate = update(index.right, left, right, count)
if (count - realUpdate > 0) {
// 4、更新左子樹
realUpdate += update(index.left, left, right, count - realUpdate)
}
// 5、合并左右子節點
tree[index].value = tree[index.left].value + tree[index.right].value
return realUpdate
}
private fun lazyUpdate(index: Int) {
tree[index].value = tree[index].right - tree[index].left + 1
tree[index].lazy = true
}
// 查詢
fun query(left: Int, right: Int): Int {
return query(0, left, right)
}
private fun query(index: Int, left: Int, right: Int): Int {
// 1、當前節點不處于區間范圍內
if (tree[index].left > right || tree[index].right < left) return 0
// 2、當前節點完全處于區間范圍內
if (tree[index].left >= left && tree[index].right <= right) return tree[index].value
// pushdown
if (tree[index].lazy) {
lazyUpdate(index.left)
lazyUpdate(index.right)
tree[index].lazy = false
}
// 3、合并左右子節點
return query(index.left, left, right) + query(index.right, left, right)
}
}
}
復雜度分析：
- 時間復雜度：$O(nlgn + U + nlgU)$ 線段樹單次區間和操作是 $O(lgU)$，單次區間更新是 $O(lgU)$；
- 空間復雜度：$O(lgn + U)$ 排序遞歸?？臻g + 線段樹空間。
