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

前言

题解

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

T1. 交替组 I

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

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 0return (s - m + currentEnergy) // m

T3. 交替组 II

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 = 0colors += colors[0:k-1]s0, s1 = 0, 0for c in colors:if c == 0:s0, s1 = s1 + 1, 0res += 1 if s0 >= k else 0else:s0, s1 = 0, s0 + 1res += 1 if s1 >= k else 0return res

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

方法一: 位运算结论题

结论:

$$按位与的序列，最多变化lo{g}_2(v),v为值域$$

同样是枚举右端点，然后处理这个 $lo{g}_2(v)$点即可。

时间复杂度为 $O(nlogv)$, 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(nlogn)$
• 枚举+三指针$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;}staticclass 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]);}}
}

写在最后