大家好入愧，我是小彭鄙漏。
今天早上是 LeetCode 第 336 場周賽嗤谚，你參加了嗎？這場周賽整體質(zhì)量比較高怔蚌，但是最后一題是老題巩步，CV 能過。但是輸入數(shù)據(jù)范圍被降低了桦踊，這操作也是沒誰了渗钉。
2587. 統(tǒng)計(jì)范圍內(nèi)的元音字符串?dāng)?shù)（Easy）
題目地址
https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/
題目描述
給你一個(gè)下標(biāo)從 0 開始的字符串?dāng)?shù)組 words 和兩個(gè)整數(shù)：left 和 right 。
如果字符串以元音字母開頭并以元音字母結(jié)尾钞钙，那么該字符串就是一個(gè) 元音字符串 鳄橘，其中元音字母是 'a'、'e'芒炼、'i'瘫怜、'o'、'u' 本刽。
返回 words[i] 是元音字符串的數(shù)目鲸湃，其中 i 在閉區(qū)間 [left, right] 內(nèi)。
題解（模擬）
簡單模擬題子寓。
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
2588. 重排數(shù)組以得到最大前綴分?jǐn)?shù)（Medium）
題目地址
https://leetcode.cn/problems/rearrange-array-to-maximize-prefix-score/
題目描述
給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 暗挑。你可以將 nums 中的元素按 任意順序 重排（包括給定順序）。
令 prefix 為一個(gè)數(shù)組斜友，它包含了 nums 重新排列后的前綴和炸裆。換句話說，prefix[i] 是 nums 重新排列后下標(biāo)從 0 到 i 的元素之和鲜屏。nums 的 分?jǐn)?shù) 是 prefix 數(shù)組中正整數(shù)的個(gè)數(shù)烹看。
返回可以得到的最大分?jǐn)?shù)。
題解（貪心）
貪心思路：負(fù)數(shù)會(huì)降低前綴和洛史，為了延緩前綴和變小的速度惯殊，正權(quán)值應(yīng)該放在盡可能前的位置，負(fù)權(quán)值放在盡可能后的位置也殖，即對數(shù)組降序排序土思。
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
排序加線性遍歷；
- 空間復(fù)雜度：
排序遞歸椧涫龋空間己儒。
2589. 統(tǒng)計(jì)美麗子數(shù)組數(shù)目（Medium）
題目地址
https://leetcode.cn/problems/count-the-number-of-beautiful-subarrays/
題目描述
給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組nums 。每次操作中霎褐，你可以：
- 選擇兩個(gè)滿足
0 <= i, j < nums.length的不同下標(biāo)i和j址愿。 - 選擇一個(gè)非負(fù)整數(shù)
k，滿足nums[i]和nums[j]在二進(jìn)制下的第k位（下標(biāo)編號(hào)從 0 開始）是1冻璃。 - 將
nums[i]和nums[j]都減去2k响谓。
如果一個(gè)子數(shù)組內(nèi)執(zhí)行上述操作若干次后损合，該子數(shù)組可以變成一個(gè)全為 0 的數(shù)組，那么我們稱它是一個(gè) 美麗 的子數(shù)組娘纷。
請你返回?cái)?shù)組 nums 中 美麗子數(shù)組 的數(shù)目嫁审。
子數(shù)組是一個(gè)數(shù)組中一段連續(xù) 非空 的元素序列。
題解一（滑動(dòng)窗口）
分析題目操作：當(dāng)兩個(gè)數(shù)在某一位都是 1 時(shí)赖晶，可以執(zhí)行一次消除操作律适。因此，在滿足題目要去的子數(shù)組中遏插，所有位上 1 出現(xiàn)的次數(shù)要么是 0捂贿，要么是大于 0 的偶數(shù)，符合異或的性質(zhì)胳嘲。于是厂僧，我們可以將題目轉(zhuǎn)換為求 “異或值為 0 的子數(shù)組” 個(gè)數(shù)，與以下題目類似：
樸素的解法我們考慮枚舉所有子數(shù)組：
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中
是
數(shù)組的長度了牛，在這道題中將超出時(shí)間限制颜屠；
- 空間復(fù)雜度：
。
題解二（前綴和 + 散列表）
“和為 k 的子數(shù)組” 有 的解法：
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
線性遍歷鹰祸；
- 空間復(fù)雜度：
2590. 完成所有任務(wù)的最少時(shí)間（Hard）
題目地址
https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/
題目描述
你有一臺(tái)電腦，它可以 同時(shí) 運(yùn)行無數(shù)個(gè)任務(wù)蛙婴。給你一個(gè)二維整數(shù)數(shù)組 tasks 粗井，其中 tasks[i] = [starti, endi, durationi] 表示第 i 個(gè)任務(wù)需要在 閉區(qū)間 時(shí)間段 [starti, endi] 內(nèi)運(yùn)行 durationi 個(gè)整數(shù)時(shí)間點(diǎn)（但不需要連續(xù)）。
當(dāng)電腦需要運(yùn)行任務(wù)時(shí)敬锐，你可以打開電腦背传，如果空閑時(shí)呆瞻，你可以將電腦關(guān)閉台夺。
請你返回完成所有任務(wù)的情況下，電腦最少需要運(yùn)行多少秒痴脾。
題解一（貪心）
這道題其實(shí)是 LCP 原題：LCP 32. 批量處理任務(wù)
區(qū)間任務(wù)問題一般有按照 “開始時(shí)間” 排序或 “結(jié)束時(shí)間” 排序兩種排序方法：
- 按照開始時(shí)間排序： 對于任務(wù) task颤介，我們無法判斷應(yīng)該優(yōu)選選擇較早點(diǎn)時(shí)間還是較晚的時(shí)間。
-
按照結(jié)束時(shí)間排序： 對于任務(wù) task赞赖，如果優(yōu)先選擇越晚的開始時(shí)間（推遲開機(jī)）滚朵，那么越有可能被后續(xù)任務(wù)覆蓋∏坝颍可以用反證法證明：假設(shè)推遲到最晚時(shí)間
不是最優(yōu)解辕近，即存在非最晚時(shí)間
是最優(yōu)解，那么對于下一個(gè)任務(wù)來說匿垄，如果它的開始時(shí)間晚于
另外漏峰，由于任務(wù)的開機(jī)時(shí)間允許不連續(xù)糠悼，所以我們需要用一個(gè)額外的數(shù)組存儲(chǔ)開機(jī)時(shí)間。在處理每個(gè)任務(wù)時(shí)浅乔，我們先講已開始時(shí)間去掉倔喂，再將剩下的時(shí)間安排在盡可能晚的時(shí)間。
class Solution {
fun findMinimumTime(tasks: Array<IntArray>): Int {
// 按照結(jié)束時(shí)間排序
Arrays.sort(tasks) { e1, e2 ->
e1[1] - e2[1]
}
val used = BooleanArray(2001)
var time = 0
for (task in tasks) {
var count = task[2]
// 消除已開機(jī)時(shí)間
for (index in task[0]..task[1]) {
if (used[index]) count--
}
if (count <= 0) continue
time += count
// 推遲最晚開機(jī)時(shí)間
for (index in task[1] downTo task[0]) {
if (used[index]) continue
used[index] = true
if (--count == 0) break
}
}
return time
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中 n 是任務(wù)個(gè)數(shù)靖苇，m 是任務(wù)的平均時(shí)間席噩；
- 空間復(fù)雜度：
其中
是數(shù)據(jù)范圍 2000，排序遞歸椣捅冢空間 +
數(shù)組空間班挖。
題解二（樸素線段樹）
回顧題解一中的 2個(gè)關(guān)鍵操作：
- 1、消除已開機(jī)時(shí)間： 計(jì)算 [start, end] 之間為 true 的時(shí)間點(diǎn)個(gè)數(shù)（等價(jià)于區(qū)間和）萧芙；
- 2、推遲最晚開機(jī)時(shí)間： 逆序?qū)?[start, end] 中最后 count 個(gè)時(shí)間點(diǎn)標(biāo)記為 true（等價(jià)于區(qū)間更新）渴邦。
因此瓮床，我們發(fā)現(xiàn)題目可能存在線段樹丑掺、樹狀數(shù)組之類優(yōu)化手段：類似的區(qū)間求和問題地粪，我們先回顧一下解決方案：
- 1旺聚、靜態(tài)數(shù)組求區(qū)間和：「前綴和數(shù)組」碱璃、「樹狀數(shù)組」、「線段樹」
- 2窄瘟、頻繁單點(diǎn)更新，求區(qū)間和：「樹狀數(shù)組」帕翻、「線段樹」
- 3泉蝌、頻繁區(qū)間更新劫映，求具體位置：「差分?jǐn)?shù)組」
- 4违孝、頻繁區(qū)間更新筹燕，求區(qū)間和：「線段樹 + 懶更新」
這道題涉及 “區(qū)間更新” 和 “區(qū)間求和”，所以屬于線段樹的覆蓋范圍。相對于在函數(shù)中重復(fù)傳遞節(jié)點(diǎn)所代表的區(qū)間范圍（例如 update(i: int, l: int, r: int, L: int, R: int)）边臼，使用 Node 節(jié)點(diǎn)記錄更為方便弛饭。
class Solution {
fun findMinimumTime(tasks: Array<IntArray>): Int {
// 按照結(jié)束時(shí)間排序
Arrays.sort(tasks) { e1, e2 ->
e1[1] - e2[1]
}
// 線段樹
val tree = SegmentTree(2001)
for (task in tasks) {
// 消除已開機(jī)時(shí)間
val count = task[2] - tree.query(task[0], task[1])
if (count <= 0) continue
// 推遲最晚開機(jī)時(shí)間
tree.update(task[0], task[1], count)
}
// 根節(jié)點(diǎn)即為所有開機(jī)時(shí)間
return tree.query(1, 2000)
}
private class SegmentTree(private val n: Int) {
// 線段樹節(jié)點(diǎn)（區(qū)間范圍與區(qū)間值）
private class Node(val left: Int, val right: Int, var value: Int)
// 線段樹數(shù)組
private val tree = Array<Node?>(n * 4) { null } as Array<Node>
// 左子節(jié)點(diǎn)索引
private val Int.left get() = 2 * this + 1
// 右子節(jié)點(diǎn)索引
private val Int.right get() = 2 * this + 2
init {
// 建樹
buildNode(0, 0, n - 1)
}
private fun buildNode(index: Int, left: Int, right: Int) {
// 葉子節(jié)點(diǎn)
if (left == right) {
tree[index] = Node(left, right, 0)
return
}
val mid = (left + right) ushr 1
// 構(gòu)建左子節(jié)點(diǎn)
buildNode(index.left, left, mid)
// 構(gòu)建右子節(jié)點(diǎn)
buildNode(index.right, mid + 1, right)
// 合并左右子節(jié)點(diǎn)
tree[index] = Node(left, right, tree[index.left].value + tree[index.right].value)
}
// 開機(jī)（推遲到最晚時(shí)間）
fun update(left: Int, right: Int, count: Int) {
update(0, left, right, count)
}
// return：有效修改個(gè)數(shù)
private fun update(index: Int, left: Int, right: Int, count: Int): Int {
// 1冕末、當(dāng)前節(jié)點(diǎn)不處于區(qū)間內(nèi)
if (tree[index].left > right || tree[index].right < left) return 0
// 2、葉子結(jié)點(diǎn)
if (tree[index].left == tree[index].right) {
// 開機(jī)
if (0 == tree[index].value) {
tree[index].value = 1
return 1
} else {
return 0
}
}
// 3侣颂、更新右子樹（貪心思路：推遲開機(jī)）
var realUpdate = update(index.right, left, right, count)
if (count - realUpdate > 0) {
// 4档桃、更新左子樹
realUpdate += update(index.left, left, right, count - realUpdate)
}
// 5、合并左右子節(jié)點(diǎn)
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憔晒、當(dāng)前節(jié)點(diǎn)不處于區(qū)間范圍內(nèi)
if (tree[index].left > right || tree[index].right < left) return 0
// 2藻肄、當(dāng)前節(jié)點(diǎn)完全處于區(qū)間范圍內(nèi)
if (tree[index].left >= left && tree[index].right <= right) return tree[index].value
// 3、合并左右子節(jié)點(diǎn)
return query(index.left, left, right) + query(index.right, left, right)
}
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
線段樹單次區(qū)間和操作是
丛晌，單次區(qū)間更新是
仅炊。其中
是排序時(shí)間，
是
是
- 空間復(fù)雜度：
題解三（線段樹 + Lazy）
樸素線段樹的性能瓶頸在于：區(qū)間更新需要改動(dòng)從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)中所有與目標(biāo)區(qū)間有交集的節(jié)點(diǎn)，因此單次區(qū)間更新操作的時(shí)間復(fù)雜度是 毁兆。
懶更新線段樹的核心思想是：當(dāng)一個(gè)節(jié)點(diǎn)代表的區(qū)間完全包含于目標(biāo)區(qū)間內(nèi)時(shí)浙滤，我們沒有必要繼續(xù)向下遞歸更新，而是在當(dāng)前節(jié)點(diǎn)上標(biāo)記 Lazy Tag 气堕。只有將來更新該節(jié)點(diǎn)的某個(gè)子區(qū)間時(shí)纺腊，才會(huì)將懶更新 pushdown 到子區(qū)間。
class Solution {
fun findMinimumTime(tasks: Array<IntArray>): Int {
// 按照結(jié)束時(shí)間排序
Arrays.sort(tasks) { e1, e2 ->
e1[1] - e2[1]
}
// 線段樹
val tree = SegmentTree(2001)
for (task in tasks) {
// 消除已開機(jī)時(shí)間
val count = task[2] - tree.query(task[0], task[1])
if (count <= 0) continue
// 推遲最晚開機(jī)時(shí)間
tree.update(task[0], task[1], count)
}
// 根節(jié)點(diǎn)即為所有開機(jī)時(shí)間
return tree.query(1, 2000)
}
private class SegmentTree(private val n: Int) {
// 線段樹節(jié)點(diǎn)（區(qū)間范圍與區(qū)間值）
private class Node(val left: Int, val right: Int, var value: Int, var lazy: Boolean = false)
// 線段樹數(shù)組
private val tree = Array<Node?>(n * 4) { null } as Array<Node>
// 左子節(jié)點(diǎn)索引
private val Int.left get() = 2 * this + 1
// 右子節(jié)點(diǎn)索引
private val Int.right get() = 2 * this + 2
init {
// 建樹
buildNode(0, 0, n - 1)
}
private fun buildNode(index: Int, left: Int, right: Int) {
// 葉子節(jié)點(diǎn)
if (left == right) {
tree[index] = Node(left, right, 0)
return
}
val mid = (left + right) ushr 1
// 構(gòu)建左子節(jié)點(diǎn)
buildNode(index.left, left, mid)
// 構(gòu)建右子節(jié)點(diǎn)
buildNode(index.right, mid + 1, right)
// 合并左右子節(jié)點(diǎn)
tree[index] = Node(left, right, tree[index.left].value + tree[index.right].value)
}
// 開機(jī)（推遲到最晚時(shí)間）
fun update(left: Int, right: Int, count: Int) {
update(0, left, right, count)
}
// return：有效修改個(gè)數(shù)
private fun update(index: Int, left: Int, right: Int, count: Int): Int {
// 1茎芭、當(dāng)前節(jié)點(diǎn)不處于區(qū)間內(nèi)
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 // 整個(gè)區(qū)間已開機(jī)
// 2揖膜、當(dāng)前節(jié)點(diǎn)完全處于區(qū)間范圍之內(nèi)
if (tree[index].left >= left && tree[index].right <= right && unUsedSize <= count) {
// 整個(gè)區(qū)間可以改為開機(jī)
lazyUpdate(index)
return unUsedSize
}
// pushdown
if (tree[index].lazy) {
lazyUpdate(index.left)
lazyUpdate(index.right)
tree[index].lazy = false
}
// 3、更新右子樹（貪心思路：推遲開機(jī)）
var realUpdate = update(index.right, left, right, count)
if (count - realUpdate > 0) {
// 4梅桩、更新左子樹
realUpdate += update(index.left, left, right, count - realUpdate)
}
// 5壹粟、合并左右子節(jié)點(diǎn)
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、當(dāng)前節(jié)點(diǎn)不處于區(qū)間范圍內(nèi)
if (tree[index].left > right || tree[index].right < left) return 0
// 2宿百、當(dāng)前節(jié)點(diǎn)完全處于區(qū)間范圍內(nèi)
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趁仙、合并左右子節(jié)點(diǎn)
return query(index.left, left, right) + query(index.right, left, right)
}
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
線段樹單次區(qū)間和操作是
- 空間復(fù)雜度：
