1. Topic 1
The test question link given in question 1 is as follows:
1. Problem solving ideas
The idea of solving this problem is very direct. It is to segment each sentence, then count the number of words in each sentence, and then return to the maximum value.
2. Code implementation
The python code is implemented as follows:
class Solution:
def mostWordsFound(self, sentences: List[str]) -> int:
return max(len(s.split()) for s in sentences)
The submitted code evaluation shows that it takes 37ms and occupies 14.6MB of memory.
2. Topic 2
The link of the test questions given in question 2 is as follows:
1. Problem solving ideas
This problem is actually a simple topology problem, so there is nothing to say. As long as the recipes and materials are converted into nodes, it is very direct.
2. Code implementation
The python code is implemented as follows:
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
The submitted code evaluation shows that it takes 840ms and occupies 16.8MB of memory.
3. Topic 3
The test question link for question 3 is as follows:
1. Problem solving ideas
The idea of this question is actually quite direct. Obviously, to make it feasible, three conditions need to be met:
- The total number of characters is even;
- From left to right, all right parentheses can find enough left parentheses to match;
- All left parentheses from right to left can find enough right parentheses to match.
2. Code implementation
The python code is implemented as follows:
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
The submitted code evaluation shows that it takes 208ms and occupies 15.4MB of memory.
4. Topic 4
The test question link given in question 4 is as follows:
1. Problem solving ideas
This question is reasonable and ingenious. In fact, the idea is good. If the amount of calculation is small, we can directly calculate the complete number. If the amount of calculation is large, we only need to consider the first five digits and the last five digits. As for the number of 0, we only need to constantly remove 0 from the last five digits.
However, because we have abandoned some digits, we need to pay attention to the accuracy in the actual implementation. In fact, we have tried many times before passing all the test case s. In a sense, it is an ignorant answer
2. Code implementation
The python code is implemented as follows:
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}"
The submitted code evaluation shows that it takes 4708ms and occupies 14.3MB of memory.