# Leetcode 第199场周赛题解

# Problem A - 重新排列字符串 (opens new window)

class Solution {
public:
string restoreString(string s, vector<int>& indices) {
string ans(s);
for (int i = 0; i < indices.size(); ++i)
ans[indices[i]] = s[i];
return ans;
}
};

1
2
3
4
5
6
7
8
9

# Problem B - 灯泡开关 IV (opens new window)

class Solution {
public:
int minFlips(string target) {
int ans = 0;
char last = '0';
for (char c : target) {
if (c != last)
ans++;
last = c;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13

# Problem C - 好叶子节点对的数量 (opens new window)

class Solution {
int ans = 0;
vector<int> dfs(TreeNode* u, int d) {
vector<int> cnt(d + 1);
if (!u)
return cnt;
vector<int> left = dfs(u->left, d);
vector<int> right = dfs(u->right, d);
for (int i = 0; i <= d; ++i)
for (int j = 0; j <= d; ++j)
if (i + j + 2 <= d)
ans += left[i] * right[j];
for (int i = 0; i < d; ++i)
cnt[i + 1] = left[i] + right[i];
if (!u->left && !u->right)
cnt[0] = 1;
return cnt;
}
public:
int countPairs(TreeNode* root, int distance) {
dfs(root, distance);
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

# Problem D - 压缩字符串 II (opens new window)

const int INF = 0x3f3f3f3f;

class Solution {
public:
int getLengthOfOptimalCompression(string s, int k) {
int n = s.size();
if (n == k)
return 0;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
for (int i = 1; i <= n; ++i) {
dp[i][1] = 1;
for (int j = 1; j < n; ++j) {
int cost = 0, cnt = 0;
for (int k = i + 1; k <= n; ++k) {
dp[k][j + 1] = min(dp[k][j + 1], dp[i][j] + 1);
if (s[k - 1] == s[i - 1]) {
cnt++;
if (cnt == 1 || cnt == 9 || cnt == 99)
cost++;
if (j + cnt > n)
break;
dp[k][j + cnt] = min(dp[k][j + cnt], dp[i][j] + cost);
}
}
}
}
int ans = n;
for (int i = 1; i <= n; ++i)
ans = min(ans, dp[i][n - k]);
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