LeetCode 第 32 场双周赛

 1 class Solution {
 2 public:
 3     int findKthPositive(vector<int>& arr, int k) {
 4         int n = arr.size();
 5         map<int, int> m;
 6         for (int i = 0; i < n; i++) {
 7             m[arr[i]] = 1;
 8         }
 9         for (int i = 1; i <= 2000; i++) {
10             if (!m[i]) {
11                 k--;
12                 if (k == 0) return i;
13             }
14         }
15         return 0;
16     }
17 };

View Code

B K 次操作转变字符串

 1 class Solution {
 2 public:
 3     bool canConvertString(string s, string t, int k) {
 4         int n = s.size();
 5         if (s.size() != t.size()) return false;
 6         map<int, int> m;
 7         for (int i = 0; i < n; i++) {
 8             int cnt = 0;
 9             char c1 = s[i];
10             char c2 = t[i]; 
11             if (c1 <= c2) cnt = (c2 - c1);
12             else cnt = (c2 - 'a' + 1) + ('z' - c1);
13             if (cnt > 0) {
14                 m[cnt]++;
15             }
16         }
17         for (int i = 1; i <= 26; i++) {
18             if (m[i] > 0) {
19                 if (((m[i] - 1) * 26 + i )> k) return false;
20             }
21         }
22         return true;
23     }
24 };

View Code

C 平衡括号字符串的最少插入次数

这题有一些细节问题需要注意，从右往左走的时候遇到 '(' ，如果当前 ')' 数量为奇数，需要变成偶数，因为题目中要求左括号要在连续两个右括号左边，最后跑完之后再对剩余的有括号进行处理下。

 1 class Solution {
 2 public:
 3     int minInsertions(string s) {
 4         int n = s.size();
 5         int ans = 0, cnt = 0;
 6         for (int i =  n - 1; i >= 0; i--) {
 7             if (s[i] == ')') cnt++;
 8             else {
 9                 if (cnt % 2 == 1) cnt++, ans++;
10                 if (cnt == 0) cnt += 2, ans += 2;
11                 cnt -= 2;
12             }
13         }
14         if ( (s[0] == ')') && (cnt % 2) ) ans++, cnt++;
15         ans += (cnt / 2);
16         return ans;
17     }
18 };

View Code

D 找出最长的超赞子字符串

状态压缩DP，没想明白，待补。