LeetCode笔记：Biweekly Contest 84
LeetCode笔记：Biweekly Contest 84
codename_cys
发布于 2022-08-23 11:13:11
发布于 2022-08-23 11:13:11
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题思路还是很简单的，用一个字典把两个item列表当中相同val的权重相加即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
res = defaultdict(int)
for v, w in items1:
res[v] += w
for v, w in items2:
res[v] += w
res = [[k,v] for k, v in res.items()]
return sorted(res)提交代码评测得到：耗时137ms，占用内存14.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题咋看之下需要一个二重循环，但是事实上我们只需要将数组进行一下变换，将每一个元素减去其位置，那么我们就只要考察相同元素即可了。
所有的好的pair一定都会拥有相同的值，因此我们在所有的pair数当中减去好的那些就能够得到我们的答案了。
2. 代码实现
给出python代码实现如下：
class Solution:
def countBadPairs(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
nums[i] -= i
cnt = Counter(nums)
res = n * (n-1) // 2
for v in cnt.values():
res -= v * (v-1) // 2
return res提交代码评测得到：耗时898ms，占用内存32.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题其实非常简单，用一个额外的字典来记录一下每一个任务下次开启的最早时间即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def taskSchedulerII(self, tasks: List[int], space: int) -> int:
nxt = defaultdict(int)
day = 0
for t in tasks:
day += 1 + max(0, nxt[t] - day)
nxt[t] = day + space
return day提交代码评测得到：耗时1765ms，占用内存31.2MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题其实就是两个关键点：
- 题目给出的操作只能将数字减小，不可能增大，因此我们只需要倒过来看就可以一个循环搞定了；
- 对于任何一个数y，假设其后一个数字是x，有y = nx + r，那么有两种情况：
- 如果r = 0，那么将会至少经过n-1次操作将这个数变成n个x；
- 如果r \neq 0 ，那么需要经过n次操作，使得最大的数不大于x，此时能够得到的最小数的最大值为\lfloor y/(n+1)\rfloor
由此，我们就能够给我们最终的解了。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumReplacement(self, nums: List[int]) -> int:
n = len(nums)
_max = nums[-1]
res = 0
for i in range(n-1, -1, -1):
if nums[i] <= _max:
_max = nums[i]
continue
m = nums[i] // _max
if nums[i] % _max == 0:
res += m-1
else:
res += m
_max = nums[i] // (m+1)
return res提交代码评测得到：耗时1056ms，占用内存27.8MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-08-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
