目录
一，3095. 或值至少 K 的最短子数组 I
本题需要知道一个知识点，0|0 = 0，0|1 = 1，1|1 = 1，根据上述性质可以得出，每按位或一个数，这个数要么变大，要么不变，也就是说它有一个非递减的性质。在者，这道题的数据范围不大，可以直接暴力，代码如下：
class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
int n = nums.length;
int ans = Integer.MAX_VALUE;
for(int i=0; i<n; i++){
int or = 0;
for(int j=i; j<n; j++){
or |= nums[j];
if(or >= k){
ans = Math.min(ans, j-i+1);
break;
}
}
}
return ans==Integer.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 += x==0?-1:1;
int n = possible.length;
int pre = 0;
for(int i=0; i<n; i++){
if(i>0 && pre > sum - pre)
return i;
pre += possible[i]==0?-1:1;
}
return -1;
}
}三，3097. 或值至少为 K 的最短子数组 II
本题和第一题相同，但是数据范围更大，无法使用暴力，但是结论可以使用：一个数按位或的越多，那么就会变大或不变
方法一：滑动窗口
使用一个大小为32的数组来统计32个比特位各出现了几次
- 每遍历到一个数，遍历它的32个bit位，如果cnt[i]==0 && (x>>i)&1==1时，说明当前数字按位或后，这个bit位会从0变成1，所以 k -= 1<<i
- 当 k <= 0 时，说明当前按位与的数已经大于k了，就可以更新ans，同时可以缩减[l,r]的范围，看看当l变大时，是否满足k<=0，注意删除nums[l]时，遍历它的32个bit位，如果cnt[i]==1 && ((nums[l]>>i)&1)==1，说明删除这个数后，按位或的这个数会减小，所以 k += 1<<i
- 注意当 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 l=0,r=0; r<n; r++){
int x = nums[r];
for(int i=0; i<32; i++){
if(cnt[i]==0 && ((x>>i)&1)==1)//按位或之后，这个bit位会从0变成1
k -= 1<<i;
cnt[i] += (x>>i)&1;
}
while(k <= 0){
ans = Math.min(ans, r-l+1);//跟新答案
int y = nums[l];
for(int i=0; i<32; i++){
if(cnt[i]==1 && ((y>>i)&1)==1)//丢掉y之后,这个bit位是否会从1变成0
k += 1<<i;
cnt[i] -= (y>>i)&1;
}
l++;
}
}
return ans==Integer.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 i=0; i<n; i++){
or[m][0] = 0;
or[m++][1] = i;
//更新操作
int j = 0;
for(int idx=0; 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 = j+1;
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}四，3098. 求出所有子序列的能量和
本题是一道单纯的dfs+记忆化题，有两种做法：
- 枚举选哪个
- 选或不选
枚举选哪个：
class Solution {
static final int MOD = (int)1e9+7;
int[] nums;
int n;
Map<Long, 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)min<<18|idx<<12|k<<6|(j+1));
if(map.containsKey(key)) return map.get(key);
for(int i=idx; i<=n-k; i++){
res = (res + dfs(i+1, 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)1e9+7;
int[] nums;
int n;
Map<Long, 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)min<<18|i<<12|k<<6|(j+1));
if(map.containsKey(key)) return map.get(key);
//选nums[i+1]
res = dfs(i+1, k-1, Math.min(min, (j==-1?Integer.MAX_VALUE:Math.abs(nums[i+1]-nums[j]))), i+1);
//不选nums[i+1]
res += dfs(i+1, k, min, j);
map.put(key, res%MOD);
return res%MOD;
}
}
