LeetCode笔记：Biweekly Contest 68
LeetCode笔记：Biweekly Contest 68
codename_cys
发布于 2021-12-29 08:16:21
发布于 2021-12-29 08:16:21
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题解题思路还是非常直接的，就是把每一个句子进行一下分词，然后统计一下每个句子当中的单词个数，然后返回最大值。
2. 代码实现
给出python代码实现如下：
class Solution:
def mostWordsFound(self, sentences: List[str]) -> int:
return max(len(s.split()) for s in sentences)提交代码评测得到：耗时37ms，占用内存14.6MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题其实就是一个简单地拓扑图的问题，因此也就没啥好多说的了，只要把菜谱和材料转换为一个个节点，那么就很直接了。
2. 代码实现
给出python代码实现如下：
class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
supplies = set(supplies)
needs = defaultdict(list)
builds = defaultdict(list)
cnt = defaultdict(int)
for recipe, ingredient in zip(recipes, ingredients):
needs[recipe] = [i for i in ingredient if i not in supplies]
cnt[recipe] = len(needs[recipe])
for i in ingredient:
if i not in supplies:
builds[i].append(recipe)
res = [x for x in recipes if x in supplies or cnt[x] == 0]
s = [x for x in cnt if cnt[x] == 0]
while s:
r = s.pop(0)
for x in builds[r]:
cnt[x] -= 1
if cnt[x] == 0:
res.append(x)
s.append(x)
return res提交代码评测得到：耗时840ms，占用内存16.8MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的思路其实也挺直接的，显然要使得可以成立，那么需要满足三个条件：
- 总的字符个数是偶数；
- 从左往右所有的右括号都能够找到足够的左括号进行匹配；
- 从右往左所有的左括号都能够找到足够的右括号进行匹配。
2. 代码实现
给出python代码实现如下：
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
if len(s) % 2 == 1:
return False
cnt = 0
for ch, st in zip(s, locked):
if st == "0" or ch == "(":
cnt += 1
else:
if cnt > 0:
cnt -= 1
else:
return False
cnt = 0
for ch, st in zip(s[::-1], locked[::-1]):
if st == "0" or ch == ")":
cnt += 1
else:
if cnt > 0:
cnt -= 1
else:
return False
return True提交代码评测得到：耗时208ms，占用内存15.4MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题讲道理有点取巧了，思路其实还好，如果计算量小，那么我们直接计算出完整的数，如果计算量大，那么我们就只需要考虑最前的5位数以及最后的5位数，而至于0的个数，我们只需要将最后五位数不断地去掉0即可。
不过由于我们中间舍弃了部分位数，因此，我们在实际实现中需要注意精度问题，这里事实上也是多次尝试之后才过了所有的测试case，某种意义上也算是懵的答案……
2. 代码实现
给出python代码实现如下：
class Solution:
def abbreviateProduct(self, left: int, right: int) -> str:
LIMIT = 1000000000000
tot, pre, suf, zero = 1, 1, 1, 0
for i in range(left, right+1):
if tot < 1e10:
tot *= i
while tot % 10 == 0:
tot = tot // 10
pre *= i
while pre >= LIMIT:
pre = pre // 10
suf *= i
while suf % 10 == 0:
suf = suf // 10
zero += 1
suf = suf % LIMIT
if tot < 1e10:
return f"{tot}e{zero}"
else:
pre = "{}".format(pre)[:5]
suf = "{}".format(suf)[-5:]
return f"{pre}...{suf}e{zero}"提交代码评测得到：耗时4708ms，占用内存14.3MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/12/28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
