題目

3206. 交替組 I

3207. 與敵人戰斗后的最大分數

3208. 交替組 II

3209. 子數組按位與值為 K 的數目

一、交替組 I & II

題目中問環形數組中交替組的長度為3的子數組個數，主要的問題在于它是環形的，我們要考慮首尾相接的情況，如何做？

這里我們可以先遍歷整個數組一次，得到與首元素相接的最長的交替組的長度(當然只看最末尾的兩個元素也可以，但是為了防止數組元素太少等極端情況的條件判斷，這里直接遍歷整個數組比較省事)，然后再次遍歷數組開始計數，得到符合要求的交替組個數即可。這里還有一點需要注意，在計數時，我們其實并不關心交替組的長度是否嚴格等于3，只要它的長度>=3就必然能得到一個滿足條件的交替組。代碼如下

class Solution {
public:int numberOfAlternatingGroups(vector<int>& colors) {int n = colors.size(), ans = 0;for(int i = 1, l = 1; i < 2*n; i++){if(colors[i%n]==colors[(i-1)%n]) l = 0;l++;if(i >= n){ans += (l >= 3);}}return ans;}
};

第三題和它一樣，只是將交替組的長度改為參數傳進來了，我們并不關心，只要將上面代碼中的l>=3 改為 l>=k即可，代碼如下

class Solution {
public:int numberOfAlternatingGroups(vector<int>& colors, int k) {int n = colors.size(), ans = 0;for(int i = 1, l = 1; i < 2*n; i++){if(colors[i%n]==colors[(i-1)%n]) l = 0;l++;if(i >= n){ans += (l >= k);}}return ans;}
};

二、與敵人戰斗后的最大分數

這其實是一個簡單的閱讀理解題，簡單來說就是你有初始值currentEnergy，操作一：你可以減去一個比你小且未被標記的數，并得到1分，操作二：如果你有分，你就能獲得其他沒有標記過的數，并標記這些數。如何做讓你的分數盡可能的大？

思路：先找最小值，然后看能否通過它獲得一分(即看currentEnery是否大于等于它)，如果小于，則無法獲得分數，返回0，如果大于等于，我們就能獲得除了最小值之外的所有數，然后在和最小值進行相減，獲得分數，最終返回。

代碼如下

class Solution {
public:long long maximumPoints(vector<int>& enemyEnergies, int currentEnergy) {int mn = INT_MAX;long long s = 0;for(auto e:enemyEnergies){s += e;mn = min(mn, e);}if(mn > currentEnergy) return 0;return (s - mn + currentEnergy)/mn;}
};

三、子數組按位與值為k的數目

像這種按位與運算的題，有一種通用的解法，我們先去暴力的求解所有子數組的&結果，然后我們在去優化，優化的思路都是固定的，根據按位與的性質，參與運算的數字越多，按位與的結果越小，原理如下

?所以我們優化之后算法的時間復雜度只有O(nlogU)，U=max(nums)。代碼如下

class Solution {
public:long long countSubarrays(vector<int>& nums, int k) {long long ans = 0;int n = nums.size(), l = 0, r = 0;for(int i = 0; i < n; i++) {for(int j = i - 1; j >= 0; j--){if((nums[j] & nums[i]) == nums[j])break;nums[j] &= nums[i];}// 用兩個指針來維護 &結果為k的區間while(l <= i && nums[l] < k) l++;while(r <= i && nums[r] <= k) r++;// nums[l] >= k, nums[r] > kans += (r - l);}return ans;}
};