LeetCode 第 68 场双周赛总结

LeetCode 第 68 场双周赛总结

5946. 句子中的最多单词数

这是我写的：执行用时: 32 ms，内存消耗: 15.2 MB

class Solution:def maxSubsequence(self, nums: List[int], k: int) -> List[int]:ans = 1for sentence in sentences:sen = sentence.split(' ')ans = max(ans, len(sen))return ans

这是大佬写的：执行用时: 32 ms，内存消耗: 15.1 MB

class Solution:def maxSubsequence(self, nums: List[int], k: int) -> List[int]:return max(len(sentence.split()) for sentence in sentences)

我用了额外空间，属实没必要~

5947. 从给定原材料中找到所有可以做出的菜

这题真的能看出来算法的博大精深，因为我的用时和大佬的差距太太太大了。
这是我写的：执行用时: 9904 ms，内存消耗: 16.6 MB

class Solution:def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:lenr, leni, lens = len(recipes), len(ingredients), len(supplies)isinsup = [False for i in range(lenr)]flag = Truewhile flag:flag = Falsefor i in range(lenr):if not isinsup[i] and all(ing in supplies for ing in ingredients[i]):flag = Truesupplies.append(recipes[i])isinsup[i] = Truereturn supplies[lens:]

这是大佬写的：执行用时: 176 ms，内存消耗: 16.7 MB，双100%

class Solution:def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:# 建图，并记录入度indegreegraph = collections.defaultdict(list)indeg = collections.defaultdict(int)for u, vs in zip(recipes, ingredients):for v in vs:graph[v].append(u)indeg[u] += 1# 将原材料作为迭代的起始点【题目已满足：给定的原材料在图中的入度均为0】deque = collections.deque(supplies)# 从原材料开始迭代，并更新indegreewhile deque:cur = deque.popleft()for nxt in graph[cur]:    # 遍历当前 cur 节点的邻居/子代节点indeg[nxt] -= 1if indeg[nxt] == 0:   # indegree=0则加入队列deque.append(nxt)res = [rec for rec in recipes if indeg[rec] == 0] return res

5948. 判断一个括号字符串是否有效

大佬写的：执行用时: 248 ms，内存消耗: 15.5 MB

class Solution:def canBeValid(self, s: str, locked: str) -> bool:if len(s)%2 == 1:return False# 正序遍历：未匹配的左括号 ( 的最大数目cnt = 0for ch, b in zip(s, locked):if ch == '(' and b == '1':cnt += 1elif ch == ')' and b == '1':cnt -= 1elif b == '0':cnt += 1   if cnt < 0:return False# 逆序遍历：未匹配的右括号 ) 的最大数目cnt = 0for ch, b in zip(s[::-1], locked[::-1]):if ch == ')' and b == '1':cnt += 1elif ch == '(' and b == '1':cnt -= 1elif b == '0':cnt += 1if cnt < 0:return Falsereturn True

5949. 一个区间内所有数乘积的缩写

大佬写的：执行用时: 3388 ms，内存消耗: 15 MB

class Solution:def abbreviateProduct(self, left: int, right: int) -> str:if right - left < 30 :to_ret = 1for n in range(left, right+1) :to_ret *= nn0 = 0while to_ret % 10 == 0 :n0 += 1to_ret = to_ret // 10to_ret = str(to_ret)if len(to_ret) <= 10 :return to_ret + 'e' + str(n0)else :return to_ret[:5] + '...' + to_ret[-5:] + 'e' + str(n0)n0 = 0to_reth = 1to_rett = 1for n in range(left, right+1) :to_reth = to_reth * nwhile to_reth >= 10**5 :to_reth = to_reth / 10to_rett = to_rett * nwhile to_rett % 10 == 0 :to_rett = to_rett // 10n0 += 1to_rett = to_rett % (10**32)return str(int(to_reth)) + '...' + str(to_rett)[-5:] + 'e' + str(n0)