LeetCode笔记：Weekly Contest 202 比赛记录
LeetCode笔记：Weekly Contest 202 比赛记录
codename_cys
发布于 2021-03-28 15:32:26
发布于 2021-03-28 15:32:26
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题没啥花哨的可言，加一个计数器以力破之即可。
2. 代码实现
给出代码实现如下：
class Solution:
def threeConsecutiveOdds(self, arr: List[int]) -> bool:
counter = 0
for n in arr:
if n % 2 == 1:
counter += 1
else:
counter = 0
if counter >= 3:
return True
return False提交代码评测得到：耗时44ms，占用内存14MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
我们考察达到最终结果时的状态，由于原始态的向量为：[1,3,5,...,2n−1]，故达到平衡态时，所有的元素变为：[n,n,n,...,n]，因此，每一个元素需要的操作次数为：[n−1,n−3,...n−3,n−1]。
我们将第i个元素与第n−i个元素进行配对，两者只需要一套操作便可同时完成。因此，我们用一个for循环便可以求解。
2. 代码实现
给出代码实现如下：
class Solution:
def minOperations(self, n: int) -> int:
ans = 0
for i in range(n-1, 0, -2):
ans += i
return ans提交代码评测得到：耗时52ms，占用内存14MB。
3. 代码优化
事实上，更简单的，我们可以直接解析求解得到：
翻译为python代码即有：
class Solution:
def minOperations(self, n: int) -> int:
return n**2 // 4提交后评测得到：耗时32ms，占用内存13.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
2. 代码实现
给出上述思路下的代码实现如下：
class Solution:
def maxDistance(self, position: List[int], m: int) -> int:
position = sorted(position)
n = len(position)
def is_possible(interval):
counter = 1
last = position[0]
for p in position[1:]:
if p - last >= interval:
last = p
counter += 1
return counter >= m
st = 1
ed = position[-1] - position[0] + 1
while ed - st > 1:
mid = (st + ed) // 2
if is_possible(mid):
st = mid
else:
ed = mid
return st提交代码之后评测得到：耗时1312ms，占用内存27.4MB。属于当前第一梯队。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题事实上就是一道简单的动态规划题目。
很显然，当n<=1时，所需时间为n天。
考察当n>1时的情况，要令其最快吃完，我们必然需要令其指数式地下降。因此，最好的解法必定是先将其简直2或3的倍数，而后直接使用策略二或者策略三。
可惜就这题我居然在实做的时候错了好几次，唉，心累。
2. 代码实现
给出代码实现如下：
class Solution:
def minDays(self, n: int) -> int:
@lru_cache(None)
def dp(n):
if n <= 1:
return n
return 1 + min(dp(n // 3) + n % 3, dp(n // 2) + n % 2)
return dp(n)提交后评测得到：耗时36ms，占用内存14.4MB。属于当前第一梯队。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录