# # Leetcode 第32场双周赛题解

## # Problem A - 第k个缺失的正整数 (opens new window)

class Solution {
public:
int findKthPositive(vector<int>& arr, int k) {
vector<bool> c(2001);
for (int i : arr)
c[i] = true;
int v = 0, i = 0;
while (v < k) {
i++;
if (!c[i])
v++;
}
return i;
}
};

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

## # Problem B - K次操作转变字符串 (opens new window)

class Solution {
public:
bool canConvertString(string s, string t, int k) {
if (s.size() != t.size())
return false;
vector<int> cnt(26);
for (int i = 0; i < s.size(); ++i) {
int delta = (t[i] - s[i] + 26) % 26;
cnt[delta]++;
}
int hi = 0;
for (int i = 1; i < 26; ++i)
hi = max(hi, (cnt[i] - 1) * 26 + i);
return hi <= k;
}
};

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

## # Problem C - 平衡括号字符串的最少插入次数 (opens new window)

class Solution {
public:
int minInsertions(string s) {
vector<pair<char, int>> v;
char l = '\$';
int cnt = 0;
s += "#";
for (char c : s) {
if (c == l)
cnt++;
else {
if (cnt > 0)
v.emplace_back(l, cnt);
cnt = 1;
l = c;
}
}
int ans = 0, bal = 0;
for (auto p : v) {
char c = p.first;
int t = p.second;
if (c == ')' && t % 2 == 1) {
ans++;
t++;
}
if (c == '(')
bal += t;
else
bal -= t / 2;
if (bal < 0) {
ans -= bal;
bal = 0;
}
}
ans += bal * 2;
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

## # Problem D - 找出最长的超赞子字符串 (opens new window)

• 0000000000
• 0000000001
• ……
• 1000000000

class Solution {
public:
int longestAwesome(string s) {
vector<int> first(1 << 10, -1);
vector<int> good = {0};
for (int i = 0; i < 10; ++i)
good.emplace_back(1 << i);
first[0] = 0;
int n = s.size(), state = 0;
int ans = 0;
for (int i = 1; i <= n; ++i) {
int c = s[i - 1] - '0';
state ^= (1 << c);
if (first[state] == -1)
first[state] = i;
for (int g : good) {
int need = g ^ state;
if (first[need] != -1)
ans = max(ans, i - first[need]);
}
}
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