Leetcode - 133双周赛

目录

一，3206. 交替组 I

二，3207. 与敌人战斗后的最大分数

三，3208. 交替组 II

四，3209. 子数组按位与值为 K 的数目

一，3206. 交替组 I

直接暴力，代码如下：

class Solution {
    public int numberOfAlternatingGroups(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for(int i=0; i<n; i++){
            if(nums[i%n]!=nums[(i+1)%n] && nums[i%n]==nums[(i+2)%n]){
                ans++;
            }
        }
        return ans;
    }
}

二，3207. 与敌人战斗后的最大分数

本题就是一道阅读理解题，可以从游戏的角度去理解：

• currentEnergy就是当前你所拥有的体力，enemyEnergies数组就是游戏中的各种副本（每个副本需要的体力可以不同），但是在本题中刷一个副本只能得到一分
• 操作一就是使用体力去刷副本，我们每刷一个副本就可以获得一分，每个副本可以无限刷
• 操作二就是选择永远不刷这个副本，从而获得对应副本刷一次所需的体力，注意：前提是必须先获得一分

综上所述，可以发现只有当我们将所有的体力去刷所需体力最小的副本，才能获得最多的分数，但是需要特判一种情况——就是我们连一分也得不到，即 currtEnergy < min(nemyEnergies)，直接返回 0.

代码如下：

class Solution {
    public long maximumPoints(int[] enemyEnergies, int currentEnergy) {
        long mn = enemyEnergies[0], s = 0;
        for(int x : enemyEnergies){
            mn = Math.min(mn, x);
            s += x; 
        }
        if(currentEnergy < mn) return 0;
        return (currentEnergy+s-mn)/mn;
    }
}

三，3208. 交替组 II

本题先解决如何判断它是连续k个相邻元素不同的子数组，可以使用一个变量cnt来统计出现几个相邻不同的数，如果cnt >= k（即满足条件），答案++。

接下来就是如何解决它是一个环的问题，我们可以在colors数组后面再copy一下它自己，比如[1，0，1] ——》[1，0，1，1，0，1]，这样就将环转换成了一个数组，但是这里有一个要注意的点是，我们需要在 i >= n 的时候再统计答案，否则会重复计算。

代码如下：

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

四，3209. 子数组按位与值为 K 的数目

本题其实是400周赛的T4，只不过这里问的是有多少子数组，可以使用暴力的思路来写，就是两层for循环遍历，但是可以使用一个 if 条件使其复杂度降低为O(nlongU)，U=max(nums)，这里就不细讲了，不会的看400周赛的那篇题解。

剩下的就是如何计算子数组数量了，因为 &运算有个性质，它 & 的数越多，它的值只能变的越小或不变，具有单调性，所以可以使用两次二分来查找子数组的右端点的范围 [ l，r)，ans += r - l，根据其单调性，我们也可以使用滑动窗口的形式来查找子数组右端点的范围。

代码如下：

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long ans = 0;
        int l = 0, r = 0, n = nums.length;
        for(int i=0; i<n; i++){
            int x = nums[i];
            for(int j=i-1; j>=0; j--){
                if((nums[j]&x) == nums[j])
                    break;
                nums[j] &= x;
            }
            while(l <= i && nums[l] < k)
                l++;
            while(r <= i && nums[r] <= k)
                r++;
            ans += r - l;
        }
        return ans;
    }
}