【算法-位运算】位运算遍历 LogTick 算法

1. 引入

最近刷题做到了位运算的题目，不得不感叹有时候这些题目写法简单是真的简单，但是思路也是真的难想，下面就来看下最新学到的一个算法 LogTick，这个算法是专门用于子数组求 or 或者 and 这些集合交集并集用的。

LogTick 可以用于计算连续子数组的 or 值，比如给定一个数组 [0 … L … R … len - 1]，需要求出这个数组中任意一个 [L … R] 这个范围数组的 or 值，如何求呢？

最简单的方法是暴力，直接遍历，下面是遍历的双重 for 循环框架。

for(int i = 0; i < len; i++){
    for(int j = i - 1; j >= 0; j--){
        ...
    }
}

这遍历的逻辑可以用下面例子直观解释：

• 当 i = 0 的时候，不处理
• 当 i = 1 的时候，会设置 nums[0] |= nums[1]，这样就能求出 [0, 1] 的子数组或
• 当 i = 2 的时候，从后往前遍历设置 nums[1] |= nums[2]，nums[0] |= nums[1]，这样就能求出 [1, 2]、[0, 2] 的子数组或
• 当 i = 3 的时候，从后往前遍历设置 nums[2] |= nums[3], nums[1] |= nums[2]，nums[0] |= nums[1]，这样就能求出 [2, 3]、[1, 3]、[0, 3] 的子数组或运算
• …

那么完整的写法是：

public int minimumDifference(int[] nums, int k) {
    for(int i = 0; i < nums.length; i++){
        int x = nums[i];
        for(int j = i - 1; j >= 0; j --){
            nums[j] |= x;
        }
    }
}

其实这里代码实现和上面例子解释的实现不太一样，上面例子解释是从后往前一直往前 or，但是给出的实现是只对 x 进行 or，其实是一样的，因为

• 当 i = 0，不处理
• 当 i = 1，nums[0] |= nums[1]
• 当 i = 2，nums[1] |= nums[2]，nums[0] |= nums[2] 等同于 nums[0] | nums[1] | nums[2]，因为在 i = 1 的时候就已经合并 nums[1] 到 nums[0] 了
• …

2. LogTick 优化遍历过程

上面的例子中时间复杂度是 O(logn)，这样一来如果数组长度是 10^5 次方就会超时，有没有什么办法优化时间复杂度呢？
对于二进制来说，a | b 其实就是把 a 和 b 二进制里面的 1 求并集，那么从并集的角度去看上面的流程：

• 当 i = 0 的时候，不处理
• 当 i = 1 的时候，会设置 nums[0] |= nums[1]，这样$nums[0]\supseteq nums[1]$，就是 nums[0] 集合里面包括 nums[1]
• 当 i = 2 的时候，会设置 nums[1] |= nums[2]，nums[0] |= nums[1]，这样 $nums[0]\supseteq nums[1],nums[1]\supseteq nums[2]=>nums[0]\supseteq nums[1]\supseteq nums[2]$

再把上面的代码贴下来方便观看。

public int minimumDifference(int[] nums, int k) {
    for(int i = 0; i < nums.length; i++){
        int x = nums[i];
        for(int j = i - 1; j >= 0; j --){
            nums[j] |= x;
        }
    }
}

这个代码就是暴力的代码，我们直接看内层循环，注意 nums[j] |= x 这行代码，这行代码的本意是将 x 合并到 nums[j] 中，那么仔细想想，假设第一次遍历的时候（j = i - 1），nums[j] | x = nums[j]，这时候还需要 j – 再往前遍历吗？

其实是不需要的，因为 $nums[0]\supseteq nums[1]\supseteq nums[2]$，我们现在假设 x = nums[3]，那么对于 j 从 i - 1 就是 2 开始往前遍历，如果 nums[2] | nums[3] == nums[2]，那么说明 nums[3] 就是 nums[2] 的一个子集，这样的话 nums[3] 自然就是 nums[1] 的子集，这种情况下根本没必要继续向前遍历执行 nums[j] |= x，从而我们就能直接跳过 2 次遍历了。

那么上面解释之后我们就能写出最终代码了，也就是 LogTick 的代码：

public int minimumDifference(int[] nums, int k) {
    for(int i = 0; i < nums.length; i++){
        int x = nums[i];
        for(int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j --){
            nums[j] |= x;
        }
    }
}

其实相比暴力的解法就是判断条件多了一个 nums[j] | x != nums[j]。

3. 题目

以下题目都来自灵神的题单，分享丨【题单】位运算（基础/性质/拆位/试填/恒等式/思维）

3.1 LeetCode3097 或值至少为 K 的最短子数组 II

3097 或值至少为 K 的最短子数组 II

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

输入： nums = [1,2,3], k = 2
输出： 1
解释： 子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：

输入： nums = [2,1,8], k = 10
输出： 3
解释： 子数组 [2,1,8] 的按位 OR 值为 11，所以我们返回 3 。

示例 3：

输入： nums = [1,2], k = 0
输出： 1
解释： 子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

提示：

• 1 <= nums.length <= $2\ast 10^5$
• 0 <= nums[i] <= $10^9$
• 0 <= k <= $10^9$

思路：

找到最短的子数组，所以没什么好说的，直接用 LogTick 算法找最短子数组即可，为什么可以用 LogTick 呢？因为如果 nums[j] | nums[i] = nums[j]，此时 nums[j] >= x，那么对于 j 前面的下标肯定也是 >= x 的，因为 $nums[0]\supseteq nums[1]...\supseteq nums[j-1]\supseteq nums[j]$。

所以这时候就没必要继续往前遍历了，下面看代码。

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

3.2 LeetCode2411 按位或最大的最小子数组长度

按位或最大的最小子数组长度

给你一个长度为 n 下标从 0 开始的数组 nums，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。

• 换言之，令 $B_{ij}$ 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 $max(B_{ij})$ ，其中 i <= k <= n - 1。

一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i] 是开始位置为 i，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

示例 1：

输入： nums = [1,0,2,1,3]
输出： [3,3,2,2,1]
解释： 任何位置开始，最大按位或运算的结果都是 3 。

• 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
• 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
• 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
• 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
• 下标 4 处，能得到结果 3 的最短子数组是 [3] 。

所以我们返回 [3,3,2,2,1] 。

示例 2：

输入： nums = [1,2]
输出： [2,1]
解释：

• 下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
• 下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。

所以我们返回 [2,1] 。

示例 3：

输入： nums = [1,2], k = 0
输出： 1
解释： 子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

提示：

• n == nums.length
• 1 <= n <= $10^5$
• 0 <= nums[i] <= $10^9$

class Solution {
     public int[] smallestSubarrays(int[] nums) {
        // 从右向左的 logTick
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = 1;
            for (int j = i - 1; j >= 0 && (nums[j] | nums[i]) != nums[j]; j--) {
                nums[j] |= nums[i];
                res[j] = i - j + 1;
            }
        }
        return res;
    }
}

3.3 LeetCode3209 子数组按位与值为 K 的数目

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

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

示例 1：

输入： nums = [1,1,1], k = 1
输出： 6
解释： 所有子数组都只含有元素 1 。

示例 2：

输入： nums = [1,1,2], k = 1
输出： 3
解释： 按位 AND 值为 1 的子数组包括：[1], [1], [1,1] 。

示例 3：

输入： nums = [1,2,3], k = 2
输出： 2
解释： 按位 AND 值为 2 的子数组包括：[2], [2,3] 。

思路：

其他几道题目都是使用 LogTick 来计算或运算，但是 AND 运算也是一样的，来看下下面的遍历过程：

1. 当 i = 0 的时候，不处理
2. 当 i = 1 的时候，nums[0] &= nums[1]，这时候 $nums[0]\subseteq nums[1]$
3. 当 i = 2 的时候，nums[1] &= nums[2]，nums[0] &= nums[1]，这时候 $nums[0]\subseteq nums[1]\subseteq nums[2]$
4. …

其实就是换个方向而已，从上面的关系可以看到，假设当 i = m 的时候，nums[m - 1] &= nums[i] 之后，nums[m - 1] < k，这时候还需要向前去找等于 k 的值吗？

不需要，因为 & 只会越 AND 越小。 根据这个特性，可以设置一个 left 和 right 指针，都指向 0，每一次遍历使用 left 指向第一个等于 k 的下标，right 指向第一个 > k 的下标，这样一来，right - left 就是等于 k 的数目。

假设当 i = m 的时候，left 指向 i1，right 指向 i2，所以这时候 nums[left] = k，i2 - i1 就是以 i = m 为结尾的子数组个数，而当 i = m + 1 的时候，由于 AND 越 AND 越小的特点，nums[left] & nums[i] 只会更小，left 要想找到等于 k 的下标，只能继续往右遍历，所以这就是 left 和 right 的单调性，依靠这个特点，我们就能写出下面代码。

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long res = 0;
        int left = 0, right = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i - 1; j >= 0 && (nums[i] & nums[j]) != nums[j]; j--) {
                nums[j] &= nums[i];
            }
            while(left <= i && nums[left] < k){
                left++;
            }
            while(right <= i && nums[right] <= k){
                right++;
            }
            // left 指向第一个 k，right 指向第一个 k + 1的值
            res += (right - left);
        }
        return res;
    }
}

上面的代码通过 left 和 right 求出等于 k 的个数，其实如果不用 left 和 right，也可以用二分法，主要就是使用二分法计算出等于 k 的左下标和右下标，但是使用二分就没有用到 left 的单调写法，时间复杂度会去到 O(nlogn)，这里二分写法如下：

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i - 1; j >= 0 && (nums[i] & nums[j]) != nums[j]; j--) {
                nums[j] &= nums[i];
            }
            int left = search(nums, 0, i, k);
            int right = search(nums, 0, i, k + 1);
            // left 指向第一个 k，right 指向第一个 k + 1的值
            res += (right - left);
        }
        return res;
    }

    public int search(int[] nums, int left, int right, int k){
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] >= k){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

3.4 LeetCode3171 找到按位或最接近 K 的子数组

找到按位或最接近 K 的子数组

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组 是数组中连续的 非空 元素序列。

示例 1：

输入： nums = [1,2,4,5], k = 3
输出： 0
解释： 子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：

输入： nums = [1,3,1,3], k = 2
输出： 1
解释： 子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

示例 3：

输入： nums = [1], k = 10
输出： 9
解释： 只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

提示：

• 1 <= nums.length <= $10^5$
• 1 <= nums[i] <= $10^9$
• 1 <= k <= $10^9$

思路：

LogTick 往前遍历，要求最小，那么如果 nums[j] | nums[i] = nums[j]，这时候 nums[j] - k 和 nums[j - 1] - k … nums[0] - k 是一样的，所以就没必要继续往前遍历了。

class Solution {
    // LogTick
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++){
            int x = nums[i];
            ans = Math.min(ans, Math.abs(x - k));
            for(int j = i - 1; j >= 0 && ((nums[j] | x) != nums[j]); j --){
                nums[j] |= x;
                ans = Math.min(ans, Math.abs(nums[j] - k));
            }
        }
        return ans;
    }
}

3.5 LeetCode1521 找到最接近目标值的函数值

找到最接近目标值的函数值

Winston 构造了一个如上所示的函数 func。他有一个整数数组 arr 和一个整数 target，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。

请你返回 |func(arr, l, r) - target| 的最小值。

请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length。

示例 1：

输入： arr = [9,12,3,7,15], target = 5
输出： 2
解释： 所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。

示例 2：

输入： arr = [1000000,1000000,1000000], target = 1
输出： 999999
解释： Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999。

示例 3：

输入： arr = [1,2,4,8,16], target = 0
输出： 0

提示：

• 1 <= arr.length <= $10^5$
• 1 <= arr[i] <= $10^6$
• 0 <= target <= $10^7$

思路：

通过 LogTick 去遍历子数组的 AND 运算结果，然后计算最小值。

class Solution {
    public int closestToTarget(int[] arr, int target) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min, Math.abs(arr[i] - target));
            for (int j = i - 1; j >= 0 && (arr[j] & arr[i]) != arr[j]; j--) {
                arr[j] &= arr[i];
                min = Math.min(min, Math.abs(arr[j] - target));
            }
        }
        return min;
    }
}

3.6 LeetCode898 子数组按位或操作

子数组按位或操作

给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。

子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。

子数组 是数组内连续的非空元素序列。

示例 1：

输入： arr = [0]
输出： 1
解释： 只有一个可能的结果 0 。

示例 2：

输入： arr = [1,1,2]
输出： 3
解释： 可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。产生的结果为 1，1，2，1，3，3。有三个唯一值，所以答案是 3 。

示例 3：

输入： arr = [1,2,4]
输出： 6
解释： 可能的结果是 1，2，3，4，6，以及 7。

提示：

• 1 <= arr.length <= $10^5$
• 1 <= arr[i] <= $10^6$
• 0 <= target <= $10^7$

代码：

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            int x = arr[i];
            set.add(x);
            for (int j = i - 1; j >= 0 && (arr[j] | x) != arr[j]; j--) {
                arr[j] |= x;
                set.add(arr[j]);
            }
        }
        return set.size();
    }
}

如有错误，欢迎指出！！！