2020 Leetcode春季个人赛 2112/4093 | Peanuts' Blog

Keep Learning

2020 Leetcode春季个人赛 2112/4093

Posted on Edited on In
Symbols count in article: 2.4k Reading time ≈ 2 mins.

成绩

做了两道题，中间跑出去研究Python语法了，回来之后又写了第三题，本打算交的时间到了，不过反正写的暴力也会超时，还需要加二分

解题

拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

输入：[4,2,1]
输出：4
解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。
1 <= n <= 4
1 <= coins[i] <= 10

签到打卡题，但是竞赛对数据类型的要求挺高的。

1
2
3
4
5
6
7
8
9
class Solution:
    def minCount(self, coins: List[int]) -> int:
        res=0
        for i in coins:
            if not i&1:
                res+= i//2
            else:
                res += i//2+1
        return res

传递信息

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

有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0

每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。

每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

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

示例：
输入：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解题即可，也可以使用BFS，然后在写嵌套函数的时候发现内部的函数不能改变外部函数的值，因为这个纠结了好久，第三题也没做完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        des = [[] for _ in range(n)]
        res = 0
        for r in relation:
            des[r[0]].append(r[1])

        def dfs(i: int,nums: List[int]) -> int:
            temp = 0
            if i>k:
                return 0
            if i==k and n-1 in nums:
                return 1
            for d in nums:
                temp+=dfs(i+1,des[d])
            return temp

        res = dfs(1,des[0])
        return 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 。

示例：

输入： 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 无法触发。

简单模拟即可，因为数量较大会超时，采用二分优化，因为本来就形成一个递增数组，不需要采取额外处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:
        c,r,h = 0,0,0
        status = [[0,0,0]]
        res = [-1] *len(requirements)
        for i in increase:
            c,r,h = c+i[0],r+i[1],h+i[2]
            status.append([c,r,h])

        length=len(status)
        for i,requirement in enumerate(requirements):
            left,right=0,length-1
            while left<=right:
                mid = left + (right - left)//2
                if status[mid][0] >= requirement[0] and status[mid][1] >= requirement[1] and status[mid][2] >= requirement[2]:
                    res[i]=mid
                    right=mid-1
                else:
                    left=mid+1
        return res

其他的就暂时没做了，估计也不是我暂时能够踏足的题，DP现在还不熟