【刷题笔记】第三天

两道简单题

2923. 找到冠军 I

方法1：
如果 i 是冠军，那么 grid[i][j] == 1, 其中j!=i
所以我们遍历grid的每一行，假设是第i行，只要除第i列外，其他位置的元素都是1，则 i 就是冠军。
除了判断每一行，也可以判断每一列，只要这一列的所有元素都为0，说明没有队伍可以战胜该队伍。

class Solution {public int findChampion(int[][] grid) {for (int i = 0; i < grid.length; ++i) {boolean flag = true; // 记录是否决出了冠军for (int j = 0; j < grid[i].length; ++j) {if (j != i && grid[i][j] == 0) {flag = false; // j比i强，i不可能是冠军break;}}if (flag) {return i;}}return -1;}
}

时间复杂度$O(n^2)$

方法2：擂主争霸

class Solution {public int findChampion(int[][] grid) {int champinon = 0; // 假设0是冠军int index = 1;int n = grid.length;while (index < n) {if (grid[index][champinon] == 1) {// index比champinon，所以冠军变为indexchampinon = index;}// 冠军变了，为什么index不需要从0开始？// 因为在1~index - 1都不能战胜原来的冠军，当然更战胜不了当前的冠军（当前的冠军战胜了原来的冠军）index++;}return champinon;}
}

时间复杂度 O(n)

3095. 或值至少 K 的最短子数组 I

3097. 或值至少为 K 的最短子数组 II
两道题区别只是数据规模不同

方法1：
暴力枚举每一个子数组

class Solution {public int minimumSubarrayLength(int[] nums, int k) {int ans = Integer.MAX_VALUE;for (int i = 0; i < nums.length; ++i) {int res = 0;for (int j = i; j < nums.length; ++j) {res |= nums[j];if (res >= k) {ans = Math.min(ans, j - i + 1);break;}}}return ans == Integer.MAX_VALUE ? -1 : ans;}
}

方法2：
遇到到子数组考虑以i结尾的子数组……
或的性质：越或，值越大或者不变，肯定不能变小。
考虑以i结尾的子数组，当i-1结尾的子数组的或值 |nums[i] ，就是i结尾的子数组的或值。
为了计算最短子数组的长度，在保存或值的同时，记录该或值对应的左端点位置。如果遇到相同的或值，就保留最大的左端点。

还有一些coding细节，例如如何利用一个list，动态的更新当前子数组的或值，下面代码用到了双指针思想。

class Solution {public int minimumSubarrayLength(int[] nums, int k) {// list中的元素按照左端点位置从小到大排序List<int[]> list = new ArrayList<>();// 保存以i结尾的子数组的{or值，对应的最大左端点}int n = nums.length;int ans = Integer.MAX_VALUE;for (int i = 0; i < n; ++i) {list.add(new int[]{0, i}); // 先占个位，不参与或运算// 此时，list是以i-1结尾的子数组的or值及其左端点位置int l = 0, r = 0;// 将list中的元素或上nums[i]for (; r < list.size(); ++r) {int[] cur = list.get(r);cur[0] |= nums[i];if (cur[0] >= k) {// 满足条件就收集结果ans = Math.min(ans, i - cur[1] + 1);}if (cur[0] == list.get(l)[0]) {// 有重复值，保留左端点最大的list.get(l)[1] = cur[1]; // 左端点更新为最大的} else {list.set(++l, cur); // 将l+1位置覆盖}}// 以i结尾的子数组对应的或值，其实是[0, l]范围，l之后的元素需要删除list.subList(l + 1, list.size()).clear();}return ans == Integer.MAX_VALUE ? -1 : ans;}
}

优化：list.subList(l + 1, list.size()).clear();这一行代码其实是比较耗时的，其实可以用一个变量记录有效值的长度。用二维数组保存子数组的或值和左端点位置

二维数组优化

class Solution {public int minimumSubarrayLength(int[] nums, int k) {// 为什么只需要开32长度的二维数组?// 注意题目中说了nums中的元素最大位int[][] list = new int[32][2]; // list[i][0]表示或值，list[i][1]表示对应的左端点位置int len = 0; // 记录list中的有效值int n = nums.length;int ans = Integer.MAX_VALUE;for (int i = 0; i < n; ++i) {list[len][0] = 0;list[len++] = i;int l = 0, r = 0;for (; r < len; ++r) {int[] cur = list[r];cur[0] |= nums[i];if (cur[0] >= k) {ans = Math.min(ans, i - cur[1] + 1);}if (cur[0] == list[l][0]) {list[l][1] = cur[1]; // 重复值} else {list[++l][0] = cur[0];list[l][1] = cur[1];}}len = l + 1; // 更新有效值的长度}return ans == Integer.MAX_VALUE ? -1 : ans;}
}

为什么只需要开辟32长度的二维数组？
nums[i] <=$10^9$，而$2^{29}<10^9<2^{30}$，假设nums[i] = $10^9$，其二进制位数也就31位。
由于或操作，可以使一位或者多位由0变为1，所以或值最多也就有31种，所以开辟32长度的二维数组，足以保存所有的或值。