乐趣区

关于android:LeetCode-周赛-335纯纯手速场

jiezi

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

大家好，我是小彭。

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

小彭的 Android 交换群 02 群来了，公众号回复“加群”退出咱们~

2582. 递枕头（Easy）

题目地址

https://leetcode.cn/problems/pass-the-pillow/

题目形容

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(time)$
  • 空间复杂度：$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）

题目地址

https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/

题目形容

给你一棵二叉树的根节点 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(nlgk)$ 其中 $n$ 是节点数。二叉树每个节点最多入队一次，二叉树最大有 $n$ 层，小顶堆保护 $k$ 个数的工夫复杂度为 $O(nlgk)$；
  • 空间复杂度：$O(n)$ 小顶堆空间 $O(k)$，递归栈空间最大 $O(n)$。

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

题目地址

https://leetcode.cn/problems/split-the-array-to-make-coprime-…

题目形容

给你一个长度为 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(n\sqrt{U}+n·m)$ 其中 $n$ 是 $nums$ 数组的长度，U 是数组元素的最大值，$m$ 是 $U$ 范畴内的质数个数 $\frac{U}{logU}$。工夫复杂度分为两局部，质因数分解占用 $O(n\sqrt{U})$，枚举宰割点的每轮循环须要枚举所有质数，占用 $O(n·m)$；
  • 空间复杂度：$O(n·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(n\sqrt{U}+mlgm+m)$ 质因数分解工夫 $O(n\sqrt{U})$，排序工夫 $O(mlgm)$，枚举区间工夫 $O(m)$；
  • 空间复杂度：$O(m + lgm)$ 质因子区间数组占用 $O(m)$，排序递归栈空间 $O(lgm)$。

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

题解二中的排序工夫能够优化。

因为咱们是从返回后合成 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(n\sqrt{U}+m)$ 质因数分解工夫 $O(n\sqrt{U})$，枚举数组工夫 $O(n)$；
  • 空间复杂度：$O(n)$ $end$ 数组空间。

2585. 取得分数的办法数（Hard）

题目地址

https://leetcode.cn/problems/number-of-ways-to-earn-points/

题目形容

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

返回你在考试中恰好失去 target 分的办法数。因为答案可能很大，后果须要对 109 +7 取余。

留神，同类型题目无奈辨别。

  • 比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是雷同的。

题解（背包问题）

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

定义 $dp[i][j]$ 示意以物品 $[i]$ 为止且分数为 $j$ 的计划数，则有：

$dp[i][j] = dp[i – 1][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(target·C)$ 其中 $C$ 是所有 $count_i$ 之和。
  • 空间复杂度：$O(target)$
退出移动版