LeetCode笔记：Biweekly Contest 76
LeetCode笔记：Biweekly Contest 76
codename_cys
发布于 2022-05-07 10:35:52
发布于 2022-05-07 10:35:52
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题就是做一个简单地排序就行了，倒是没啥好说的。
2. 代码实现
给出python代码实现如下：
class Solution:
def findClosestNumber(self, nums: List[int]) -> int:
nums = sorted(nums, key=lambda x: (abs(x), -x))
return nums[0]提交代码评测得到：耗时185ms，占用内存14.2MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题遍历一下就完事了，既然不需要用完所有的钱，那么只需要枚举一下买
支钢笔情况下铅笔能有多少选择就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
if cost1 < cost2:
return self.waysToBuyPensPencils(total, cost2, cost1)
res = 0
for i in range(total // cost1 + 1):
res += (total - cost1 * i) // cost2 + 1
return res提交代码评测得到：耗时632ms，占用内存13.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这题算是这周的8道题里面浪费我时间最多的一题了，原因是因为看错了题目……
题目要求的atm就是一个greedy的atm机，不需要从所有支付算法中给出可行解，只需要greedy地从大额面钞进行取用就行，所以实现难度基本为零……
2. 代码实现
给出python代码实现如下：
class ATM:
def __init__(self):
self.vals = [20, 50, 100, 200, 500]
self.cnt = [0, 0, 0, 0, 0]
def deposit(self, banknotesCount: List[int]) -> None:
for i in range(5):
self.cnt[i] += banknotesCount[i]
def withdraw(self, amount: int) -> List[int]:
res = [0, 0, 0, 0, 0]
for i in range(4, -1, -1):
res[i] = min(self.cnt[i], amount // self.vals[i])
amount -= self.vals[i] * res[i]
if amount != 0:
return [-1]
for i in range(5):
self.cnt[i] -= res[i]
return res提交代码评测得到：耗时655ms，占用内存17.5MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题暂时没有啥特别好的思路，所幸题目中的序列相对比较短，只有4个节点，因此，我们通过对中间两个节点进行暴力枚举的方式进行处理。
2. 代码实现
给出python代码实现如下：
class Solution:
def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
for u in graph:
graph[u] = sorted(graph[u], key=lambda x: scores[x], reverse=True)
def get_neighbour(u, ban):
for v in graph[u]:
if v not in ban:
return v
return -1
res = -1
for u in graph:
if len(graph[u]) < 2:
continue
for v in graph[u]:
if v == u or len(graph[v]) < 2:
continue
w = get_neighbour(u, [v])
r = get_neighbour(v, [u, w])
if w != -1 and r != -1:
res = max(res, scores[u] + scores[v] + scores[w] + scores[r])
return res提交代码评测得到：耗时2098ms，占用内存38.9MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
