LeetCode笔记：Weekly Contest 271
LeetCode笔记：Weekly Contest 271
codename_cys
发布于 2021-12-20 19:27:28
发布于 2021-12-20 19:27:28
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题只要统计每一个位置上出现的所有的颜色，然后将包含了所有3中颜色的位置进行一下计数即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def countPoints(self, rings: str) -> int:
n = len(rings)
cnt = defaultdict(set)
for i in range(0, n, 2):
cnt[rings[i+1]].add(rings[i])
return len([x for x in cnt if len(cnt[x]) == 3])提交代码评测得到：耗时32ms，占用内存14.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题本来还想着有没有什么好的思路，不过碰壁了几次之后最后还是用了最暴力的二重循环处理了一下，毕竟本身并不是什么难题，不过还是觉得应该有更好的解题方法的，唉……
2. 代码实现
给粗python代码实现如下：
class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
n = len(nums)
res = 0
for i in range(n-1):
_min, _max = nums[i], nums[i]
for j in range(i+1, n):
_min = min(nums[j], _min)
_max = max(nums[j], _max)
res += _max - _min
return res提交代码评测得到：耗时4272ms，占用内存14.4MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题同样感觉只要按照题意按部就班地进行实现即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
n = len(plants)
i, j = 0, n-1
a, b = capacityA, capacityB
res = 0
while i < j:
if a < plants[i]:
a = capacityA
res += 1
a -= plants[i]
i += 1
if b < plants[j]:
b = capacityB
res += 1
b -= plants[j]
j -= 1
return res+1 if i == j and max(a, b) < plants[i] else res提交代码评测得到：耗时848ms，占用内存29.4MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题的思路来说的最终结果就是吃掉前后某一个范围内的所有的果实数目，因此，我们要做的就是首先用一个累积数组记录每一个位置前方所有的果实数目，然后遍历长度为k的所有可以覆盖的范围内的果实总数。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
n = len(fruits)
for i in range(n-1):
fruits[i+1][1] += fruits[i][1]
fruits = [[-1, 0]] + fruits + [[math.inf, fruits[-1][1]]]
l = bisect.bisect_left(fruits, [startPos-k, 0])
res = 0
while fruits[l][0] <= startPos:
lbound = fruits[l][0]
rbound = max(k - 2*(startPos-lbound) + startPos , startPos + (k - (startPos-lbound)) // 2)
r = bisect.bisect_right(fruits, [rbound, math.inf]) -1
res = max(res, fruits[r][1] - fruits[l-1][1])
l += 1
rbound = startPos + k
r = bisect.bisect_right(fruits, [rbound, math.inf]) -1
res = max(res, fruits[r][1] - fruits[l-1][1])
return res 提交代码评测得到：耗时1860ms，占用内存60.8MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-12-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录