# LeetCode notes: Biweekly Contest 68

## 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:

1. The total number of characters is even;
2. From left to right, all right parentheses can find enough left parentheses to match;
3. 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.

Keywords: Python Algorithm leetcode

Added by secoxxx on Tue, 28 Dec 2021 10:30:32 +0200