LeetCode笔记：Weekly Contest 266
LeetCode笔记：Weekly Contest 266
codename_cys
发布于 2021-11-16 16:06:56
发布于 2021-11-16 16:06:56
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题我的思路比较暴力，就是通过一个二重循环直接进行求解。
2. 代码实现
给出python代码实现如下：
class Solution:
def countVowelSubstrings(self, word: str) -> int:
n = len(word)
def have_all(cnt):
return all(cnt[ch] > 0 for ch in "aeiou")
res = 0
for i in range(n):
cnt = defaultdict(int)
for j in range(i, n):
if word[j] not in "aeiou":
break
cnt[word[j]] += 1
if have_all(cnt):
res += 1
return res提交代码评测得到：耗时192ms，占用内存14.2MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题思路也比较直接，就是考察每一个元音贡献的统计次数。对于每一个元音，假设其左右元素的的个数分别为x和y，那么其贡献的统计次数就是( x+1 ) ×(y+1 )。
由此，我们即可求解。
2. 代码实现
给出python代码实现如下：
class Solution:
def countVowels(self, word: str) -> int:
n = len(word)
res = 0
for i in range(n):
if word[i] in "aeiou":
l = i
r = n-1-i
res += (l+1) * (r+1)
return res耗时124ms，占用内存14.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题思路而言也没啥难的，就是通过二分法找到第一个合法的x即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
m = len(quantities)
if n == m:
return max(quantities)
i, j = 0, max(quantities)
while i < j-1:
mid = (i+j) // 2
s = sum(math.ceil(x / mid) for x in quantities)
if s <= n:
j = mid
else:
i = mid
return j提交代码评测得到：耗时2032ms，占用内存28.2MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题坦率地说感觉应该有更好的解决思路，就一直在想，然后没想出来，然后看了一下别人的解法，居然直接暴力的dfs也不会发生超时，就惊呆了……
瞬间感觉没啥难度可言了……
2. 代码实现
给出python代码实现如下：
class Solution:
def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
graph = defaultdict(list)
for u, v, t in edges:
graph[u].append((v, t))
graph[v].append((u, t))
for u in graph:
graph[u] = sorted(graph[u], key=lambda x: x[1])
res = 0
def dfs(u, seen, cost, score):
nonlocal res
if u == 0:
res = max(res, score)
for v, t in graph[u]:
if cost + t > maxTime:
break
if v in seen:
dfs(v, seen, cost+t, score)
else:
dfs(v, seen | {v}, cost+t, score + values[v])
return
dfs(0, {0}, 0, values[0])
return res提交代码评测得到：耗时1472ms，占用内存17.4MB。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-11-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录