大家好，我是小彭。
明天早上是 LeetCode 第 336 场周赛，你加入了吗？这场周赛整体品质比拟高，然而最初一题是老题，CV 能过。然而输出数据范畴被升高了，这操作也是没谁了。
2587. 统计范畴内的元音字符串数（Easy）
题目地址
https://leetcode.cn/problems/count-the-number-of-vowel-string…
题目形容
给你一个下标从 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-pref…
题目形容
给你一个下标从 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)$ 排序递归栈空间。
2589. 统计漂亮子数组数目（Medium）
题目地址
https://leetcode.cn/problems/count-the-number-of-beautiful-su…
题目形容
给你一个下标从 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 的子数组”个数，与以下题目相似：
- 1. 两数之和
- 560. 和为 K 的子数组
- 974. 和可被 K 整除的子数组
奢侈的解法咱们思考枚举所有子数组：
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，如果优先选择越晚的开始工夫（推延开机），那么越有可能被后续工作笼罩。能够用反证法证实：假如推延到最晚工夫 $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，排序递归栈空间 + $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)$ 排序递归栈空间 + 线段树空间。
题解三（线段树 + 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)$ 排序递归栈空间 + 线段树空间。