leetcode134双周赛 子数组按位与值为 K 的数目「动态规划」「位运算」

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

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个子数组满足：子数组中所有元素按位 AND 的结果为 k

思路1:动态规划

打力扣打PTSD了，看什么题都是DP

状态：$dp[i][j]$表示以$num[i]$结尾，二进制第$j$位连续是1的最长长度

状态转移：

• 如果$nums[i]$的第$j$是1，则$dp[i][j]=dp[i-1][j]+1$
• 否则，$dp[i][j]=0$

有了状态以后，怎么计算答案？

我们可以枚举子数组的右边界 $i$ ，然后想办法去计算左边界的一个上界和下界

• 如果$k$的第$j$位是1，根据&运算的性质，则满足条件的子数组的每个数的第$j$位都应该是1。所以我们对k的每一个是1的位，求对应$dp[i][j]$的最小值，计作minx，求最小值的原因是，我们要求出满足这个子区间所有k是1的位都是1的最短长度，这是上界，不能再往前找了，因为只要再往前一位，一定存在一位本该是1的位置&上了0，变成了0，使得区间&起来不是k
• 如果k的第$j$位是0，根据&运算的性质，则满足条件的子数组的第$j$位应该至少有一个0，所以我们对k的每一个是0的位，求对应$dp[i][j]$的最大值，计作maxn，求最大值的原因是，$dp[i][j]$代表第$nums[i]$的第$j$位往前连续的1的最长长度，我们现在要保证有一个0，则往前的第一个0是位于往前$dp[i][j]+1$的位置，这是下界，是可以再往前找的，因为前面不管是什么，我们是0的位置&起来都是0
• 所以答案就是 $max(0,minx-maxn)$

对于每个右边界$i$,我们都算出$maxn$和$minx$，求个 $\sum max(0,minx-main)$就行

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>>dp(n + 1, vector<int>(32));
        long long ans = 0;
        for(int i = 1; i <= nums.size(); ++i){
            for(int j = 0; j < 32; ++j){
                if((nums[i - 1]>>j) & 1)dp[i][j] = dp[i - 1][j] + 1;
                else dp[i][j] = 0;
            }
            int minx = i, maxn = 0;
            for(int j = 0; j < 32; ++j){
                if((k>>j)&1)minx = min(minx, dp[i][j]);
                else maxn = max(maxn, dp[i][j]);
            }
            cout<< minx << " " << maxn << endl;
            ans += max(0, minx - maxn);
        }
        return ans;
    }
};

思路2:位运算性质+二分

考虑一个简单问题，给定一个数组，如何求所有（子区间$num[i]$到$num[j]$进行与操作后起来）的结果

我们可以对数组进行如下操作：

• 我们搞一个$new\_num$数组，初始$new\_num[i]=num[i]$
• 然后$i$从1开始遍历到n，$j$从$i-1$遍历到1，每次都把$ne{w}_{n}um[i]$与前面所有的$num[j]$进行与操作，即$new\_num[j]=new\_num[j]\&num[i]$
• 这样操作会使得每次遍历完$i$，会使得$new\_num[j]$变成$num[j]\&num[j+1]\&...\&num[i]$
• 在这个过程中就可以得到所有的子区间数字相与的结果

但是如果仅仅是这样做，只会是标准的$O(n^2)$复杂度，我们可以想办法优化一下

由于&操作，一定会让数字变小或者不变，所以我们在第二层枚举的时候，可以判断一下如果$new\_num[j]==new\_num[j]\&num[i]$，说明
$$num[j]\&num[j+1]\&...\&num[i-1]==num[j]\&num[j+1]\&...\&num[i-1]\&num[i]$$
也就是说$\&$上$num[i]$不会使得$new\_num[j]$变小，那我们就可以停止第二层的循环了

我们可以将&操作看作集合的求交集操作，现在$new\_num[j]==new\_num[j]\&num[i]$说明$new\_num[j]$二进制是1的位置的集合一定是$num[i]$二进制是1的位置的集合的子集，而因为$new\_num[j-1]=new\_num[j]\&num[j-1]$，则$new\_num[j-1]<=new\_num[j]$，$new\_num[j-1]$二进制是1的位置的集合一定是$new\_num[j]$二进制是1的位置的集合的子集，则集合的大小关系是$new\_num[j-1]\subseteq new\_num[j]\subseteq num[i]$

那这样$new\_num[j-1]$&上$num[i]$也一定不变，当然，不是说只有$j-1$不用&了，小于$j-1$的也不用&了，证明同上

可以发现，如果想让数字变小，一定是至少有一位二进制位从1变成0，由于本题二进制下1最多30位，所以最坏的时间也就是$O(n\ast log(ma{x}_{e}lement))$

现在回到本题，本题求的是子区间&起来等于k的数量，我们只需要在循环$i$的时候，统计一下$1$到$i$中$num[i]=k$的数量，求和就行，$num[i]$中数字都是连续出现且递增的，所以我们可以用二分来找

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        long long ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = i - 1; j >= 0; --j){
                if((nums[j] & nums[i]) == nums[j]){
                    break;
                }
                nums[j] &= nums[i];
            }
            int l = lower_bound(nums.begin(), nums.begin() + i + 1, k) - nums.begin();
            int r = upper_bound(nums.begin(), nums.begin() + i + 1, k) - nums.begin();
            ans += r - l;
        }
        return ans;
    }
};