LeetCode笔记：Biweekly Contest 89
LeetCode笔记：Biweekly Contest 89
codename_cys
发布于 2022-10-28 10:52:20
发布于 2022-10-28 10:52:20
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题我的思路比较暴力，算是反其道行之吧，正常来说是考察给定的数字可以构成那些组合，但是这样得涉及到一些分类讨论问题。
所以这里我反了一下，直接考察全部可能的时间，然后看有哪些可以用给定的字符串进行表示，这样就可以规避掉分类讨论的问题，不过对应的会增加一下时间开销。
2. 代码实现
给出python代码实现如下：
class Solution:
def countTime(self, time: str) -> int:
def is_equal(t, time):
for c1, c2 in zip(t, time):
if c2 == "?":
continue
elif c1 != c2:
return False
return True
res = 0
for h in range(24):
for m in range(60):
t = f"{h}".rjust(2, "0") + ":" + f"{m}".rjust(2, "0")
if is_equal(t, time):
res += 1
return res提交代码评测得到：耗时82ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题我的思路就是先把给定的n的分解求出来，这个只要通过求
是很方便就可以快速实现的。
然后，求范围内的乘积我们可以通过求取累积乘积的方式进行实现，不过处于简单考察，我们直接使用一个二重循环就行。
2. 代码实现
给出python代码实现如下：
class Solution:
def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
MOD = 10**9 + 7
powers = []
while n != 0:
p = int(log(n) / log(2))
k = 2**p
powers.insert(0, k)
n -= k
res = []
for i, j in queries:
ans = 1
for k in range(i, j+1):
ans = ans * powers[k] % MOD
res.append(ans)
return res提交代码评测得到：耗时5967ms，占用内存51.7MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题我的思路是使用二分法找到最小的可以实现的值。
而对于任意给定的
，要看这个数能否满足，我们只需要看在任意时刻，其之前给出的余留的空间是否足够即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
n = len(nums)
def is_possible(k):
remain = k - nums[0]
for i in range(1, n):
if nums[i] - k > remain:
return False
if nums[i] < k:
remain += k - nums[i]
else:
remain -= nums[i] - k
return True
i, j = max(0, nums[0]-1), max(nums)
while j - i > 1:
m = (i+j) // 2
if is_possible(m):
j = m
else:
i = m
return j提交代码评测得到：耗时6985ms，占用内存26.1MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题实在是没啥思路，只能放弃了……
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
