[第335场周赛]质因数分解，多重背包

喜提AK以及最佳排名：

6307. 递枕头

提示

简单

3

相关企业

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

最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

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

给你两个正整数 ​​n​​ 和 ​​time​​ ，返回 ​​time​​ 秒后拿着枕头的人的编号。

示例 1：

输入：n = 4, time = 5
输出：2
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
5 秒后，枕头传递到第 2 个人手中。

示例 2：

输入：n = 3, time = 2
输出：3
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 。
2 秒后，枕头传递到第 3 个人手中。

提示：

• ​​2 <= n <= 1000​​
• ​​1 <= time <= 1000​​

Solution

直接公式

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        time %= 2 * (n - 1)
        return time + 1 if time <= (n - 1) else 2 * (n - 1) + 1 - time

学习python库函数：d, m = divmod(n)，可同时得到商和余数。

6308. 二叉树中的第 K 大层和

提示

中等

1

相关企业

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

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

返回树中第 ​​k​​ 大的层和（不一定不同）。如果树少于 ​​k​​ 层，则返回 ​​-1​​ 。

注意，如果两个节点与根节点的距离相同，则认为它们在同一层。

示例 1：

输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：树中每一层的层和分别是：
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。

示例 2：

输入：root = [1,2,null,3], k = 1
输出：3
解释：最大的层和是 3 。

提示：

• 树中的节点数为 ​​n​​
• ​​2 <= n <= 105​​
• ​​1 <= Node.val <= 106​​
• ​​1 <= k <= n​​

Solution

我是用dfs做的

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        h = []
        val = [0] * 10**5
        def dfs(layer, node):
            val[layer] += node.val
            if node.left != None: dfs(layer + 1, node.left)
            if node.right != None: dfs(layer + 1, node.right)
        dfs(0, root)
        cnt = 0
        for v in val:
            if v > 0:
                heappush(h, -v)
                cnt += 1
        if cnt < k:
            return -1
        res = 0
        while k > 0:
            res = heappop(h)
            k -= 1
        return -res
            

不过可以用bfs做，常规bfs做法就是滚动数组。

渐渐对bfs和dfs不再那么恐惧了。

6309. 分割数组使乘积互质

提示

中等

4

相关企业

给你一个长度为 ​​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​​ 的最大公约数。

示例 1：

输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。

示例 2：

输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。

提示：

• ​​n == nums.length​​
• ​​1 <= n <= 104​​
• ​​1 <= nums[i] <= 106​​

Solution

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        n = len(nums)
        # print(n)
        g = [False] * n
        border = -1
        for i in range(n - 1):
            if i == border:
                return border
            if g[i]:
                continue
            g[i] = True
            for j in range(border + 1, n):
                if gcd(nums[i], nums[j]) != 1:
                    g[j] = True
                    border = max(border, j)
        return -1

这题比较奇怪，反正我糊出来了。就是两重循环不断gcd，然后gcd不为1就把这些数标记为True，并且从下一个循环开始内层循环从上一次循环的最右端点开始，因为答案一定不比最右端点小。然后一旦外层循环达到了最右端点，则可以返回结果了。

这么做的最坏时间复杂度应该是O(n^2logC)的，但是感觉应该要比这个复杂度低。最后跑了5000ms的样子吧，也不是特别慢。

另外上面的continue应该是有问题的，数据不够强。

不过学习一下灵神的做法。

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        left = {}  # left[p] 表示质数 p 首次出现的下标
        right = [-1] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值

        def f(p: int, i: int) -> None:
            if p in left:
                right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值
            else:
                left[p] = i  # 第一次遇到质数 p

        for i, x in enumerate(nums):
            d = 2
            while d * d <= x:  # 分解质因数
                if x % d == 0:
                    f(d, i)
                    x //= d
                    while x % d == 0:
                        x //= d
                d += 1
            if x > 1: f(x, i)

        max_r = 0
        for l, r in enumerate(right):
            if l > max_r:  # 最远可以遇到 max_r
                return max_r  # 也可以写 l-1
            max_r = max(max_r, r)
        return -1

作者：灵茶山艾府
链接：https://leetcode.cn/problems/split-the-array-to-make-coprime-products/solutions/2148324/ben-zhi-shi-tiao-yue-you-xi-by-endlessch-8chd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

基本上就是分解质因数，并获取每个数质因数存在的最右端点就可以了。时间复杂度O(Nlog(sqrt(C)))，因为质因数只要分解到sqrt(C)就好了。

6310. 获得分数的方法数

提示

困难

1

相关企业

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

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

注意，同类型题目无法区分。

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

示例 1：

输入：target = 6, types = [[6,1],[3,2],[2,3]]
输出：7
解释：要获得 6 分，你可以选择以下七种方法之一：
- 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6
- 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6
- 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6
- 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6
- 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6
- 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6
- 解决 2 道第 2 种类型的题目：3 + 3 = 6

示例 2：

输入：target = 5, types = [[50,1],[50,2],[50,5]]
输出：4
解释：要获得 5 分，你可以选择以下四种方法之一：
- 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5
- 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5
- 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5
- 解决 1 道第 2 种类型的题目：5

示例 3：

输入：target = 18, types = [[6,1],[3,2],[2,3]]
输出：1
解释：只有回答所有题目才能获得 18 分。

提示：

• ​​1 <= target <= 1000​​
• ​​n == types.length​​
• ​​1 <= n <= 50​​
• ​​types[i].length == 2​​
• ​​1 <= counti, marksi <= 50​​

Solution

dfs

class Solution:
    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:
        n = len(types)
        @cache
        def dfs(idx, pts):
            res = 0
            for i in range(types[idx][0]+1):
                tmp = types[idx][1] * i
                if pts + tmp < target and idx < n - 1:
                    res += dfs(idx + 1, pts + tmp)
                    res %= 10 ** 9 + 7
                elif pts + tmp == target:
                    # print(pts + tmp)
                    res += 1
                    res %= 10 ** 9 + 7
            return res
        return dfs(0, 0)

注意写@cache之后最好不要直接对外部变量进行修改，否则会出现未定义的行为。就是这句话让我排名骤降200名。

另外可以用背包来做，对每一个分数进行背包。比赛的时候没有想清楚背包的对象。

写matlab去。