# # Leetcode 第266场周赛题解

## # Problem A - 统计字符串中的元音子字符串 (opens new window)

### # 方法一：暴力穷举

• 时间复杂度$\mathcal{O}(|S|^3)$
• 空间复杂度$\mathcal{O}(|S|^3)$

class Solution:
def countVowelSubstrings(self, word: str) -> int:
n = len(word)
ans = 0
for i in range(n):
for j in range(i + 4, n):
sub = word[i:j + 1]
good = True
s = set(sub)
if len(s) == 5:
for ch in s:
if ch not in 'aeiou':
good = False
break
if good:
ans += 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

### # 方法二：双指针

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution:
def countVowelSubstrings(self, word: str) -> int:
n = len(word)
next_consonant = [n] * n
for i in range(n - 2, -1, -1):
if word[i + 1] not in 'aeiou':
next_consonant[i] = i + 1
else:
next_consonant[i] = next_consonant[i + 1]

ans = 0
l = 0
r = -1
cnt = collections.Counter()
while l < n:
r = max(r, l - 1)

if word[l] not in 'aeiou':
l += 1
cnt = collections.Counter()
continue

jump = False

while len(cnt) < 5 and r + 1 < n:
r += 1
if word[r] in 'aeiou':
cnt[word[r]] += 1
else:
l = r + 1
jump = True
cnt = collections.Counter()
break

if jump:
continue

if len(cnt) == 5:
ans += next_consonant[r] - r

if l < n:
cnt[word[l]] -= 1
if cnt[word[l]] == 0:
del cnt[word[l]]

l += 1
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

## # Problem B - 所有子字符串中的元音 (opens new window)

### # 方法一：遍历

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution:
def countVowels(self, word: str) -> int:
n = len(word)
return sum((i + 1) * (n - i) for i, ch in enumerate(word) if ch in 'aeiou')
1
2
3
4

## # Problem C - 分配给商店的最多商品的最小值 (opens new window)

### # 方法一：二分答案

• 时间复杂度$\mathcal{O}(N\log Q_{\max})$，其中$Q_{\max}$表示数目最多的商品的件数。
• 空间复杂度$\mathcal{O}(C)$

class Solution {
public:
int minimizedMaximum(int n, vector<int>& quantities) {
int m = quantities.size();
int lo = 1, hi = *max_element(quantities.begin(), quantities.end());
while (lo <= hi) {
int mid = (lo + hi) >> 1;
long long need = 0;
for (int q : quantities)
need += (q - 1) / mid + 1;
if (need > n)
lo = mid + 1;
else
hi = mid - 1;
}
return lo;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

## # Problem D - 最大化一张图中的路径价值 (opens new window)

### # 方法一：回溯

1. 节点的度数不超过$4$
2. 边权不小于$10$，同时允许的最长时间不超过$100$

• 时间复杂度$\mathcal{O}(D^{T/t})$。其中$D\le4$为最大度数，$t\ge10$为最小边权，$T\le100$为最长的允许时间。
• 空间复杂度$\mathcal{O}(V+E)$

class Solution {
int max_time, best_value, current_value, current_time;
vector<int> vis, values;

void dfs(int u) {
if (!vis[u])
current_value += values[u];

vis[u]++;
if (u == 0)
best_value = max(best_value, current_value);

for (auto [v, time] : adj[u]) {
if (current_time + time <= max_time) {
current_time += time;
dfs(v);
current_time -= time;
}
}

vis[u]--;
if (!vis[u])
current_value -= values[u];
}
public:
int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int max_time) {
this->max_time = max_time;
this->values = values;
int n = values.size();
vis = vector<int>(n);
for (auto &e : edges) {
int u = e[0], v = e[1], t = e[2];
}

best_value = 0, current_time = 0, current_value = 0;
dfs(0);
return best_value;
}
};
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