Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.1k 阅读时长 ≈ 2 分钟
logtrick经典题目。先处理出单调序列，然后再二分。

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

题目描述：

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

数据范围：

$1\le nums.len \le 10^5, 0 \le nums[i],k \le 10^9$

题解：

按照 logtrick 可以快速处理出所有以 $nums[i]$ 为终点的区间位运算和。而且此时 $nums[i]$ 左侧的全是他的子集。因此可以直接找出所有与 $k$ 相等的，这里可以用二分，因为最后得到的数组是升序的。

也可以找出与 $k$ 最接近的，这时就需要使用二分找到 $\ge k$ 的位置，然后使用他和他前面的数字更新最优解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static long long mod = 1e9 + 7;
    const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
    const int INF = 0x3f3f3f3f;
    long long countSubarrays(vector<int> &nums, int k)
    {
        // a1 & a2 & a3, a2 & a3, a3, a4
        int n = nums.size();
        long long ans = 0;
        //  vector<int> a = {1, 9, 9, 7, 4};
        for (int i = 0; i < n; ++i)
        {
            if(nums[i] == k) ans++;
            int j;
            for (j = i - 1; j >= 0; --j)
            {
                if ((nums[j] & nums[i]) == nums[j])
                {
                    break;
                }
                nums[j] &= nums[i];
            }
            // nums[j] 是 nums[i] 的子集。nums[k], k \in [0, j] 是 nums[i] 的子集
            int cnt = upper_bound(nums.begin(), nums.begin() + i, k) - lower_bound(nums.begin(), nums.begin() + i, k);
            ans += cnt;
        }
        return ans;
    }
};

找出最接近的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static long long mod = 1e9 + 7;
    const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
    const int INF = 0x3f3f3f3f;
    int minimumDifference(vector<int> &nums, int k)
    {
        int n = nums.size();
        int ans = INT_MAX;
        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];
            }
            // 找到大于等于 k 的。
            int l = 0, r = i;
            int index = -1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if(nums[mid] >= k) {
                    index = mid;
                    l = mid + 1;
                }else r = mid - 1;
            }
            if(index == -1) {
                ans = min(ans, abs(nums[0] - k));
            } else {
                ans = min(ans, abs(nums[index] - k));
                if(index + 1 <= i) {
                    ans = min(ans, abs(nums[index + 1] - k));
                }
            }
        }
        return ans;
    }
};