给出题目一的试题链接如下:
这一题思路还是很简单的,用一个字典把两个item列表当中相同val的权重相加即可。
给出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。
给出题目二的试题链接如下:
这一题咋看之下需要一个二重循环,但是事实上我们只需要将数组进行一下变换,将每一个元素减去其位置,那么我们就只要考察相同元素即可了。
所有的好的pair一定都会拥有相同的值,因此我们在所有的pair数当中减去好的那些就能够得到我们的答案了。
给出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。
给出题目三的试题链接如下:
这一题其实非常简单,用一个额外的字典来记录一下每一个任务下次开启的最早时间即可。
给出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。
给出题目四的试题链接如下:
这一题其实就是两个关键点:
由此,我们就能够给我们最终的解了。
给出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。