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

2020 Leetcode春季个人赛 2112/4093

成绩

做了两道题,中间跑出去研究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现在还不熟