力扣第 134 场双周赛

比赛时间 2024-07-06。本场周赛国服共 360 人 AK。

T1. 交替组 I（3 分）

解题思路

见 T3。

参考代码

略。

T2. 与敌人战斗后的最大分数（4 分）

解题思路

诈骗题。

只有两种情况：一个都击败不了；或者能量增加至敌人总和，然后捏软柿子，选最弱的敌人得分。

时间复杂度：O(n)。

参考代码

class Solution {
    public long maximumPoints(int[] enemyEnergies, int currentEnergy) {
        int mn = Arrays.stream(enemyEnergies).min().orElseThrow();
        if (currentEnergy >= mn) {
            long sum = currentEnergy;
            for (int v : enemyEnergies) {
                sum += v;
            }
            return sum / mn - 1;
        }
        return 0;
    }
}

T3. 交替组 II（5 分）

解题思路

前缀和。环形数组多一个下标取模。和 3152 题基本一样。

时间复杂度：O(n)。

参考代码

class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
        int[] ps = new int[n * 2 + 1];
        for (int i = 1; i < n * 2; i++) {
            int ai = (colors[(i - 1) % n] + colors[i % n]) % 2 == 1 ? 0 : 1;
            ps[i] = ps[i - 1] + ai;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (ps[k + i - 1] - ps[i] == 0) {
                ans++;
            }
        }
        return ans;
    }
}

T4. 子数组按位与值为 K 的数目（7 分）

解题思路

logTrick。和 CF452D 基本一样（CF452D 是进阶版本）。

时间复杂度：O(nlogU)。

参考代码

class Solution {
    public long countSubarrays(int[] nums, int K) {
        int n = nums.length;
        Map<Integer, Long> cnt = new HashMap<>();
        // v,l,r
        List<int[]> b = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int[] p : b) {
                p[0] &= x;
            }
            b.add(new int[]{x, i, i + 1});
            int k = 0;
            for (int j = 1; j < b.size(); j++) {
                int[] q = b.get(j);
                if (b.get(k)[0] == q[0]) {
                    b.get(k)[2] = q[2];
                } else {
                    k++;
                    b.set(k, q);
                }
            }
            // b = b[:k+1]
            b.subList(k + 1, b.size()).clear();
            for (int[] p : b) {
                cnt.put(p[0], cnt.getOrDefault(p[0], 0L) + p[2] - p[1]);
            }
        }

        return cnt.getOrDefault(K, 0L);
    }
}

（全文完）