【leetcode系列】【算法】2020春季全国编程大赛-个人赛

本文主要是介绍【leetcode系列】【算法】2020春季全国编程大赛-个人赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目一：

解题思路：

奇数需要拿/ 2 + 1次，偶数需要拿/ 2次

代码实现：

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

题目二：

解题思路：

回溯 + 剪枝

走到固定步数，如果是n - 1，则结果个数 + 1,

如果不是，则不继续遍历查找

代码实现：

class Solution:def numWays(self, n: int, relation: List[List[int]], k: int) -> int:rec = collections.defaultdict(list)for a in relation:rec[a[0]].append(a[1])res = set()def numWays_help(k, curr_idx, path, n):nonlocal rec, resif k == 0:if curr_idx == n - 1:res.add((a for a in path))returnfor a in rec[curr_idx]:path.append(a)numWays_help(k - 1, a, path, n)path.pop()numWays_help(k, 0, [], n)return len(res)

题目三：

解题思路：

先根据increase计算出每一天的资源情况

然后对requirements根据求和结果排序，并对排序结果开始遍历

如果一天中的资源之和小于requirements中的资源之和，一定不会符合要求，也一定不会符合requirements后面的要求

代码实现：

class Solution:def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:state_lst = [[0,0,0]]for a in increase:b = state_lst[-1][:]b[0] += a[0]b[1] += a[1]b[2] += a[2]state_lst.append(b[:])rec = {idx : a for idx, a in enumerate(requirements)}idx = 0res = [-1] * len(requirements)start = 0for key in sorted(rec, key = lambda x : sum(rec[x])):last_bigger_start = -1while start < len(state_lst):curr_sum = sum(state_lst[start])if curr_sum < sum(rec[key]):start += 1continueif last_bigger_start == -1:last_bigger_start = startif state_lst[start][0] >= rec[key][0] and state_lst[start][1] >= rec[key][1] and state_lst[start][2] >= rec[key][2]:res[key] = startbreakstart += 1start = last_bigger_startreturn res

题目四：

解题思路：

根据题意，jump[i] >= 1，所以最多经过N步，一定可以跳出jump

初始化一个步数列表，初始化的值为N，个数为N

然后开始遍历每一步能够走到的位置

如果某一步跳出了jump数组，则返回K

否则继续遍历

代码实现：

class Solution:def minJump(self, jump: List[int]) -> int:jump_len = len(jump)step_lst = [0] + [jump_len] * jump_lenstack = [0]left = 0for step in range(1, jump_len + 1):new_stack = []right = max(stack)while left < right:if step < step_lst[left]:step_lst[left] = stepnew_stack.append(left)left += 1left = right + 1for pos in stack:next_pos = pos + jump[pos]if next_pos >= jump_len:return stepelif step < step_lst[next_pos]:step_lst[next_pos] = stepnew_stack.append(next_pos)stack = new_stack[:]return 0