大家好，我是小彭。

今天早上是 LeetCode 第 336 场周赛，你参加了吗？这场周赛全体质量比较高，可是最后一题是老题，CV 能过。可是输入数据规模被下降了，这操作也是没谁了。

LeetCode 周赛 336，多少人直接 CV？

LeetCode 周赛 336，多少人直接 CV？

2587. 计算规模内的元音字符串数（Easy）

标题地址

leetcode.cn/problems/co…

标题描述

给你一个下标从0开端的字符串数组words和两个整数：left和right。

假如字符串以元音字母开头并以元音字母完毕，那么该字符串便是一个元音字符串，其间元音字母是'a'、'e'、'i'、'o'、'u'。

回来words[i]是元音字符串的数目，其间i在闭区间[left, right]内。

LeetCode 周赛 336，多少人直接 CV？

题解（模仿）

简单模仿题。

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(n)
  • 空间复杂度：O(1)O(1)

2588. 重排数组以得到最大前缀分数（Medium）

标题地址

leetcode.cn/problems/re…

标题描述

给你一个下标从0开端的整数数组nums。你能够将nums中的元素按任意次序重排（包括给定次序）。

令prefix为一个数组，它包括了nums重新排列后的前缀和。换句话说，prefix[i]是nums重新排列后下标从0到i的元素之和。nums的分数是prefix数组中正整数的个数。

回来能够得到的最大分数。

LeetCode 周赛 336，多少人直接 CV？

题解（贪心）

贪心思路：负数会下降前缀和，为了推延前缀和变小的速度，正权值应该放在尽或许前的方位，负权值放在尽或许后的方位，即对数组降序排序。

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(nlgn + n) 排序加线性遍历；
  • 空间复杂度：O(lgn)O(lgn) 排序递归栈空间。

2589. 计算美丽子数组数目（Medium）

标题地址

leetcode.cn/problems/co…

标题描述

给你一个下标从0开端的整数数组nums。每次操作中，你能够：

  • 挑选两个满意0 <= i, j < nums.length的不同下标i和j。
  • 挑选一个非负整数k，满意nums[i]和nums[j]在二进制下的第k位（下标编号从0开端）是1。
  • 将nums[i]和nums[j]都减去2k。

假如一个子数组内履行上述操作若干次后，该子数组能够变成一个全为0的数组，那么咱们称它是一个美丽的子数组。

请你回来数组nums中美丽子数组的数目。

子数组是一个数组中一段接连非空的元素序列。

LeetCode 周赛 336，多少人直接 CV？

题解一（滑动窗口）

剖析标题操作：当两个数在某一位都是 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(n2)O(n^2) 其间 nn 是 numsnums 数组的长度，在这道题中将超出时刻约束；
  • 空间复杂度：O(1)O(1)。

题解二（前缀和 + 散列表）

“和为 k 的子数组” 有 O(n)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) 线性遍历；
  • 空间复杂度：O(n)O(n) 散列表空间。

2590. 完结一切使命的最少时刻（Hard）

标题地址

leetcode.cn/problems/mi…

标题描述

你有一台电脑，它能够同时运转无数个使命。给你一个二维整数数组tasks，其间tasks[i] = [starti, endi, durationi]表明第i个使命需要在闭区间时刻段[starti, endi]内运转durationi个整数时刻点（但不需要接连）。

当电脑需要运转使命时，你能够打开电脑，假如空闲时，你能够将电脑封闭。

请你回来完结一切使命的情况下，电脑最少需要运转多少秒。

LeetCode 周赛 336，多少人直接 CV？

题解一（贪心）

这道题其实是 LCP 原题：LCP 32.批量处理使命

区间使命问题一般有依照 “开端时刻” 排序或 “完毕时刻” 排序两种排序方法：

  • 依照开端时刻排序： 关于使命 task，咱们无法判断应该优选挑选较早点时刻仍是较晚的时刻。
  • 依照完毕时刻排序： 关于使命 task，假如优先挑选越晚的开端时刻（推延开机），那么越有或许被后续使命掩盖。能够用反证法证明：假定推延到最晚时刻 taskendtask_{end} 不是最优解，即存在非最晚时刻 taskend−1task_{end – 1} 是最优解，那么关于下一个使命来说，假如它的开端时刻晚于 taskend−1task_{end – 1}，那么它就错过了一次开机时刻，说明 taskend−1task_{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)O(nlgn + nm) 其间 n 是使命个数，m 是使命的均匀时刻；
  • 空间复杂度：O(lgn+U)O(lgn + U) 其间 UU 是数据规模 2000，排序递归栈空间 + usedused 数组空间。

题解二（朴素线段树）

回忆题解一中的 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(nlgn + U + nU + nlgU) 线段树单次区间和操作是 O(lgU)O(lgU)，单次区间更新是 O(U)O(U)。其间 O(nlgn)O(nlgn) 是排序时刻，O(U)O(U) 是建树时刻，O(nU)O(nU) 是 nn 次区间更新，O(nlgU)O(nlgU) 是 nn 次区间查询；
  • 空间复杂度：O(lgn+U)O(lgn + U) 排序递归栈空间 + 线段树空间。

题解三（线段树 + Lazy）

朴素线段树的功能瓶颈在于：区间更新需要改动从根节点到叶子节点中一切与方针区间有交集的节点，因而单次区间更新操作的时刻复杂度是 O(n)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(nlgn + U + nlgU) 线段树单次区间和操作是 O(lgU)O(lgU)，单次区间更新是 O(lgU)O(lgU)；
  • 空间复杂度：O(lgn+U)O(lgn + U) 排序递归栈空间 + 线段树空间。