LeetCode 第 200 场周赛

 1 class Solution {
 2 public:
 3     int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
 4         int n = arr.size();
 5         int ans = 0;
 6         for (int i = 0; i < n; i++) {
 7             for (int j = i + 1; j < n; j++) {
 8                 for (int k = j + 1; k < n; k++) {
 9                     if (abs(arr[i] - arr[j]) <= a && abs(arr[j]- arr[k]) <= b && abs(arr[i] - arr[k]) <= c) ans++;
10                 }
11             }
12         }
13         return ans;
14     }
15 };

View Code

B 找出数组游戏的赢家

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

View Code

C 排布二进制网格的最少交换次数

后缀0计数 + 贪心。从上往下遍历，遇到不符合的，从该位置往下找到符合的行换上来，中间计数并交换行和记录的后缀0。

 1 class Solution {
 2 public: 
 3     int minSwaps(vector<vector<int>>& grid) {
 4         vector<int> cnt;
 5         int n = grid.size();
 6         for (int i = 0; i < n; i++) {
 7             int c = 0;
 8             for (int j = n - 1; j >= 0; j--) {
 9                 if (grid[i][j] == 0) c++;
10                 else break;
11             }
12             cnt.push_back(c);
13         }
14         int ans = 0;
15         for (int i = 0; i < n - 1; i++) {
16             bool ok = false;
17             if (cnt[i] >= n - i - 1) continue;
18             for (int j = i + 1; j < n; j++) {
19                 if (cnt[j] >= n - i - 1) {
20                     int p = j;
21                     for (;j > i;j--) {
22                         swap(grid[j], grid[j - 1]);
23                         swap(cnt[j], cnt[j - 1]);
24                         ans++;
25                     }
26                     ok = true;
27                     break;
28                 }
29             }
30             if(!ok) return -1;
31         }
32         return ans;
33     }
34 };

View Code

D 最大得分

一开始写了个记忆化搜索，以nums里的值做标记转移，一直判我数组越界（怀疑给的nums[i]不止1e7，-.-，菜是原罪。之后看了下大佬们的做法，记录下各段交叉点之间的位置，计算分别的sum，取大的那段值即可。还有一种类似我写的记忆化搜索，只不过是以位置做标记，数组开到1e5就可以了的。

 1 class Solution {
 2     typedef long long ll;
 3     const ll mod = 1000000007;
 4 public:
 5     int maxSum(vector<int>& nums1, vector<int>& nums2) {
 6         vector<int> v1, v2;
 7         v1.push_back(0);
 8         v2.push_back(0);
 9         int i = 0, j = 0;
10         int n = nums1.size(), m = nums2.size();
11         while (i < n && j < m) {
12             if (nums1[i] == nums2[j]) {
13                 v1.push_back(i);
14                 v2.push_back(j);
15                 i++;
16             } else if (nums1[i] > nums2[j]) {
17                 j++;
18             } else {
19                 i++;
20             }
21         }
22         v1.push_back(n);
23         v2.push_back(m);
24         int k = v1.size();
25         ll ans = 0;
26         for (int i = 0; i < k - 1; i++) {
27             ll sum1 = 0, sum2 = 0;
28             for (int j = v1[i]; j < v1[i + 1]; j++) sum1 = sum1 + nums1[j];
29             for (int j = v2[i]; j < v2[i + 1]; j++) sum2 = sum2 + nums2[j];
30             ans = (ans + max(sum1, sum2)) % mod;
31         }
32         return ans % mod;
33     }
34 };

View Code