本文已收录到 AndroidFamily，技术和职场问题，请关注大众号 [彭旭锐] 发问。

大家好，我是小彭。

上周末是 LeetCode 第 338 场周赛，你参与了吗？这场周赛掩盖的常识点很多，第四题称得上是近期几场周赛的天花板。

目录

2600.K 件物品的最大和（Easy）

  • 贪心、模仿 O(1)O(1)

2601. 质数减法运算（Medium）

  • 题解一：暴力枚举 + 二分查找 O(UU+nlgU)O(U\sqrt{U} + nlgU)
  • 题解二：Eratosthenes 埃氏筛 + 二分查找 O(UlgU+nlgU)O(UlgU + nlgU)
  • 题解三：Euler 欧氏线性筛 + 二分查找 O(U+nlgU)O(U + nlgU)

2602. 使数组元素全部持平的最少操作次数

  • 前缀和 + 二分查找 O(nlgn+qlgn)O(nlgn + qlgn)

2603. 搜集树中金币（Hard）

  • 拓扑排序 + 模仿 O(n)O(n)

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

2600.K 件物品的最大和（Easy）

标题地址

leetcode.cn/problems/k-…

标题描绘

袋子中装有一些物品，每个物品上都符号着数字 1、0 或 -1。

给你四个非负整数 numOnes、numZeros、numNegOnes 和 k。

袋子开端包括：

  • numOnes 件符号为 1 的物品。
  • numZeroes 件符号为 0 的物品。
  • numNegOnes 件符号为 1 的物品。

现方案从这些物品中刚好选出 k 件物品。回来一切可行方案中，物品上所符号数字之和的最大值。

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

题解（贪心 + 模仿）

简单模仿题，优先挑选 1，其次 0，最终 -1。

class Solution {
    fun kItemsWithMaximumSum(numOnes: Int, numZeros: Int, numNegOnes: Int, k: Int): Int {
        var x = k
        // 1
        val oneCnt = Math.min(numOnes, x)
        x -= oneCnt
        if (x == 0) return oneCnt
        // 0
        x -= Math.min(numZeros, x)
        if (x == 0) return oneCnt
        // -1
        return oneCnt - x
    }
}

复杂度剖析：

  • 时刻复杂度：O(1)O(1)
  • 空间复杂度：O(1)O(1)

2601. 质数减法运算（Medium）

标题地址

leetcode.cn/problems/pr…

标题描绘

给你一个下标从 0 开端的整数数组 nums，数组长度为 n。

你能够履行无限次下述运算：

  • 挑选一个之前未选过的下标 i，并挑选一个 严厉小于nums[i] 的质数 p，从 nums[i] 中减去 p。

假如你能通过上述运算使得 nums 成为严厉递加数组，则回来 true；否则回来 false。

严厉递加数组 中的每个元素都严厉大于其前面的元素。

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

准备常识

这道题假如熟悉质数筛便是简单二分查找问题。

1、质数界说：

  • 质数 / 素数：只能被 1 和本身整除的数，例如 3，5，7；
  • 合数：除了能被 1 和本身整在外，还能被其他数整除的数。也能够了解为由多个不为 1 的质数相乘组成的数，例如 4 = 2 _ 2，6 = 2 _ 3。
  • 1 既不是质数也不是合数。

2、判别 x 是否为质数：

能够枚举 [2,n-1] 的一切数，查看是否是 x 的因数，时刻复杂度是 O(n)。事实上并不需求枚举到 n-1：以 n = 17 为例，假定从 2 枚举到 4 都没有发现因子，咱们发现 5 也没必要查看。

能够用反证法证明：假如 17 能够被 5 整除，那么必定存在 17 能够被 17/5 的另一个数整除。而由于 17/5 < 5 与前面验证过 [2,4] 不存在因子的前提对立。因而 5 不可能是因子。

由此得出，假如存在整除联系 n/x = y，咱们只需求查看 x 和 y 之间的较小值。一切的较小值最大不会超越 n 的平方根。所以咱们能够缩小查看规模，只查看 [1,O(x)][1, O(\sqrt{x})]，时刻复杂度是 O(x)O(\sqrt{x})

3、核算一切小于 n 的质数，有三种算法：

  • 暴力枚举： 枚举每个数，判别它是不是质数，全体时刻复杂度是 O(nn)O(n\sqrt{n})
  • Eratosthenes 埃氏筛： 假如 x 不是质数，则从 x*x 开端将成倍的数字符号为非质数，全体时刻复杂度是 O(UlgU)；
  • Euler 欧氏线性筛： 符号 x 与 “小于等于 x 的最小质因子的质数” 的乘积为非质数，确保每个合数只被符号最小的质因子符号。

题解一（暴力枚举质数 + 二分查找）

为了取得严厉递加数组，明显数组的末位元素的束缚是最弱的，甚至是没有束缚的。所以咱们挑选从后往前处理，最终一个数不需求处理。

明显假如靠后的元素尽可能大，那么靠前的元素越简单满意条件。因而，咱们能够找到贪心思路：从后往前处理，每处理一个数字时，咱们尽可能减去满意标题要求的最小质数，减缓数字变小的速度，给靠前的数字留出空间。

简单发现，“满意标题要求的最小质数” 存在单调性能够用二分查找处理。因而咱们的题解分为 2 部分：

  • 1、预处理标题数据规模内的一切质数，即小于 1000 的质数列表，能够用预置常识中的两种；
  • 2、运用二分查找寻找 “满意标题要求的最小质数”。
class Solution {
    companion object {
        // 1000 以内的质数列表
        private val primes = getPrimes(1000)
        // 暴力求质数
        private fun getPrimes(max: Int): IntArray {
            val primes = LinkedList<Int>()
            for (num in 2..max) {
                if (isPrime(num)) primes.add(num)
            }
            return primes.toIntArray()
        }
        // 质数判别
        private fun isPrime(num: Int): Boolean {
            var x = 2
            while (x * x <= num) {
                if (num % x == 0) return false
                x++
            }
            return true
        }
    }
    fun primeSubOperation(nums: IntArray): Boolean {
        for (index in nums.size - 2 downTo 0) {
            if (nums[index] < nums[index + 1]) continue
            // 二分查找：寻找严厉小于 nums[index] 且减去后形成递加的最小质数
            var left = 0
            var right = primes.size - 1
            while (left < right) {
                val mid = (left + right) ushr 1
                if (primes[mid] >= nums[index] || nums[index] - primes[mid] < nums[index + 1]) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            if (primes[left] >= nums[index] || nums[index] - primes[left] >= nums[index + 1]) return false
            nums[index] -= primes[left]
        }
        return true
    }
}

复杂度剖析：

  • 时刻复杂度：O(U⋅U+nlgU)O(U\sqrt{U} + nlgU) 其间 nn 是 numsnums 数组的长度，UU 是输入数据规模，UU 为常数 10001000；
  • 空间复杂度：O(1)O(1) 疏忽预处理质数空间，仅运用常数等级空间。

题解二（Eratosthenes 埃氏筛 + 二分查找）

核算质数的部分能够用经典埃氏筛。

筛法求质数的思路是：假如 x 是质数，那么 x 的整数倍 2x、3x 必定不是质数。咱们设 isPrime[i] 表明 i 是否为质数，从小开端遍历，假如 i 是质数，则同时将一切倍数符号为合数。事实上，咱们不必从 x 开端符号，而是直接从 x*x 开端符号，由于 x * 2, x * 3 已经在之前被符号过，会重复符号。

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

class Solution {
    companion object {
        // 1000 以内的质数列表
        private val primes = getPrimes(1000)
        // 埃氏筛求质数
        private fun getPrimes(max: Int): IntArray {
            val primes = LinkedList<Int>()
            val isPrime = BooleanArray(max + 1) { true }
            for (num in 2..max) {
                // 查看是否为质数，这儿不需求调用 isPrime() 函数判别是否质数，由于它没被小于它的数符号过，那么必定不是合数
                if (!isPrime[num]) continue
                primes.add(num)
                // 符号
                var x = num * num
                while (x <= max) {
                    isPrime[x] = false
                    x += num
                }
            }
            return primes.toIntArray()
        }
    }
    fun primeSubOperation(nums: IntArray): Boolean {
        val n = nums.size
        if (n <= 1) return true
        for (index in n - 2 downTo 0) {
            if (nums[index] < nums[index + 1]) continue
            // 二分查找
            var left = 0
            var right = primes.size - 1
            while (left < right) {
                val mid = (left + right) ushr 1
                if (primes[mid] >= nums[index] || nums[index] - primes[mid] < nums[index + 1]) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            if (primes[left] >= nums[index] || nums[index] - primes[left] >= nums[index + 1]) return false
            nums[index] -= primes[left]
        }
        return true
    }
}

复杂度剖析：

  • 时刻复杂度：O(U⋅lgU+nlgU)O(UlgU + nlgU) 其间 nn 是 numsnums 数组的长度，UU 是输入数据规模，UU 为常数 10001000；
  • 空间复杂度：O(1)O(1) 疏忽预处理质数空间，仅运用常数等级空间。

题解三（Euler 欧氏线性筛 + 二分查找）

尽管咱们从 x * x 开端符号来减少重复符号，但 Eratosthenes 挑选法还是会重复符号一个合数。举个比如，400 这个数不只会被 2 符号一遍，还会被 5 符号，这就导致了很多的重复核算。

为了避免重复符号，咱们运用欧氏筛，它与埃氏筛不同的是：

  • 符号过程不再仅对质数 prime 符号，而是对每个数 x 符号；
  • 不再符号一切 x* x 的整数倍，而是符号 x 与 “小于等于 x 的最小质因子的质数” 的乘积，确保每个合数只被符号最小的质因子符号。
class Solution {
    companion object {
        // 1000 以内的质数列表
        private val primes = getPrimes(1000)
        // 线性筛求质数
        private fun getPrimes(max: Int): IntArray {
            val primes = LinkedList<Int>()
            val isPrime = BooleanArray(max + 1) { true }
            for (num in 2..max) {
                // 查看是否为质数，这儿不需求调用 isPrime() 函数判别是否质数，由于它没被小于它的数符号过，那么必定不是合数
                if (isPrime[num]) {
                    primes.add(num)
                }
                // 符号
                for (prime in primes) {
                    if (num * prime > max) break
                    isPrime[num * prime] = false
                    if (num % prime == 0) break
                }
            }
            return primes.toIntArray()
        }
    }
    fun primeSubOperation(nums: IntArray): Boolean {
        val n = nums.size
        if (n <= 1) return true
        for (index in n - 2 downTo 0) {
            if (nums[index] < nums[index + 1]) continue
            // 二分查找
            var left = 0
            var right = primes.size - 1
            while (left < right) {
                val mid = (left + right) ushr 1
                if (primes[mid] >= nums[index] || nums[index] - primes[mid] < nums[index + 1]) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            if (primes[left] >= nums[index] || nums[index] - primes[left] >= nums[index + 1]) return false
            nums[index] -= primes[left]
        }
        return true
    }
}

复杂度剖析：

  • 时刻复杂度：O(U+nlgU)O(U + nlgU) 其间 nn 是 numsnums 数组的长度，UU 是输入数据规模，UU 为常数 10001000；
  • 空间复杂度：O(1)O(1) 疏忽预处理质数空间，仅运用常数等级空间。

类似标题：

  • 204. 计数质数
  • 2523. 规模内最接近的两个质数

2602. 使数组元素全部持平的最少操作次数（Medium）

标题地址

leetcode.cn/problems/mi…

标题描绘

给你一个正整数数组 nums。

同时给你一个长度为 m 的整数数组 queries。第 i 个查询中，你需求将 nums 中一切元素变成 queries[i]。你能够履行以下操作 恣意 次：

  • 将数组里一个元素 增大 或者 减小1。

请你回来一个长度为 m 的数组 **answer，其间 **answer[i]是将 nums 中一切元素变成 queries[i] 的 最少 操作次数。

留意，每次查询后，数组变回最开端的值。

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

题解（前缀和 + 二分查找）

一道题很明显有前缀和问题，难点也正是怎么把原问题转换为前缀和问题。 假如用暴力解法，咱们只需求核算每个元素到 queries[i] 的绝对值之和，单词查询操作的时刻复杂度是 O(n)，咱们不考虑。

为了优化时刻复杂度，咱们剖析数据的特征：

以 nums = [3,1,6,8], query = 5 为例，小于 5 的 3 和 1 需求增大才干变为 5，大于 5 的 6 和 8 需求减小才干变为 5。因而咱们测验将数组分为两部分 [3,1, | 6,8]，需求履行加法的次数为 [+2,+4, | -1,-3]。

可是，咱们不需求累加这 n 个差值的绝对值，而是运用前缀和在 O(1) 时刻内快速核算。如图所示，小于 5 的部分能够用 “小于 5 的数字个数 _ 5” – “小于 5 的数字之和” 取得，大于 5 的部分能够用 “大于 5 的数字之和” – “大于 5 的数字个数 _ 5” 核算：

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

而 “小于 5 的数字之和” 与 “大于 5 的数字之和” 是明显的区间求和，能够用前缀和数组在 O(1) 时刻复杂度处理。至此，咱们成功将原问题转换为前缀和问题。

那么，剩余的问题是怎么将数组拆分为两部分？

咱们发现对于单次查询来说，咱们能够运用快速挑选算法在 O(lgn) 时刻内找到。可是标题不只只有一次，所以咱们能够先对整个数组排序，再用二分查找找到枚举的分割点。

最终一个细节，由于数组的输入规模很大，所以前缀和数组要界说为 long 数组类型。

class Solution {
    fun minOperations(nums: IntArray, queries: IntArray): List<Long> {
        val n = nums.size
        // 排序
        nums.sort()
        // 前缀和
        val preSums = LongArray(n + 1)
        for (index in nums.indices) {
            preSums[index + 1] = nums[index] + preSums[index]
        }
        val ret = LinkedList<Long>()
        for (target in queries) {
            // 二分查找寻找大于等于 target 的第一个元素
            var left = 0
            var right = n - 1
            while (left < right) {
                val mid = (left + right) ushr 1
                if (nums[mid] < target) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            val index = if (nums[left] >= target) left - 1 else left
            val leftSum = 1L * (index + 1) * target - preSums[index + 1]
            val rightSum = preSums[n] - preSums[index + 1] - 1L * (n - 1 - index) * target
            ret.add(leftSum + rightSum)
        }
        return ret
    }
}

复杂度剖析：

  • 时刻复杂度：O(nlgn+qlgn)O(nlgn + qlgn) 其间 nn 是 numsnums 数组的长度，qq 是 queriesqueries 数组的长度。总共会履行 qq 次查询操作，每次查询操作的时刻复杂度是 O(lgn)O(lgn)；
  • 空间复杂度：O(n)O(n) 前缀和数组空间。

近期周赛前缀和问题：

  • 周赛 336. 统计美丽子数组数目（Medium）

2603. 搜集树中金币（Hard）

标题地址

leetcode.cn/problems/co…

标题描绘

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges，其间 edges[i] = [ai, bi] 表明树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins，其间 coins[i] 可能为 0 也可能为 1，1 表明节点 i 处有一个金币。

一开端，你需求挑选树中恣意一个节点动身。你能够履行下述操作恣意次：

  • 搜集间隔当时节点间隔为 2 以内的一切金币，或者
  • 移动到树中一个相邻节点。

你需求搜集树中一切的金币，而且回到动身节点，请你回来最少通过的边数。

假如你多次通过一条边，每一次通过都会给答案加一。

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

准备常识

  • 拓扑排序：

给定一个包括 n 个节点的有向图 G，咱们给出它的节点编号的一种摆放，假如满意： 对于图 G 中的恣意一条有向边 (u,v)，u 在摆放中都呈现在 v 的前面。 那么称该摆放是图 G 的「拓扑排序」。

  • 拓扑排序的实现思路：

拓扑排序的常规实现是 Kahn 拓扑排序算法，根据 BFS 搜索和贪心思维：每次从图中删去没有前驱的节点（入度为 0），并修正它指向的节点的入度，直到 BFS 队列为空结束。

题解（拓扑排序 + 模仿）

  • 观察示例 1：从节点 2 动身，搜集节点 0 处的金币，移动到节点 3 ，搜集节点 5 处的金币，然后移动回节点 2。
  • 观察示例 2：从节点 0 动身，搜集节点 4 和 3 处的金币，移动到节点 2 处，搜集节点 7 处的金币，移动回节点 0。

结合标题规矩（搜集间隔当时节点间隔为 2 以内的一切金币）和这 2 个示例剖析： 最优途径必定不需求触达图的边缘，而只需求在图的中心部分来回试探 （如示例 1 的节点 2 和节点 3，示例 2 的节点 0 和节点 2）。

  • 1、拜访无金币的子树没有意义，咱们将整个子树剪枝；
  • 2、叶子节点和间隔叶子节点间隔为 1 的节点都没有必要拜访，咱们将这些点剪枝；

剩余的点便是有必要通过的中心点。再结合标题规矩（你需求搜集树中一切的金币，而且回到动身节点），且标题确保输入数据是合法的树，因而答案正好便是剩余部分边的数目 * 2。

LeetCode 周赛 338（2023/03/26）贪心、埃氏筛、欧氏线性筛、前缀和、二分查找、拓扑排序

class Solution {
    fun collectTheCoins(coins: IntArray, edges: Array<IntArray>): Int {
        val n = coins.size
        // 入度表
        val inDegrees = IntArray(n)
        // 领接表
        val graph = HashMap<Int, MutableList<Int>>()
        for (edge in edges) {
            graph.getOrPut(edge[0]) { LinkedList<Int>() }.add(edge[1])
            graph.getOrPut(edge[1]) { LinkedList<Int>() }.add(edge[0])
            inDegrees[edge[0]]++
            inDegrees[edge[1]]++
        }
        // 剩余的边
        var left_edge = edges.size // n - 1
        // 1、拓扑排序剪枝无金币子树
        val queue = LinkedList<Int>()
        for (node in 0 until n) {
            // 标题是无向图，所以叶子结点的入度也是 1
            if (inDegrees[node] == 1 && coins[node] == 0) {
                queue.offer(node)
            }
        }
        while (!queue.isEmpty()) {
            // 删去叶子结点
            val node = queue.poll()
            left_edge -= 1
            // 修正相邻节点
            for (edge in graph[node]!!) {
                if (--inDegrees[edge] == 1 && coins[edge] == 0) queue.offer(edge)
            }
        }
        // 2、拓扑排序剪枝与叶子结点间隔不大于 2 的节点（裁剪 2 层）
        // 叶子节点
        for (node in 0 until n) {
            if (inDegrees[node] == 1 && coins[node] == 1) {
                queue.offer(node)
            }
        }
        for (node in queue) {
            // 2.1 删去叶子结点
            left_edge -= 1
            // 2.2 删去到叶子结点间隔为 1 的节点
            for (edge in graph[node]!!) {
                if (--inDegrees[edge] == 1) left_edge -= 1
            }
        }
        // println(inDegrees.joinToString())
        // coins=[0,0],edges=[[0,1]] 会减去一切节点导致呈现负数
        return Math.max(left_edge * 2, 0)
    }
}

复杂度剖析：

  • 时刻复杂度：O(n)O(n) 其间 nn 是 coinscoins 数组的长度；
  • 空间复杂度：O(n)O(n)。

类似标题：

  • 207. 课程表
  • 2050. 并行课程 III

有用请支持，你们的支持是我继续分享有价值内容的动力。

本文正在参与「金石方案」

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。