# # Leetcode 第201场周赛题解

## # Problem A - 整理字符串 (opens new window)

class Solution {
public:
string makeGood(string s) {
while (true) {
int n = s.size();
string t;
for (int i = 0; i < n; ++i) {
if (i + 1 < n && (s[i] - s[i + 1] == 'a' - 'A' || s[i] - s[i + 1] == 'A' - 'a'))
i++;
else
t.push_back(s[i]);
}
if (t == s)
return t;
s = t;
}
return "";
}
};

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

## # Problem B - 找出第 N 个二进制字符串中的第 K 位 (opens new window)

class Solution {
public:
char findKthBit(int n, int k) {
if (n == 1)
return '0';
int len = (1 << n) - 1;
int mid = (len + 1) / 2;
if (k == mid)
return '1';
if (k > mid)
return '1' - findKthBit(n - 1, len + 1 - k) + '0';
return findKthBit(n - 1, k);
}
};

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

## # Problem C - 和为目标值的最大数目不重叠非空子数组数目 (opens new window)

class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int n = nums.size();
vector<int> dp(n + 1);
unordered_map<int, int> dict;
int sum = 0;
dict[0] = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
sum += nums[i - 1];
int delta = sum - target;
if (dict.count(delta))
dp[i] = max(dp[i], dp[dict[delta]] + 1);
dict[sum] = i;
}
return dp[n];
}
};

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

## # Problem D - 切棍子的最小成本 (opens new window)

const int INF = 0x3f3f3f3f;

class Solution {
public:
int minCost(int n, vector<int>& cuts) {
sort(cuts.begin(), cuts.end());
vector<int> seg;
int l = 0;
for (int i : cuts)
seg.emplace_back(i - l), l = i;
seg.emplace_back(n - l);
int m = seg.size();
vector<int> s(m + 1);
for (int i = 1; i <= m; ++i)
s[i] = s[i - 1] + seg[i - 1];
vector<vector<int>> dp(m + 1, vector<int>(m + 1, INF));
for (int i = 1; i <= m; ++i)
dp[i][i] = 0;
for (int k = 2; k <= m; ++k)
for (int i = 1; i + k - 1 <= m; ++i) {
int r = i + k - 1;
for (int j = i; j < r; ++j)
dp[i][r] = min(dp[i][r], dp[i][j] + dp[j + 1][r] + s[r] - s[i - 1]);
}
return dp[1][m];
}
};

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