力扣杯2020春季全国编程大赛_个人赛

目录

• 拿硬币
• 传递信息
• 剧情触发事件
• 最小跳跃次数
• 二叉树任务调度

拿硬币

在数组coins中有n个数，每个数表示一堆硬币包含的硬币数。每次任选一堆，那种其中的一枚或两枚，求拿完所有硬币的最少次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/na-ying-bi/

示例

输入：[4, 2, 1]
输出：4
解释：第一堆至少要拿2次，第二堆至少拿1次，第三堆至少拿1次

我的思路

非常简单。偶数硬币堆直接除以2即为拿完最少次数；奇数硬币堆整除2后还要再加1，例如3个硬币，至少要拿2次，3整除2得1，1再加1得2

我的代码

1
2
3
4
5
6
7
8
9

class Solution:
    def minCount(self, coins: List[int]) -> int:
        res = 0
        for coin in coins:
            if coin % 2 == 0:
                res += coin // 2
            else:
                res += coin // 2 + 1
        return res   

别人的思路

榜首对奇数堆是先加1再整除2，甚至可一行代码解决

别人的代码

1
2
3

class Solution:
    def minCount(self, coins: List[int]) -> int:
        return sum((x + 1) // 2 for x in coins)

传递信息

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

• 有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
• 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
• 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

给定总玩家数 n，以及按 [玩家编号, 对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chuan-di-xin-xi

示例

输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
输出：3
解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

我的思路

需要用DFS查询。先用哈希表tmp存储每个编号的人能够访问的编号。然后设置一个DFS递归函数，函数传递的是当前人所能访问的编号列表ds以及当前已传递的轮次cur。当传递轮次cur达到k时，判断此时编号n-1是否在可访问列表ds，若存在则保存方案数的全局self.res加1，否则self.res不变，之后退出递归。对每个访问列表ds，用for循环遍历其可访问的编号，并对这些编号进行DFS递归直到退出递归。

我的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def numWays(self, n, relation, k):
        tmp = {}
        for key, val in relation:
            try:
                tmp[key] += [val]
            except:
                tmp[key] = [val]

        self.res = 0

        def dfs(ds, cur):
            if cur == k:
                if n - 1 in ds:
                    self.res += 1
                return
            for d in ds:
                try:
                    dfs(tmp[d], cur + 1)
                except:
                    continue
        
        dfs(tmp[0], 1)
        return self.res

剧情触发事件

在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（C），资源储备（R）以及人口数量（H）。在游戏开始时（第 0 天），三种属性的值均为 0。

随着游戏进程的进行，每一天玩家的三种属性都会对应增加，我们用一个二维数组 increase 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组，例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2。

所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件 c[i], r[i], h[i]，如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，则剧情会被触发。

根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-qing-hong-fa-shi-jian

示例

输入：
increase = [[2,8,4],[2,5,0],[10,9,8]]
requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]
输出: [2,-1,3,-1]
解释：
初始时，C = 0，R = 0，H = 0
第 1 天，C = 2，R = 8，H = 4
第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0
第 3 天，C = 14，R = 22，H = 12，此时触发剧情 2
剧情 1 和 3 无法触发。

我的思路

首先用 c, r, h 三个列表存储C，R，H三个变量在游戏过程中每天的值，这个通过遍历 increase 可得。

接着遍历 requirements 来获得答案。首先判断遍历过程中每个 req 是否超过 c, r, h 中的最大值，超过的话则此 req 的要求一定无法满足，用-1表示；若可满足要求，由于 c, r, h 都是升序数列，则用 二分查找 在 c, r, h 中找到第一个大于等于 req 的要求的数的位置索引，这三个指标索引的最大值即为可触发该情节的天数。

关于实现二分查找 BiSearch()函数 的一些细节，由于 c, r, h 中可能存在相同数，而满足要求的数如果在数列中有相同数时，则查找的位置索引应该是这些相同数中排在最前面的那个数的。这个问题卡了我很久，最后用了一个while循环来找排在最前面的那个数的索引。

我的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution:
    def getTriggerTime(self, increase, requirements):
        res = list()
        c, r, h = [0], [0], [0]
        for nums in increase:
            c.append(c[-1] + nums[0])
            r.append(r[-1] + nums[1])
            h.append(h[-1] + nums[2])
            
        def biSearch(target, arr):
            """
            在升序序列arr中找到第一个大于等于target的数的下标
            """
            left, right = 0, len(arr) - 1
            ind = -1
            while left <= right:
                mid = left + (right - left) // 2
                if arr[mid] == target:
                    while mid - 1 >= 0 and arr[mid - 1] == arr[mid]:
                        mid -= 1
                    return mid
                if arr[mid] > target:
                    ind = mid
                    right = mid - 1
                else:
                    left = mid + 1
            return ind
        
        for req in requirements:
            if req[0] > c[-1] or req[1] > r[-1] or req[2] > h[-1]:
                res.append(-1)
                continue
            req_c = biSearch(req[0], c)
            req_r = biSearch(req[1], r)
            req_h = biSearch(req[2], h)
            res.append(max(req_c, req_r, req_h))
        
        return res

别人的思路

使用了模组 bisect.bisect_left() 来实现我上面所提到的二分查找功能。 bisect.bisect_left(a, x, lo=0, hi=len(a)) 的实际说明为：查找在有序列表a中插入x的index。lo和hi用于指定查找区间，默认查找整个列表。如果x已存在，则返回其左边一个位置的索引。

别人的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def getTriggerTime(self, increase, requirements):
        n = len(increase)
        C, R, H = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
        for i in range(n):
            C[i+1] = C[i] + increase[i][0]
            R[i+1] = R[i] + increase[i][1]
            H[i+1] = H[i] + increase[i][2]
        a = []
        for c, r, h in requirements:
            i1 = bisect.bisect_left(C, c)
            i2 = bisect.bisect_left(R, r)
            i3 = bisect.bisect_left(H, h)
            if i1 <= n and i2 <= n and i3 <= n:
                a.append(max(i1, i2, i3))
            else:
                a.append(-1)
        return a

最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-tiao-yue-ci-shu

示例

输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

别人的思路

动态规划。将 dp[i] 设为从第i个弹簧弹出机器的最小次数。 从后往前进行记忆化搜索。

• 1、当i + jump[i] >= len(jump)时，表示可以从第i个弹簧直接弹出机器，故设dp[i] = 1
• 2、当1不成立时，首先计算从第i个弹簧向右跳时，弹出机器所需最小次数，dp[i] = dp[i + jump[i]] + 1
• 3、基于当前的dp[i]更新（i+1，i+jump[i]）范围内的dp[j]，其中 i+1 <= j <= i + jump[i]。实现这里的功能是代码中的while循环。由于右边界i + jump[i] 可能会超过jump的索引范围，故while循环加了两个约束条件，即j < len(jump) 和 j < i + jump[i]。还有一个关键的约束条件 dp[j] > dp[i]，如果不加入此条件将会超时，由于dp[i]在dp[j]的左边，即可从第j个弹簧往左跳到第i个弹簧，故当dp[j] > dp[i]时，可从第j个弹簧往左跳到第i个弹簧以此获得更少的次数dp[j] = dp[i] + 1; 而当dp[j] > dp[i] 不成立时，说明此前的while循环中有更优解，故从此处剪枝。

别人的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minJump(self, jump):
        dp = [0] * len(jump)
        for i in range(len(jump) - 1, -1, -1):
            if i + jump[i] >= len(jump):
                dp[i] = 1
            else:
                dp[i] = dp[i + jump[i]] + 1
            j = i + 1
            while j < len(jump) and j < i + jump[i] and dp[j] > dp[i]:
                dp[j] = min(dp[j], dp[i] + 1) # 可优化为dp[j] = dp[i] + 1
                j += 1
        return dp[0]

二叉树任务调度

任务调度优化是计算机性能优化的关键任务之一。在任务众多时，不同的调度策略可能会得到不同的总体执行时间，因此寻求一个最优的调度方案是非常有必要的。

通常任务之间是存在依赖关系的，即对于某个任务，你需要先完成他的前导任务（如果非空），才能开始执行该任务。我们保证任务的依赖关系是一棵二叉树，其中 root 为根任务，root.left 和 root.right 为他的两个前导任务（可能为空），root.val 为其自身的执行时间。

在一个 CPU 核执行某个任务时，我们可以在任何时刻暂停当前任务的执行，并保留当前执行进度。在下次继续执行该任务时，会从之前停留的进度开始继续执行。暂停的时间可以不是整数。

现在，系统有两个 CPU 核，即我们可以同时执行两个任务，但是同一个任务不能同时在两个核上执行。给定这颗任务树，请求出所有任务执行完毕的最小时间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du

示例

输入：root = [47, 74, 31]
输出：121
解释：根节点的左右节点可以并行执行31分钟，剩下的43+47分钟只能串行执行，因此总体执行时间是121分钟。

输入：root = [1, 3, 2, null, null, 4, 4] 输出：7.5 解释：0.5s并行处理根节点的左节点（3-0.5=2.5）以及处理一个孙子节点（4-0.5=3.5），再0.5s处理根节点的左节点（2.5-0.5=2）以及处理另一个孙子节点（4-0.5=3.5），接下来3.5s并行处理两个孙子节点，接下来2s并行处理左右子节点，最后1s处理根节点。共0.5+0.5+3.5+2+1=7.5s。

别人的思路

DFS递归。DFS自底向上，每次返回两个数，分别代表执行完当前节点的最小耗时 minTime 以及串行处理完当前节点前置子任务的总时间preTime。双核并行处理前置子任务的最优解（自小耗时）为 preTime / 2，最优解只是理想情况，故需要与完成左右前置子任务的最小耗时比较（非理想情况下，这两者中至少有一者会比并行最优解大），取三者中最大值加上当前节点所需时间可得 minTime。该方法可以绕开 考虑双核如何分配并行 这一个困难问题。

别人的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minimalExecTime(self, root: TreeNode) -> float:
        
        def dfs(node):
            """
            返回:res
            res[0]执行完当前节点的最小耗时
            res[1]串行处理完node子任务的时间
            """
            if not node:
                return [0, 0]
            leftTime = dfs(node.left)
            rightTime = dfs(node.right)
            preTime = leftTime[1] + rightTime[1]
            minTime = max(leftTime[0], rightTime[0], preTime / 2) + node.val
            return [minTime, preTime + node.val]

        return dfs(root)[0]

总结

本次竞赛AC了前三题，后两题基本就看了下题目，没思路就没做了。排名（1193/4093)，在前30%。
做完4月19日的周赛后，复盘了五个小时才复盘完，效率太低了。
DFS一直很难，所幸这次解决了一道DFS的题（LCP 07. 传递信息），算是有所进步。
二分查找边界定义依然不够熟练，（LCP 08. 剧情触发事件）罚时了很多。在没有测试用例的提示下，找bug确实也很不容易。
LCP 09. 最小跳跃次数 是 跳跃游戏 类型的题型，DP依然不熟练。
LCP 10. 二叉树任务调度 对当前水平来说还是很难的DFS，题解思路也没完全看懂。