# # Leetcode 第211场周赛题解

## # Problem A - 两个相同字符之间的最长子字符串 (opens new window)

• 时间复杂度$O(|S|)$
• 空间复杂度$O(C)$，其中$C$为字母表的大小，本题中$C=26$

class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
vector<int> L(26, -1), R(26, -1);
for (int i = 0; i < s.size(); ++i) {
int c = s[i] - 'a';
if (L[c] == -1)
L[c] = i;
R[c] = max(R[c], i);
}
int ans = -1;
for (int i = 0; i < 26; ++i)
if (R[i] != -1 && R[i] > L[i])
ans = max(ans, R[i] - L[i] - 1);
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

## # Problem B - 执行操作后字典序最小的字符串 (opens new window)

• 时间复杂度$O(D^2|S|^2)$，本题中$D=10$
• 空间复杂度$O(|S|)$

class Solution {
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
public:
string findLexSmallestString(string s, int a, int b) {
int n = s.size();
string ans = s;
string t = s + s;
int g = gcd(n, b);
for (int i = 0; i < n; i += g) {
string p = t.substr(i, n);
for (int j = 0; j <= 9; ++j) {
int th = g % 2 == 0 ? 0 : 9;
for (int k = 0; k <= th; ++k) {
string q(p);
for (int t = 1; t < n; t += 2)
q[t] = '0' + (q[t] - '0' + a * j) % 10;
for (int t = 0; t < n; t += 2)
q[t] = '0' + (q[t] - '0' + a * k) % 10;
ans = min(ans, q);
}
}
}
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

## # Problem C - 无矛盾的最佳球队 (opens new window)

• 时间复杂度$O(N^2)$
• 空间复杂度$O(N)$

class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();
vector<int> order(n);
for (int i = 0; i < n; ++i)
order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j){
return ages[i] < ages[j] || (ages[i] == ages[j] && scores[i] < scores[j]);
});
vector<int> dp(n);
int ans = 0;
for (int i = 0; i < n; ++i) {
int idx = order[i];
dp[i] = scores[idx];
for (int j = 0; j < i; ++j) {
int last = order[j];
if (scores[last] <= scores[idx])
dp[i] = max(dp[i], dp[j] + scores[idx]);
}
ans = max(ans, dp[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

## # Problem D - 带阈值的图连通性 (opens new window)

• 时间复杂度$O(N\log N+Q)$
• 空间复杂度$O(N)$

class UnionFind {
int n;
vector<int> parent, size;

public:
UnionFind(int n) {
this->n = n;
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}

int find(int idx) {
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}

void connect(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
if (size[fa] > size[fb]) {
parent[fb] = fa;
size[fa] += size[fb];
} else {
parent[fa] = fb;
size[fb] += size[fa];
}
}
}
};

class Solution {
public:
vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
UnionFind uf(n + 1);
for (int i = threshold + 1; i <= n; ++i)
for (int j = 2 * i; j <= n; j += i)
uf.connect(i, j);
vector<bool> ans;
for (auto &q : queries) {
int u = q[0], v = q[1];
int fu = uf.find(u), fv = uf.find(v);
ans.emplace_back(fu == fv);
}
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