成都 网站推广,如何用网站模板做网站,高端 网站定制,做算命网站目录 一#xff0c;3095. 或值至少 K 的最短子数组 I
二#xff0c;3096. 得到更多分数的最少关卡数目
三#xff0c;3097. 或值至少为 K 的最短子数组 II
四#xff0c;3098. 求出所有子序列的能量和 一#xff0c;3095. 或值至少 K 的最短子数组 I 本题需要知道一个知…
目录 一3095. 或值至少 K 的最短子数组 I
二3096. 得到更多分数的最少关卡数目
三3097. 或值至少为 K 的最短子数组 II
四3098. 求出所有子序列的能量和 一3095. 或值至少 K 的最短子数组 I 本题需要知道一个知识点0|0 00|1 11|1 1根据上述性质可以得出每按位或一个数这个数要么变大要么不变也就是说它有一个非递减的性质。在者这道题的数据范围不大可以直接暴力代码如下 class Solution {public int minimumSubarrayLength(int[] nums, int k) {int n nums.length;int ans Integer.MAX_VALUE;for(int i0; in; i){int or 0;for(int ji; jn; j){or | nums[j];if(or k){ans Math.min(ans, j-i1);break;}}}return ansInteger.MAX_VALUE?-1:ans;}
}
二3096. 得到更多分数的最少关卡数目 本题实际上就是求前缀和大于后缀和的所需要的最小数量需要先统计整个数组的和sum再遍历数组possible用一个额外变量pre统计它的前缀和那么sum - pre就是它的后缀和如果 pre sum - pre返回结果代码如下 class Solution {public int minimumLevels(int[] possible) {int sum 0;for(int x : possible) sum x0?-1:1;int n possible.length;int pre 0;for(int i0; in; i){if(i0 pre sum - pre)return i;pre possible[i]0?-1:1;}return -1;}
}
三3097. 或值至少为 K 的最短子数组 II 本题和第一题相同但是数据范围更大无法使用暴力但是结论可以使用一个数按位或的越多那么就会变大或不变 方法一滑动窗口 使用一个大小为32的数组来统计32个比特位各出现了几次 每遍历到一个数遍历它的32个bit位如果cnt[i]0 (xi)11时说明当前数字按位或后这个bit位会从0变成1所以 k - 1i当 k 0 时说明当前按位与的数已经大于k了就可以更新ans同时可以缩减[l,r]的范围看看当l变大时是否满足k0注意删除nums[l]时遍历它的32个bit位如果cnt[i]1 ((nums[l]i)1)1说明删除这个数后按位或的这个数会减小所以 k 1i注意当 k 0 时直接返回 1 class Solution {public int minimumSubarrayLength(int[] nums, int k) {int[] cnt new int[32];//统计bit位出现了几次int n nums.length;int ans Integer.MAX_VALUE;if(k 0) return 1;for(int l0,r0; rn; r){int x nums[r];for(int i0; i32; i){if(cnt[i]0 ((xi)1)1)//按位或之后这个bit位会从0变成1k - 1i;cnt[i] (xi)1;}while(k 0){ans Math.min(ans, r-l1);//跟新答案int y nums[l];for(int i0; i32; i){if(cnt[i]1 ((yi)1)1)//丢掉y之后,这个bit位是否会从1变成0k 1i;cnt[i] - (yi)1;}l;}}return ansInteger.MAX_VALUE?-1:ans;}
} 方法二通用模板 遍历数组nums使用二维数组不停的更新以 i 为右端点的按位或值及其最大左端点同时计算符合条件的最短子数组 class Solution {public int minimumSubarrayLength(int[] nums, int k) {int ans Integer.MAX_VALUE;int[][] or new int[32][2];int m 0;int n nums.length;for(int i0; in; i){or[m][0] 0;or[m][1] i;//更新操作int j 0;for(int idx0; idx m; idx){or[idx][0] | nums[i];if(or[idx][0] k){ans Math.min(ans, i-or[idx][1]1);}if(or[idx][0] ! or[j][0])//去重or[j][0] or[idx][0];or[j][1] or[idx][1];}m j1;}return ans Integer.MAX_VALUE ? -1 : ans;}
}
四3098. 求出所有子序列的能量和 本题是一道单纯的dfs记忆化题有两种做法 枚举选哪个选或不选 枚举选哪个 class Solution {static final int MOD (int)1e97;int[] nums;int n;MapLong, Long map new HashMap();public int sumOfPowers(int[] nums, int k) {this.nums nums;Arrays.sort(nums);this.n nums.length;long ans dfs(0,k,Integer.MAX_VALUE, -1);return (int)ans%MOD;}long dfs(int idx, int k, int min, int j){if(k 0){return min;}long res 0;long key ((long)min18|idx12|k6|(j1));if(map.containsKey(key)) return map.get(key);for(int iidx; in-k; i){res (res dfs(i1, k-1, Math.min(min, (j-1?Integer.MAX_VALUE:Math.abs(nums[i]-nums[j]))), i))%MOD;}map.put(key, res);return res;}
} 选或不选 class Solution {static final int MOD (int)1e97;int[] nums;int n;MapLong, Long map new HashMap();public int sumOfPowers(int[] nums, int k) {this.nums nums;Arrays.sort(nums);this.n nums.length;long ans dfs(-1,k,Integer.MAX_VALUE, -1);return (int)ans%MOD;}//选或不选long dfs(int i, int k, int min, int j){if(k 0)return min;if(k n - i - 1)return 0;long res 0;long key ((long)min18|i12|k6|(j1));if(map.containsKey(key)) return map.get(key);//选nums[i1]res dfs(i1, k-1, Math.min(min, (j-1?Integer.MAX_VALUE:Math.abs(nums[i1]-nums[j]))), i1);//不选nums[i1]res dfs(i1, k, min, j);map.put(key, res%MOD);return res%MOD;}
}
