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

leetcode,多少,直接,cv · 浏览次数 : 243

小编点评

**线段树单次区间更新** 线段树的更新操作通常需要考虑该操作对整个树的性能影响。由于在更新操作中需要考虑所有与目标区间有交集的节点，传统线段树的更新操作会对整个树进行遍历，导致时间复杂度为 $O(n)$。 为了解决这个问题，一些优化方法被引入，包括懒更新和 lazy lifting。 **懒更新** 懒更新是一种在更新操作中只更新与目标区间的节点的方法。这种方法可以避免在更新操作过程中对整个树进行遍历，从而减少时间复杂度。 **lazy lifting** lazy lifting是一种在更新操作之前对目标区间的节点进行标记的方法。这种方法可以帮助提前处理与目标区间的节点，从而减少更新操作的成本。 **复杂度分析** * 线段树单次区间和操作是 $O(lgU)$ * 单次区间更新是 $O(lgU)$ * 懒更新的复杂度是 $O(lgU)$ * lazy lifting的复杂度是 $O(lgU)$ **总结** 线段树的更新操作通常需要考虑其对整个树的性能影响。通过使用懒更新和 lazy lifting等优化方法，可以有效地降低更新操作的成本，并最终获得线性时间复杂度。

正文

本文已收录到 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)$ 排序递归栈空间。

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，如果优先选择越晚的开始时间（推迟开机），那么越有可能被后续任务覆盖。可以用反证法证明：假设推迟到最晚时间 $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)$ 排序递归栈空间 + 线段树空间。
leetcode 多少 直接 cv

与LeetCode 周赛 336，多少人直接 CV？相似的内容：

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

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 今天早上是 LeetCode 第 336 场周赛，你参加了吗？这场周赛整体质量比较高，但是最后一题是老题，CV 能过。但是输入数据范围被降低了，这操作也是没谁了。 2587. 统计范围内的

leetcode 多少 直接 cv
243
LeetCode 周赛 332，在套路里摸爬滚打~

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，今天是 3T 选手小彭。 上周是 LeetCode 第 332 场周赛，你参加了吗？算法解题思维需要长时间锻炼，加入我们一起刷题吧~ 小彭的 Android 交流群 02 群已经建立啦，公众号回复 “

leetcode 套路 摸爬滚打
111
LeetCode 周赛 333，你管这叫 Medium 难度？

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 上周是 LeetCode 第 333 场周赛，你参加了吗？这场周赛质量很高，但难度标得不对，我真的会谢。算法解题思维需要长时间锻炼，加入我们一起刷题吧~ 小彭的 Android 交流群 0

leetcode medium 难度
177
LeetCode 周赛 334，在算法的世界里反复横跳

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 今天是 LeetCode 第 334 场周赛，你参加了吗？这场周赛考察范围比较基础，整体难度比较平均，第一题难度偏高，第四题需要我们在算法里实现 “反复横跳”，非常有意思。 小彭的 And

leetcode 算法 世界 反复
221
LeetCode 周赛 335，纯纯手速场！

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 昨晚是 LeetCode 第 335 场周赛，你参加了吗？这场周赛整体难度不高，有两道模板题，第三题和第四题应该调换一下位置。 小彭的 Android 交流群 02 群来了，公众号回复 “

leetcode 纯纯
203
LeetCode 周赛 338，贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 上周末是 LeetCode 第 338 场周赛，你参加了吗？这场周赛覆盖的知识点很多，第四题称得上是近期几场周赛的天花板。 小彭的技术交流群 02 群来了，公众号回复 “加群” 加入我们~

leetcode 贪心 欧氏 线性
157
LeetCode 周赛 340，质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 上周跟大家讲到小彭文章风格的问题，和一些朋友聊过以后，至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小，但却有很多像我一样的初学者，他们有兴趣参加但容易被题目难度和大神选

leetcode 质数 前缀 极大
188
LeetCode 周赛 341 场，模拟 / 树上差分 / Tarjan 离线 LCA / DFS

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 上周末有单双周赛，双周赛我们讲过了，单周赛那天早上有事没参加，后面做了虚拟竞赛，然后整个人就不好了。前 3 题非常简单，但第 4 题有点东西啊，差点就放弃了。最后，被折磨了一个下午和一个大

leetcode 模拟 树上 差分
148
LeetCode 周赛 342（2023/04/23）容斥原理、计数排序、滑动窗口、子数组 GCB

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 前天刚举办 2023 年力扣杯个人 SOLO 赛，昨天周赛就出了一场 Easy - Easy - Medium - Medium 的水场，不得不说 LeetCode 是懂礼数的 😁。 接

leetcode 原理 计数 排序
186
LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 今天是五一假期的第二天，打周赛的人数比前一天的双周赛多了，难道大家都只玩一天吗？这场周赛是 LeetCode 第 343 场单周赛，如果不考虑第一题摆烂的翻译，整体题目质量还是很不错哒。

leetcode 结合 一个 排列
253
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.