# # Leetcode 第205场周赛题解

## # Problem A - 替换所有的问号 (opens new window)

class Solution {
public:
string modifyString(string s) {
int n = s.size();
vector<int> v;
for (int i = 0; i < n; ++i)
if (s[i] == '?') {
v.emplace_back(i);
s[i] = 'a';
}
auto check = [&](int i) {
if (i > 0 && s[i] == s[i - 1])
return false;
if (i < n - 1 && s[i] == s[i + 1])
return false;
return true;
};
for (int i : v) {
if (!check(i)) {
for (char ch = 'a'; ch <= 'z'; ++ch) {
s[i] = ch;
if (check(i))
break;
}
}
}
return s;
}
};

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

## # Problem B - 数的平方等于两数乘积的方法数 (opens new window)

typedef long long ll;

class Solution {
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
map<ll, int> sq1, sq2;
int n1 = nums1.size(), n2 = nums2.size();
for (int num : nums1)
sq1[(ll)num * num]++;
for (int num : nums2)
sq2[(ll)num * num]++;
ll ans = 0;
for (int i = 0; i < n1; ++i)
for (int j = i + 1; j < n1; ++j)
ans += sq2[(ll)nums1[i] * nums1[j]];
for (int i = 0; i < n2; ++i)
for (int j = i + 1; j < n2; ++j)
ans += sq1[(ll)nums2[i] * nums2[j]];
return ans;
}
};

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

## # Problem C - 避免重复字母的最小删除成本 (opens new window)

const int INF = 0x3f3f3f3f;

class Solution {
public:
int minCost(string s, vector<int>& cost) {
int n = s.size();
vector<int> dp(26);
for (int i = 1; i <= n; ++i) {
vector<int> ndp(26, INF);
int c = s[i - 1] - 'a';
for (int j = 0; j < 26; ++j) {
ndp[j] = min(ndp[j], dp[j] + cost[i - 1]);
if (j != c)
ndp[c] = min(ndp[c], dp[j]);
}
dp = move(ndp);
}
return *min_element(dp.begin(), dp.end());
}
};

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

## # Problem D - 保证图可完全遍历 (opens new window)

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) {
a--, 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];
}
}
}

int components() {
vector<bool> is_root(n);
for (int i = 0; i < n; ++i)
is_root[find(i)] = true;
int ans = 0;
for (int i = 0; i < n; ++i)
ans += is_root[i];
return ans;
}
};

class Solution {
public:
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
int m = edges.size();
UnionFind ufa(n), ufb(n);
for (auto v : edges) {
if (v[0] == 3) {
ufa.connect(v[1], v[2]);
ufb.connect(v[1], v[2]);
}
}
int c = ufa.components();
for (auto v : edges) {
if (v[0] == 1)
ufa.connect(v[1], v[2]);
}
if (ufa.components() != 1)
return -1;
for (auto v : edges) {
if (v[0] == 2)
ufb.connect(v[1], v[2]);
}
if (ufb.components() != 1)
return -1;
return m - (n - c) - (c - 1) * 2;
}
};

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
70
71