力扣第 134 场双周赛解题报告

力扣第 134 场双周赛解题报告 | 珂学家

前言

题解

T1/T3是环形的处理技巧，这边可以double数组(更准确地讲，添加一个合适的小尾巴).
T4是典题，前不久周赛刚考过，是一道结论题，也可以借助数据结构处理。

T1. 交替组 I

和T3一起讲

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

题型: 阅读理解题

思路: 贪心

最小代价得分，那就永远取最小的
能量最大化，获取非最小值的所有能量

有解的前提，需要保证

$\ge 最小值$

class Solution {
    public long maximumPoints(int[] es, int v) {  
        long s = Arrays.stream(es).mapToLong(Long::valueOf).sum();
        int m = Arrays.stream(es).min().getAsInt();
        if (v < m) return 0;
        return (s - m + v) / m;  
    }
}

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        s, m = sum(enemyEnergies), min(enemyEnergies)
        if currentEnergy < m:
            return 0
        return (s - m + currentEnergy) // m

T3. 交替组 II

环形的处理技巧之一

扩充原有的数组

$原数组添加前 k - 1 项到尾部$

剩下的事情就容易处理了

枚举右端点
状态计数s0/s1, 表示以0,1结尾且交替的最长子数组

class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        
        // 环形扩增
        int[] arr = new int[n + k - 1];
        for (int i = 0; i < n + k - 1; i++) arr[i] = colors[i % n];

        // 引入状态计数，表示以0,1结尾符合交替的最长计数
        int s0 = 0, s1 = 0;
        // 枚举右端点
        for (int i = 0; i < n + k - 1; i++) {
            if (arr[i] == 0) {
                s0 = s1 + 1;
                s1 = 0;
            } else {
                s1 = s0 + 1;
                s0 = 0;
            }
            if (s1 >= k) res += 1;
            if (s0 >= k) res += 1;
        }
        return res;
    }
}

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        res = 0
        colors += colors[0:k-1]
        s0, s1 = 0, 0
        for c in colors:
            if c == 0:
                s0, s1 = s1 + 1, 0
                res += 1 if s0 >= k else 0
            else:
                s0, s1 = 0, s0 + 1
                res += 1 if s1 >= k else 0
        return res

T4. 子数组按位与值为 K 的数目

这题属于糖题，方法特别多

按位与的序列，它有一个显著的特点，就是呈现单调性

方法一: 位运算结论题

结论:

$按位与的序列，最多变化log_2(v), v为值域$

同样是枚举右端点，然后处理这个 $log_2(v)$ 点即可。

时间复杂度为 $O (n l o gv)$ , v为值域

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long res = 0;
        
        int n = nums.length;
        
        // 维护值/位置的信息
        TreeMap<Integer, Integer> prev = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            
            TreeMap<Integer, Integer> next = new TreeMap<>();
            for (var kv: prev.entrySet()) {
                next.put(kv.getKey() & nums[i], kv.getValue());
            }
            next.put(nums[i], i);
            
            // 如果存在k值，必然存在一个区间
            if (next.containsKey(k)) {
                var nk = next.lowerEntry(k);
                if (nk == null) {
                    res += next.get(k) + 1;
                } else {
                    res += (next.get(k) - nk.getValue());
                }
            }
            prev = next;
        }
        return res;
    }
}

方法二: ST表 + 三指针

其实ST表上二分也可以，但是三指针处理起来更优雅

这样时间复杂度为

ST预处理 $O (n l o g n)$
枚举+三指针 $O (n)$

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long res = 0;
        int n = nums.length;
        SparesTable st = new SparesTable(nums, (a, b) -> a & b);

        int j0 = 0, j1 = 0;
        for (int i = 0; i < n; i++) {
            // 注意是 <
            while (j0 <= i && st.query(j0, i) < k) {
                j0++;
            }
            // 注意是 <=
            while (j1 <= i && st.query(j1, i) <= k) {
                j1++;
            }
            res += (j1 - j0);
        }
        return res;
    }

    static
    class SparesTable {
        int[][] tables;
        BiFunction<Integer, Integer, Integer> callback;

        public SparesTable(int[] arr, BiFunction<Integer, Integer, Integer> callback) {
            int n = arr.length;
            int m = (int)(Math.log(n) / Math.log(2) + 1);
            tables = new int[m][n];
            this.callback = callback;

            for (int i = 0; i < n; i++) {
                tables[0][i] = arr[i];
            }
            for (int i = 1; i < m; i++) {
                int half = 1 << (i - 1);
                for (int j = 0; j + half < n; j++) {
                    tables[i][j] = callback.apply(tables[i - 1][j], tables[i - 1][j + half]);
                }
            }
        }
        // 闭闭区间
        int query(int l, int r) {
            int t = (int)(Math.log(r - l + 1) / Math.log(2));
            return callback.apply(tables[t][l], tables[t][r - (1 << t) + 1]);
        }
    }
}