# # Leetcode 第198场周赛题解

## # Problem A - 换酒问题 (opens new window)

class Solution {
public:
int numWaterBottles(int a, int b) {
int ans = a, bottles = a;
while (bottles >= b) {
ans += bottles / b;
bottles = bottles / b + bottles % b;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11

## # Problem B - 子树中标签相同的节点数 (opens new window)

DFS过程中记录当前节点子树中每种标签的数目即可。

class Solution {
int n;
vector<int> ans;
string labels;
vector<int> dfs(int u, int p) {
vector<int> cnt(26);
cnt[labels[u] - 'a'] = 1;
for (int v : adj[u]) {
if (v != p) {
vector<int> child = dfs(v, u);
for (int i = 0; i < 26; ++i)
cnt[i] += child[i];
}
}
ans[u] = cnt[labels[u] - 'a'];
return cnt;
}
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
ans = vector<int>(n);
this->labels = labels;
this->n = n;
for (auto v : edges) {
}
dfs(0, -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

## # Problem C - 最多的不重叠子字符串 (opens new window)

class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
int n = s.size();
vector<int> first(26, -1), last(26, -1);
vector<vector<int>> v(26);
for (int i = 0; i < n; ++i) {
int d = s[i] - 'a';
v[d].emplace_back(i);
if (first[d] == -1)
first[d] = i;
last[d] = i;
}
for (int k = 0; k < 26; ++k) {
for (int i = 0; i < 26; ++i) {
if (first[i] == -1)
continue;
for (int j = 0; j < 26; ++j) {
if (j == i)
continue;
int l = first[i], r = last[i];
auto lit = lower_bound(v[j].begin(), v[j].end(), l);
auto rit = lower_bound(v[j].begin(), v[j].end(), r);
if (rit - lit > 0) {
first[i] = min(first[i], first[j]);
last[i] = max(last[i], last[j]);
}
}
}
}

vector<pair<int, int>> seg;
for (int i = 0; i < 26; ++i) {
if (first[i] != -1)
seg.emplace_back(first[i], last[i]);
}
sort(seg.begin(), seg.end());
int num = 0, len = n;
vector<int> best;
int m = seg.size();
vector<int> f(m), g(m);
vector<vector<int>> h(m);
for (int i = 0; i < m; ++i) {
int clen = seg[i].second - seg[i].first + 1;
f[i] = 1;
g[i] = clen;
h[i] = {i};
for (int j = 0; j < i; ++j) {
if (seg[j].second < seg[i].first) {
if (f[j] + 1 > f[i] || (f[j] + 1 == f[i] && g[j] + clen < g[i])) {
f[i] = f[j] + 1;
g[i] = g[j] + clen;
h[i] = h[j];
h[i].emplace_back(i);
}
}
}
if (f[i] > num || (f[i] == num && g[i] < len)) {
num = f[i];
len = g[i];
best = h[i];
}
}
vector<string> ans;
for (int i : best)
ans.emplace_back(s.substr(seg[i].first, seg[i].second - seg[i].first + 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

## # Problem D - 找到最接近目标值的函数值 (opens new window)

#define K 20

class Solution {
public:
int closestToTarget(vector<int>& arr, int target) {
int n = arr.size();
vector<vector<int>> st(n, vector<int>(K));
for (int i = 0; i < n; ++i)
st[i][0] = arr[i];
for (int k = 1; k < K; ++k) {
for (int i = 0; i < n; ++i) {
st[i][k] = st[i][k - 1];
int r = i + (1 << (k - 1));
if (r < n)
st[i][k] &= st[r][k - 1];
}
}
auto query = [&](int l, int r) {
if (l == r)
return arr[l];
int len = r - l + 1;
int depth = log2(len - 1);
return st[l][depth] & st[r - (1 << depth) + 1][depth];
};
int ans = INT_MAX;
for (int l = 0; l < n; ++l) {
int lo = l, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
int f = query(l, mid);
if (f == target)
return 0;
if (f < target)
hi = mid - 1;
else
lo = mid + 1;
}
for (int i = max(l, lo - 1); i < min(n, lo + 1); ++i)
ans = min(ans, abs(query(l, i) - target));
}
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

class Solution:
def closestToTarget(self, arr: List[int], target: int) -> int:
ans = abs(arr[0] - target)
valid = {arr[0]}
for num in arr:
valid = {x & num for x in valid} | {num}
ans = min(ans, min(abs(x - target) for x in valid))
return ans

1
2
3
4
5
6
7
8