跳到主要内容

14 篇博文 含有标签「位运算」

查看所有标签

· 阅读需 4 分钟

1、题干​

给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [0]
输出：0

示例 3：

输入：nums = [2,4]
输出：6

示例 4：

输入：nums = [8,10,2]
输出：10

示例 5：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

 

提示：

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

 

进阶：你可以在 O(n) 的时间解决这个问题吗？

 

注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

题目比较难，没能想到官解那些优秀解法，尝试了暴力解法并两次剪枝优化后，不仅AC还超过82%提交

2、解题思路​

解题关键是：最大异或结果一定是由 二进制位数最多的一个数 与 另一个数 进行异或运算得来。 以 [3,10,5,25,2,8] 为例，用二进制表示是：[11, 1010, 101, 11001, 10, 1000]，其中 二进制位数最多 的只有1个数 25(11001)，接着计算 25 跟其他数的异或结果并取最大值即可。


暴力解法步骤 ：

  • 先对数组进行降序排序
  • 对所有数进行异或运算并取最大值

剪枝优化：

  • 优化1：异或结果的最大可能是：二进制位数最多的数异或之后所有二进制位变成 1，假设为 MAX_NUM。如果运算结果已达到最大可能 MAX_NUM，则直接退出程序。（效果显著）
  • 优化2：异或运算时，第一个数取 二进制位数最多的数 ，第二个数取 二进制位数更少的数 。第一个数不变的情况下，第二个数的二进制位数与其相同则异或会导致最高位变为 0，结果必然小于第二个数的二进制位数更少的情况。

3、代码​

// 优化1
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    let idx = nums.findIndex((n) => n < 1 << c);
    if (idx < 0) idx = nums.length;

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    for (let i = 0; i < idx; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            res = Math.max(res, nums[i] ^ nums[j]);
            if (res === MAX_NUM) return res;
        }
    }

    return res;
};

// 优化1 + 优化2
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    const idx = nums.findIndex((n) => n < 1 << c);

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    if (idx > -1) {
        for (let i = 0; i < idx; i++) {
            for (let j = idx; j < nums.length; j++) {
                res = Math.max(res, nums[i] ^ nums[j]);
                if (res === MAX_NUM) return res;
            }
        }
    } else {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) res = Math.max(res, nums[i] ^ nums[j]);
        }
    }

    return res;
};

4、复杂度​

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

 

提示：

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

 

注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

题目比较难，没能想到官解那些优秀解法，尝试了暴力解法并两次剪枝优化后，不仅AC还超过82%提交

2、解题思路​

解题关键是：最大异或结果一定是由 二进制位数最多的一个数 与 另一个数 进行异或运算得来。 以 [3,10,5,25,2,8] 为例，用二进制表示是：[11, 1010, 101, 11001, 10, 1000]，其中 二进制位数最多 的只有1个数 25(11001)，接着计算 25 跟其他数的异或结果并取最大值即可。


暴力解法步骤 ：

  • 先对数组进行降序排序
  • 对所有数进行异或运算并取最大值

剪枝优化：

  • 优化1：异或结果的最大可能是：二进制位数最多的数异或之后所有二进制位变成 1，假设为 MAX_NUM。如果运算结果已达到最大可能 MAX_NUM，则直接退出程序。（效果显著）
  • 优化2：异或运算时，第一个数取 二进制位数最多的数 ，第二个数取 二进制位数更少的数 。第一个数不变的情况下，第二个数的二进制位数与其相同则异或会导致最高位变为 0，结果必然小于第二个数的二进制位数更少的情况。

3、代码​

// 优化1
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    let idx = nums.findIndex((n) => n < 1 << c);
    if (idx < 0) idx = nums.length;

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    for (let i = 0; i < idx; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            res = Math.max(res, nums[i] ^ nums[j]);
            if (res === MAX_NUM) return res;
        }
    }

    return res;
};

// 优化1 + 优化2
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    const idx = nums.findIndex((n) => n < 1 << c);

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    if (idx > -1) {
        for (let i = 0; i < idx; i++) {
            for (let j = idx; j < nums.length; j++) {
                res = Math.max(res, nums[i] ^ nums[j]);
                if (res === MAX_NUM) return res;
            }
        }
    } else {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) res = Math.max(res, nums[i] ^ nums[j]);
        }
    }

    return res;
};

4、复杂度​

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
  • 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ，且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

 

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

 

提示：

  • 1 <= n <= 16

格雷编码的生成方式有3种，直接计算、镜像对称构造、交替构造；可惜我一个都没推出来，这里做个简单记录。

2、直接计算​

直接计算的公式是：G(n)=n⊕n2G(n) = n \oplus \dfrac{n}{2}。其中 G(n)G(n) 表示第 nn 个格雷码。

该解法对应官解2

3、代码​

var grayCode = function(n) {
    const ret = [];
    for (let i = 0; i < 1 << n; i++) {
        ret.push((i >> 1) ^ i);
    }
    return ret;
};

4、镜像对称构造​

  • 将前2k个格雷码去除首位二进制数并分成两半后具有镜像对称性。（如下图3位格雷码）
  • n位格雷码是将n-1位格雷码作为前半部分，将n-1位格雷码倒序遍历并在其二进制数之前添1作为后半部分。（如下图3位格雷码与2位格雷码关系）

image.png

该解法对应官解1

5、代码​

var grayCode = function (n) {
    const arr = [0, 1];
    for (let i = 2; i <= n; i++) {
        for (let j = arr.length - 1; j > -1; j--) {
            arr.push(arr[j] | (1 << (i - 1)));
        }
    }
    return arr;
};

6、交替构造​

以3位格雷码为例：

  • 从 n = 0 开始，按以下2步反复操作，即可得到所有格雷码
  • n 为偶数：翻转最低位得到下一个格雷码，如 000 变成 001
  • n 为奇数：把最右边的 1 左边的位翻转得到下一个格雷码，如 001 变成 011

实现略复杂，暂无代码，建议优先使用前2种方法生成

· 阅读需 5 分钟

1、题干​

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

 

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

 

提示：

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words[i] 仅包含小写字母

思路​

  • 暴力解法：

    • 暴力解法是做个嵌套循环遍历所有words，判断两个word是否有相同字母需要再遍历word中的字符
    • 按暴力解法估算时间复杂度大概是O(n^3)，n取1000的话，超时基本没跑了
    • 实际上2层嵌套循环基本无法避免，也就是说时间复杂度至少是O(n^2)，那就想办法再减少一层遍历

  • 第1层优化-字典：

    • 题目中说到 每个单词只包含小写字母，通常会想到把单词转换成以字母为key的哈希表或者数组字典来做优化
    • 根据题意，使用数组表示单词时，只要将字母对应ASCII码顺序作为索引，值为bool类型即可
    • 举个例子，单词abc可以表示为[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1]，单词a可以表示为[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
    • 判断两个单词是否包含相同字母需要做一次遍历，由于数组长度恒定为26，因此时间复杂度为常数
    • 至此，时间复杂度已经可以达到O(n^2)

  • 第2层优化-位运算：

    • 实际上，如果用二进制整数来表示单词会更简洁 abc可以表示为0b111，a可以表示为0b1
    • 而且判断两个单词是否有相同字母只需要做一次&运算而不需要遍历数组，&运算结果为0则表示没有相同字母
    • 这个优化不能减少时间复杂度，但是可以减少执行时间

  • 解题步骤：

    • 1、遍历words，将words中的单词转换为长度为2的数组[bit,word.length]，数组两个元素分别表示单词的二进制和单词的长度
    • 2、再次遍历words，把当前单词与剩余单词做匹配，如果不存在相同单词，则计算长度乘积
    • 3、返回长度乘积的最大值，具体代码如下

  • 进一步优化：

    • 题解中说到单词转成二进制之后可能会相等，因此可以用哈希表做进一步优化（答题的时候没想到，另外考虑到单词组合问题，26个字母组成1000个单词，最坏情况下转成二进制之后可能没有相等的情况，因此就不写了）
    • 答题的时候发现运算次数达到一定量级之后，位运算的速度比乘方运算更快些（属于自己挖坑了，这里耗时差距能达到10+倍，具体参考附录）

代码​

var maxProduct = function (words) {
    const CODEA = 'a'.charCodeAt(0);
    for (let i = 0; i < words.length; i++) {
        let bit = 0;
        for (let j = 0; j < words[i].length; j++) {
            const p = words[i].charCodeAt(j) - CODEA;
            bit = bit | (1 << p);
        }
        words[i] = [bit, words[i].length];
    }

    let res = 0;
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            if ((words[i][0] & words[j][0]) === 0) {
                res = Math.max(res, words[i][1] * words[j][1]);
            }
        }
    }

    return res;
};

附录​

const K = 1e6;
const MOD = 10;

console.time('乘方');
let n = 0;
for (let i = 0; i < K; i++) {
  n = n | (2 ** (i % MOD));
}
console.timeEnd('乘方');

console.time('位运算');
n = 0;
for (let i = 0; i < K; i++) {
  n = n | (1 << (i % MOD));
}
console.timeEnd('位运算');
// 浏览器下执行结果
// 乘方: 78.853759765625 ms
// 位运算: 6.093994140625 ms