LeetCode 周赛 335，纯纯手速场！-六虎

大家好，我是小彭。

昨夜是 LeetCode 第 335 场周赛，你参与了吗？这场周赛整体难度不高，有两道模板题，第三题和第四题应该调换一下方位。

2582. 递枕头（Easy）

标题地址

leetcode.cn/problems/pa…

标题描绘

n个人站成一排，按从1到n编号。

开端，排在队首的榜首个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给部队中的下一个人。一旦枕头到达队首或队尾，传递方向就会改动，部队会继续沿相反方向传递枕头。

例如，当枕头到达第n个人时，TA 会将枕头传递给第n - 1个人，然后传递给第n - 2个人，依此类推。

给你两个正整数n和time，回来t

题解一（模仿）

简单模仿题。

class Solution {
    fun passThePillow(n: Int, time: Int): Int {
        var index = 1
        var flag = true
        for (count in 0 until time) {
            if (flag) {
                if (++index == n) flag = !flag
            } else {
                if (--index == 1) flag = !flag
            }
        }
        return index
    }
}

复杂度剖析：

时刻复杂度： $O (t im e)$
空间复杂度： $O (1)$

题解二（数学）

以 n = 4 为例，明显每 n – 1 次传递为一轮，则有 time % (n – 1) 分辩出奇数轮 / 偶数轮。其间偶数轮是正向传递，奇数轮是逆向传递。

偶数轮：2 → 3 → 4，time = 1 时传递到 2 号；
奇数轮：3 → 2 → 1。
…

class Solution {
    fun passThePillow(n: Int, time: Int): Int {
        val mod = n - 1
        return if (time / mod % 2 == 0) {
            (time % mod) + 1
        } else {
            n - (time % mod)
        }
    }
}

复杂度剖析：

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

2583. 二叉树中的第 K 大层和（Medium）

标题地址

leetcode.cn/problems/kt…

标题描绘

给你一棵二叉树的根节点root和一个正整数k。

树中的层和是指同一层上节点值的总和。

回来树中第k大的层和（不必定不同）。假如树少于k层，则回来-1。

留意，假如两个节点与根节点的间隔相同，则以为它们在同一层。

题解（BFS + 堆）

BFS 模板题，使用小顶堆记载最大的 k 个数。

class Solution {
    fun kthLargestLevelSum(root: TreeNode?, k: Int): Long {
        if (null == root) return 0L
        val heap = PriorityQueue<Long>()
        // BFS
        val queue = LinkedList<TreeNode>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            var levelSum = 0L
            for (count in 0 until queue.size) {
                val node = queue.poll()
                levelSum += node.`val`
                if (null != node.left) {
                    queue.offer(node.left)
                }
                if (null != node.right) {
                    queue.offer(node.right)
                }
            }
            if (heap.size < k) {
                heap.offer(levelSum)
            } else if (heap.peek() < levelSum) {
                heap.poll()
                heap.offer(levelSum)
            }
        }
        return if (heap.size >= k) heap.peek() else -1L
    }
}

复杂度剖析：

时刻复杂度： $O (n l g k)$ 其间 $n$ 是节点数。二叉树每个节点最多入队一次，二叉树最大有 $n$ 层，小顶堆保护 $k$ 个数的时刻复杂度为 $O (n l g k)$ ；
空间复杂度： $O (n)$ 小顶堆空间 $O (k)$ ，递归栈空间最大 $O (n)$ 。

2584. 切割数组使乘积互质（Medium）

标题地址

leetcode.cn/problems/sp…

标题描绘

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

假如在下标i处切割数组，其间0 <= i <= n - 2，使前i + 1个元素的乘积和剩余元素的乘积互质，则以为该切割有用。

例如，假如nums = [2, 3, 3]，那么在下标i = 0处的切割有用，由于2和9互质，而在下标i = 1处的切割无效，由于6和3不互质。在下标i = 2处的切割也无效，由于i == n - 1。

回来能够有用切割数组的最小下标i，假如不存在有用切割，则回来-1。

当且仅当gcd(val1, val2) == 1成立时，val1和val2这两个值才是互质的，其间gcd(val1, val2)表明val1和val2的最大公约数。

题解（质因子分化）

这道题是这场周赛中最复杂的标题，应该放在 T4。

由于多个数相乘的成果会溢出（假如标题中存在 0 还会搅扰），所以这道题不能用前后缀分化的思路。 比较容易想到的思路是做质因子分化：明显合法切割数点的左右两边不能有公共质因子，不然子集的乘积必定是非互质的。

举个例子，在数组 [1, 2, 3, 2, 5] 中，将质因子 2 划分到不同子集的计划是过错的：

[1 | 2, 3, 2, 5]：过错切割
[1 , 2 | 3, 2, 5]：正确切割
[1 , 2, 3 | 2, 5]：正确切割
[1 , 2, 3, 2 | 5]：过错切割

脑海中有闪现过状况压缩，但标题输入数据较大无法完成，只能有散列表记载质因子信息。因而咱们的算法是：先对 nums 数组中的每个元素做质因数分化，然后枚举一切切割点，统计左右子会集质因子的呈现次数。假如呈现同一个质因子再左右子会集的呈现次数一起大于 1，阐明切割点不成立。

class Solution {
    fun findValidSplit(nums: IntArray): Int {
        val n = nums.size
        // 质因子计数
        val leftCount = HashMap<Int, Int>()
        val rightCount = HashMap<Int, Int>()
        // 质因子分化
        val primeMap = HashMap<Int, HashSet<Int>>()
        for (num in nums) {
            // 对 num 做质因数分化
            primeMap[num] = HashSet<Int>()
            var x = num
            var prime = 2
            while (prime * prime <= x) {
                if (x % prime == 0) {
                    // 发现质因子
                    primeMap[num]!!.add(prime)
                    rightCount[prime] = rightCount.getOrDefault(prime, 0) + 1
                    // 消除一切 prime 因子
                    while (x % prime == 0) x /= prime
                }
                prime++
            }
            if(x > 1) {
                // 剩余的质因子
                primeMap[num]!!.add(x)
                rightCount[x] = rightCount.getOrDefault(x, 0) + 1 
            }
        }
        // 枚举切割点
        outer@ for (index in 0..n - 2) {
            for (prime in primeMap[nums[index]]!!) {
                leftCount[prime] = leftCount.getOrDefault(prime, 0) + 1
                rightCount[prime] = rightCount[prime]!! - 1
            }
            for ((prime, count) in leftCount) {
                if (rightCount[prime]!! != 0) continue@outer
            }
            return index
        }
        return -1
    }
}

复杂度剖析：

时刻复杂度： $O(nU+n⋅m)O(n\sqrt{U}+nm)$ 其间 $n$ 是 $n u m s$ 数组的长度，U 是数组元素的最大值， $m$ 是 $U$ 范围内的质数个数 $UlogU\frac{U}{logU}$ 。时刻复杂度分为两部分，质因数分化占用 $O(nU)O(n\sqrt{U})$ ，枚举切割点的每轮循环需要枚举一切质数，占用 $O (n \cdot m)$ ；
空间复杂度： $O (n \cdot m + m)$ 质因子分化映射表和计数表。

题解二（质因数分化 + 兼并区间）

思路来历：灵茶山艾符的题解

统计每种质因子在数组中呈现的开端方位 left 和停止方位 right，假如切割点位于 [left, right) 区间，那么左右两子集必定会存在公共质因子。

因而咱们的算法是：将质数的散布看成一个接连区间，依照区间开端方位对一切区间排序。遍历区间并保护最大区间停止方位 preEnd，假如当时区间与 preEnd 不接连，则阐明以当时方位为切割点的计划不会拆分区间，也就找到目标答案。

假如依照这个思路理解，这道题本质上和 55. 跳跃游戏类似。

class Solution {
    fun findValidSplit(nums: IntArray): Int {
        // 质因子区间 <首次呈现方位，末次呈现方位>
        val primeMap = HashMap<Int, IntArray>()
        // 质因数分化
        for ((index, num) in nums.withIndex()) {
            // 对 num 做质因数分化
            var x = num
            var prime = 2
            while (prime * prime <= x) {
                if (x % prime == 0) {
                    // 发现质因子
                    primeMap.getOrPut(prime) { intArrayOf(index, index) }[1] = index
                    // 消除一切 prime 因子
                    while (x % prime == 0) x /= prime
                }
                prime++
            }
            if (x > 1) {
                // 剩余的质因子
                primeMap.getOrPut(x) { intArrayOf(index, index) }[1] = index
            }
        }
        // 区间排序
        val areaList = primeMap.values.toMutableList()
        Collections.sort(areaList) { e1, e2 ->
            e1[0] - e2[0]
        }
        // 枚举区间
        var preEnd = 0
        for (area in areaList) {
            if (area[0] > preEnd) return area[0] - 1
            preEnd = Math.max(preEnd, area[1])
        }
        return -1
    }
}

复杂度剖析：

时刻复杂度： $O(nU+mlgm+m)O(n\sqrt{U}+mlgm+m)$ 质因数分化时刻 $O(nU)O(n\sqrt{U})$ ，排序时刻 $O (m l g m)$ ，枚举区间时刻 $O (m)$ ；
空间复杂度： $O (m + l g m)$ 质因子区间数组占用 $O (m)$ ，排序递归栈空间 $O (l g m)$ 。

题解三（兼并区间 + 排序优化）

题解二中的排序时刻能够优化。

由于咱们是从前往后分化 nums 数组，每分化一个质因子 prime 时，它必定能够更新该质数区间的末次呈现方位。所以咱们不必等到最终再做一次区间排序，直接在做质因数分化时保护 preEnd。在题解二中，咱们是从区间的维度保护 preEnd，现在咱们直接从 nums 数组的维度保护 preEnd。

class Solution {
    fun findValidSplit(nums: IntArray): Int {
        val n = nums.size
        // start[p] 表明质数 p 首次呈现停止
        val start = HashMap<Int, Int>()
        // end[i] 表明以 i 为左端点的区间的最大右端点
        val end = IntArray(n)
        // 质因数分化
        for ((index, num) in nums.withIndex()) {
            // 对 num 做质因数分化
            var x = num
            var prime = 2
            while (prime * prime <= x) {
                if (x % prime == 0) {
                    // 发现质因子
                    if (!start.containsKey(prime)) {
                        start[prime] = index
                    } else {
                        end[start[prime]!!] = index
                    }
                    // 消除一切 prime 因子
                    while (x % prime == 0) x /= prime
                }
                prime++
            }
            if (x > 1) {
                // 剩余的质因子
                if (!start.containsKey(x)) {
                    start[x] = index
                } else {
                    end[start[x]!!] = index
                }
            }
        }
        var preEnd = 0
        for (index in 0 until n) {
            if (index > preEnd) return index - 1
            preEnd = Math.max(preEnd, end[index])
        }
        return -1
    }
}

复杂度剖析：

时刻复杂度： $O(nU+m)O(n\sqrt{U}+m)$ 质因数分化时刻 $O(nU)O(n\sqrt{U})$ ，枚举数组时刻 $O (n)$ ；
空间复杂度： $O (n)$ $e n d$ 数组空间。

2585. 获得分数的方法数（Hard）

标题地址

leetcode.cn/problems/nu…

标题描绘

考试中有n种类型的标题。给你一个整数target和一个下标从0开端的二维整数数组types，其间types[i] = [counti, marksi] 表明第i种类型的标题有counti道，每道标题对应marksi分。

回来你在考试中恰好得到target分的方法数。由于答案可能很大，成果需要对109 +7取余。

留意，同类型标题无法区别。

比如说，假如有3道同类型标题，那么回答第1和第2道标题与回答第1和第3道标题或者第2和第3道标题是相同的。

题解（背包问题）

这是分组背包模板题，OIWiki-背包 DP。

界说 $d p [i] [j]$ 表明以物品 $[i]$ 停止且分数为 $j$ 的计划数，则有：

$\sum_{k=0}^{k=j/count_i}dp[i – 1][j – k*marks_{si}]$

class Solution {
    fun waysToReachTarget(target: Int, types: Array<IntArray>): Int {
        val MOD = 1000000007
        // 背包问题
        val n = types.size
        // dp[i][j] 表明以 [i] 停止且分数为 j 的计划数
        val dp = Array(n + 1) { IntArray(target + 1) }.apply {
            // 不挑选且分数为 0 的计划数为 1
            this[0][0] = 1
        }
        // 枚举物品
        for (i in 1..n) {
            val count = types[i - 1][0]
            val mark = types[i - 1][1]
            for (j in target downTo 0) {
                dp[i][j] += dp[i - 1][j]
                for (k in 1..Math.min(count, j / mark)) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k * mark]) % MOD
                }
            }
        }
        return dp[n][target]
    }
}

彻底背包能够撤销物品维度优化空间：

class Solution {
    fun waysToReachTarget(target: Int, types: Array<IntArray>): Int {
        val MOD = 1000000007
        // 背包问题
        val n = types.size
        // dp[i][j] 表明以 [i] 停止且分数为 j 的计划数
        val dp = IntArray(target + 1).apply {
            // 不挑选且分数为 0 的计划数为 1
            this[0] = 1
        }
        // 枚举物品
        for (i in 1..n) {
            val count = types[i - 1][0]
            val mark = types[i - 1][1]
            for (j in target downTo 0) {
                for (k in 1..Math.min(count, j / mark)) {
                    dp[j] = (dp[j] + dp[j - k * mark]) % MOD
                }
            }
        }
        return dp[target]
    }
}

复杂度剖析：

时刻复杂度： $O (t a r g e t \cdot C)$ 其间 $C$ 是一切 $count_i$ 之和。
空间复杂度： $O (t a r g e t)$

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

LeetCode 周赛 335，纯纯手速场！

2582. 递枕头（Easy）

标题地址

标题描绘

题解一（模仿）

题解二（数学）

2583. 二叉树中的第 K 大层和（Medium）

标题地址

标题描绘

题解（BFS + 堆）

2584. 切割数组使乘积互质（Medium）

标题地址

标题描绘

题解（质因子分化）

题解二（质因数分化 + 兼并区间）

题解三（兼并区间 + 排序优化）

2585. 获得分数的方法数（Hard）

标题地址

标题描绘

题解（背包问题）

相关文章

透彻！android binder机制原来是这样的

2022，拔剑四顾心茫然

[官文翻译]Dart轻量超快键值数据库Hive – 基础

字节跳动智创音视频团队拿下 NTIRE2022 ESR 挑战赛主赛道冠军

作者信息