LeetCode 第 31 场双周赛

1 int countOdds(int low, int high){
2     int ans = (high - low) / 2 + 1;
3     if ((low % 2 == 0 ) && (high % 2 == 0)) ans--;
4     return ans;
5 }

View Code

B 和为奇数的子数组数目

arr前缀和，记录前缀和为奇数的地方，再搞个前缀和。

 1 int numOfSubarrays(int* arr, int arrSize){
 2     int mod = 1e9 + 7;
 3     int sum[arrSize + 10], odd[arrSize + 10];
 4     int ans = 0;
 5     sum[0] = arr[0];
 6     if (arr[0] % 2) odd[0] = 1, ans++;
 7     else odd[0] = 0;
 8     for (int i = 1; i < arrSize; i++) {
 9         sum[i] = sum[i - 1] + arr[i];
10         odd[i] = odd[i - 1];
11         if(sum[i] % 2) odd[i]++, ans++;
12     }
13     for (int i = 1; i < arrSize; i++) {
14         if (sum[i - 1] % 2) {
15             int evencnt = (arrSize - i) - (odd[arrSize - 1] - odd[i - 1]);
16             ans = (ans + evencnt ) % mod;
17         } else{
18             int oddcnt = (odd[arrSize - 1] - odd[i - 1]);
19             ans = (ans + oddcnt ) % mod;
20         }
21     }
22     return ans;
23 }

View Code

C 字符串的好分割数目

 1 int numSplits(char * s){
 2     int n = strlen(s);
 3     int a[n + 10][30];
 4     for (int i  = 0; i < 26; i++) a[0][i] = 0;
 5     a[0][s[0] - 'a']++;
 6     for (int i = 1; i < n; i++) {
 7         for (int j = 0; j < 26; j++) a[i][j] = a[i - 1][j];
 8         a[i][s[i] - 'a']++;
 9     }
10     int ans = 0;
11     for (int i = 0; i < n; i++) {
12         int l = 0, r = 0;
13         for (int j = 0; j < 26; j++) {
14             if (a[i][j] > 0) l++;
15             if ((a[n - 1][j] - a[i][j]) > 0) r++;
16         }
17         if (l == r) ans++;
18     }
19     return ans;
20 }

View Code

D 形成目标数组的子数组最少增加次数

只需要考虑升序，把升序相邻之间的差值处理下。降序的数字增加可以通过延长升序范围处理掉。

1 int minNumberOperations(int* target, int targetSize){
2     int res = target[0];
3     for (int i = 1; i < targetSize; i++) {
4         if (target[i] > target[i - 1]) res += (target[i] - target[i - 1]);
5     }
6     return res;
7 }

View Code