LeetCode笔记：Biweekly Contest 70
LeetCode笔记：Biweekly Contest 70
codename_cys
发布于 2022-04-13 16:24:43
发布于 2022-04-13 16:24:43
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题直接使用贪婪算法即可实现。
首先我们将价格进行排序，然后价格最大的两个必然只能靠自费，而后我们就可以免费获得价格第三高的糖果，重复上述操作即可可到最终的答案。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumCost(self, cost: List[int]) -> int:
cost = sorted(cost, reverse=True)
cost = [c for i, c in enumerate(cost) if i % 3 != 2]
return sum(cost)提交代码评测得到：耗时40ms，占用内存14.4MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题首先就是我们假设第一个元素为0，那么显然我们可以恢复出完整的序列。
此时，我们就可以得到这个序列当中最大元素与最小元素的差值，此时我们给出的范围与这个差值的差即为我们的答案。
2. 代码实现
给出python代码实现如下：
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
n = len(differences)
nums = [0 for _ in range(n+1)]
for i in range(n):
nums[i+1] = nums[i] + differences[i]
_min, _max = min(nums), max(nums)
delta = _max - _min
res = upper - lower - delta + 1
return res if res >= 0 else 0提交代码评测得到：耗时1943ms，占用内存28.8MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题其实只需要通过一个bfs就能够获得能够走到的所有的格子，然后我们对其按照排序规则进行排序之后取前k个元素即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
n, m = len(grid), len(grid[0])
i, j = start
q = [start + [0]]
reachable = []
seen = set([(i, j)])
while q:
i, j, s = q.pop(0)
if pricing[0] <= grid[i][j] <= pricing[1]:
reachable.append([s, grid[i][j], i, j])
if i-1 >= 0 and grid[i-1][j] != 0 and (i-1, j) not in seen:
q.append((i-1, j, s+1))
seen.add((i-1, j))
if i+1 < n and grid[i+1][j] != 0 and (i+1, j) not in seen:
q.append((i+1, j, s+1))
seen.add((i+1, j))
if j-1 >= 0 and grid[i][j-1] != 0 and (i, j-1) not in seen:
q.append((i, j-1, s+1))
seen.add((i, j-1))
if j+1 < m and grid[i][j+1] != 0 and (i, j+1) not in seen:
q.append((i, j+1, s+1))
seen.add((i, j+1))
reachable = sorted(reachable)[:k]
return [x[2:] for x in reachable] 提交代码评测得到：耗时3336ms，占用内存68.3MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题其实相较上一题反而更加简单，我们只要以每两个位子为界，考察两个room之间的plant数目（不妨即为k），那么在这两个之间就有
种树立墙板的方法，而我们累乘所有的可能性即可得到我们最终的答案。
2. 代码实现
给出python代码实现如下：
class Solution:
def numberOfWays(self, corridor: str) -> int:
MOD = 10**9 + 7
corridor = corridor.strip("P")
seat_num = len([ch for ch in corridor if ch == "S"])
if seat_num == 0 or seat_num % 2 != 0:
return 0
i, cnt, n = 0, 0, len(corridor)
res = 1
while i < n:
if corridor[i] == "P":
i += 1
continue
cnt += 1
if cnt % 2 == 0:
j = i+1
while j < n and corridor[j] == "P":
j += 1
res = res * (j-i) % MOD
i = j
else:
i += 1
return res提交代码评测得到：耗时1355ms，占用内存16MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022/01/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
