# # Leetcode 第68场双周赛题解

## # Problem A - 句子中的最多单词数 (opens new window)

### # 方法一：暴力

• 时间复杂度$\mathcal{O}(\sum|W|)$。其中$|W|$表示单词的长度。
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def mostWordsFound(self, sentences: List[str]) -> int:
return max(map(lambda x: x.count(' ') + 1, sentences))

1
2
3

## # Problem B - 从给定原材料中找到所有可以做出的菜 (opens new window)

### # 方法一：暴力

• 时间复杂度$\mathcal{O}(N^3/W)$。其中$W$为字长。
• 空间复杂度$\mathcal{O}(N^3/W)$

class Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
int n = recipes.size();

unordered_map<string, int> mp;
int idx = 0;
for (auto &s : recipes)
mp[s] = idx++;
for (auto &s : supplies)
mp[s] = idx++;

bitset<200> bs;
for (auto &s : supplies)
bs.set(mp[s]);

vector<bitset<200>> vi(n);
vector<bool> can(n, true);
for (int i = 0; i < n; ++i) {
for (auto &s : ingredients[i]) {
if (!mp.count(s)) {
can[i] = false;
break;
}
vi[i].set(mp[s]);
}
}

bool changed = true;
for (int i = 0; i < n; ++i) {
changed = false;
for (int j = 0; j < n; ++j) {
if (!can[j] || bs[j])
continue;
if ((bs | vi[j]) == bs)
bs.set(j), changed = true;
}
if (!changed)
break;
}

vector<string> ans;
for (int i = 0; i < n; ++i)
if (bs[i])
ans.push_back(recipes[i]);

return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

## # Problem C - 判断一个括号字符串是否有效 (opens new window)

### # 方法一：记录可能的最大和最小平衡值

• 所有位置处的平衡值非负
• 结尾处的平衡值为零

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
bool canBeValid(string s, string locked) {
int n = s.size();
if (n % 2 == 1)
return false;

int lo = 0, hi = 0;

for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
hi++;
if (locked[i] == '1')
lo++;
else
lo = lo == 0 ? 1 : lo - 1;
} else {
lo = lo == 0 ? 1 : lo - 1;
if (locked[i] == '1')
hi--;
else
hi++;
if (lo > hi)
return false;
}
}

return lo == 0;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

## # Problem D - 一个区间内所有数乘积的缩写 (opens new window)

### # 方法一：数学

• 末尾$0$的数量：经典题，统计区间内的数有多少个$2$的因子和$5$的因子即可；

• 末尾五位：去除$2$$5$后，对所有数进行模数为$100000$的带模乘法，并记得在最后乘上没有用掉的$2$$5$

• 开头五位：对所有数取以$10$为底的对数并求和，保留小数部分再还原即可得到。

• 时间复杂度$\mathcal{O}(N\log N)$

• 空间复杂度$\mathcal{O}(N)$

from functools import reduce
from numpy import float128, log10

MOD = 100000

class Solution:
def abbreviateProduct(self, left: int, right: int) -> str:
if right - left + 1 <= 50:
ans = reduce(lambda x, y: x * y, range(left, right + 1), 1)
s = str(ans)
t = s.rstrip('0')
z = len(s) - len(t)
if len(t) <= 10:
return t + 'e' + str(z)
else:
return t[:5] + '...' + t[-5:] + 'e' + str(z)
else:
l = float(
sum(map(lambda x: log10(float128(x)), range(left, right + 1))))
L = str(10 ** (l - trunc(l)) * 10000)[:5]

R = 1
two = 0
five = 0
for i in range(left, right + 1):
num = i
while num % 2 == 0:
two += 1
num >>= 1
while num % 5 == 0:
five += 1
num //= 5
R = R * num % MOD

z = min(two, five)
R = R * pow(2, two - z, MOD) % MOD
R = R * pow(5, five - z, MOD) % MOD
return L + '...' + str(R).rjust(5, '0') + 'e' + str(z)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38