logTrick

题目

3171. 找到按位或最接近 K 的子数组 - 力扣（LeetCode）

3097. 或值至少为 K 的最短子数组 II - 力扣（LeetCode）

方法

logTrick的核心思路即对于元素U，进行或操作/与操作的其中一种，最多只能增大/减小logU次。

遇到涉及子数组或运算/与运算的题目时，可以考虑采用logTrick思想进行优化。步骤如下：

1. 定义数组nums和数组ops，其中nums为原始输入，当前遍历到的数组下标为ptr，则ops[i]表示nums[i:ptr-1]这段区间的所有元素的位运算结果；

2. 容易发现对于或运算，ops数组中的右侧元素为左侧元素的子集；对于与运算，ops数组中左侧元素为右侧元素的子集；

3. 在对当前元素nums[ptr]操作时，可以从ptr-1开始倒序枚举下标j：

   • 对于或运算，当发现nums[ptr]是ops[j]的子集时，说明nums[ptr]也是ops[:j-1]的子集；
   • 对于与运算，当发现ops[j]是nums[ptr]的子集时，说明ops[:j-1]也都是nums[ptr]的子集；

   继续枚举并不会导致ops[j]的变化，因此可以停止枚举；

4. 由于ops数组的每个元素最多只会增大/减小logU次，因此总的时间复杂度为O(nlogn)

实际情况中，可以原地维护ops数组，进一步优化空间。

代码

或操作

1
2
3
4
5
6
7
8
9
10
11

int n = nums.length;
int[] ors = new int[n];
for(int i = 0;i < n;++i){
    int num = nums[i];
    ors[i] = nums[i];
    // 得到了一个长度为1的子数组的或运算值ors[i]
    for(int j = i-1;j >= 0 && (ors[j] | num) != ors[j];--j){
        ors[j] |= num;
        // 得到了一个长度大于1的子数组的或运算值ors[j]
    }
}

或操作（原地修改）

1
2
3
4
5
6
7
8

for (int i = 0; i < nums.length; i++) {
    int x = nums[i];
    // 得到了一个长度为1的子数组的或运算值 nums[i]
    for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
        nums[j] |= x;
        // 得到了一个长度大于1的子数组的或运算值nums[j]
    }
}

__END__