Leetcode 刷题笔记-Leetcode 101 第10章 位运算

Leetcode 刷题笔记-Leetcode 101 第10章 位运算

位运算

常用技巧

按位异或：x ^ 0s = x, x ^ 1s = ~x, x ^ x = 0

按位与：x & 0s = 0, x & 1s = x, x & x = x

按位或：x | 0s = x, x | 1s = 1s, x | x = x

n & (n - 1)可以去除 n的位级表示中最低的那一位，例如对于二进制表示 11110100，减去 1得到 11110011，这两个数按位与得到 11110000。

n & (-n)可以得到n的位级表示中最低的那一位，例如对于二进制表示 11110100，取负得到 00001100，这两个数按位与得到 00000100。

位运算基础问题

Leetcode 461

给定两个十进制数字，求它们二进制表示的汉明距离（Hamming distance，即不同位的个数）。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int diff = x ^ y;
        int ans = 0;
        while(diff){
            ans += diff & 1;
            diff >>= 1;
        }
        return ans;
    }
};

分析：将x和y按位异或，则不同的位置为1，相同的位置为0。然后将得到的结果与1进行与操作，为0说明是0，为1说明是1，就计数了1。然后将这个结果逐步右移就可以看出下一位了。

错误：第一道题不太熟悉。

Leetcode 190

颠倒给定的 32 位无符号整数的二进制位

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i=0;i<32;++i){
            ans <<= 1;
            ans += n & 1;
            n >>= 1;
        }
        return ans;
    }
};

分析：摆出一个0，然后左移，逐步加上n右移的数字。

错误：不太明白左右移这种东西

Leetcode 136

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;
        return ret;
    }
};

分析：一个数字和 0进行按位异或会得到本身，一个数字和本身进行按位异或会得到0。因此在数组内部进行循环，两次的元素出现了一定会变为0，最后剩下的一个就是这个数字本身。

错误：不熟练

二进制特性

Leetcode 342

给定一个整数，判断它是否是4 的次方。

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && !(n & (n - 1)) && (n & 1431655765);
    }
};

分析：首先我们考虑一个数字是不是2 的（整数）次方：如果一个数字n 是2 的整数次方，那么它的二进制一定是0…010…0 这样的形式；考虑到n - 1 的二进制是0…001…1，这两个数求按位与的结果一定是0。因此如果n & (n - 1) 为0，那么这个数是2 的次方。如果这个数也是4 的次方，那二进制表示中1 的位置必须为奇数位。我们可以把n 和二进制的10101…101（即十进制下的1431655765）做按位与，如果结果不为0，那么说明这个数是4的次方。

错误：不理解

Leetcode 318

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

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> hash;
        int ans = 0;
        for (const string & word : words) {
            int mask = 0, size = word.size();
            for (const char & c : word) {
                mask |= 1 << (c - 'a');
            }
            hash[mask] = max(hash[mask], size);
            for (const auto& [h_mask, h_len]: hash) {
                if (!(mask & h_mask)) {
                    ans = max(ans, size * h_len);
                }
            }
        }
        return ans;
    }
};

分析：怎样快速判断两个字母串是否含有重复数字呢？可以为每个字母串建立一个长度为26的二进制数字，每个位置表示是否存在该字母。如果两个字母串含有重复数字，那它们的二进制表示的按位与不为0。

错误：看了思路后自己实现的。

Leetcode 338

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n+1,0);
        for (int i = 1; i <= num; ++i){
            dp[i] = i & 1? dp[i-1] + 1: dp[i>>1];
        }
        return ans;
    }
};

分析：本题可以利用动态规划和位运算进行快速的求解。定义一个数组dp，其中dp[i] 表示数字i的二进制含有1 的个数。对于第i 个数字，如果它二进制的最后一位为1，那么它含有1 的个数
则为dp[i-1] + 1；如果它二进制的最后一位为0，那么它含有1 的个数和其算术右移结果相同，即dp[i>>1]。

练习

Leetcode 268

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }
};

分析：高斯求和后相减即可

Leetcode 693

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int pre = 0;
        int sign = 0;
        while(n){
            int ans = n & 1;
            if(sign == 1){
                if(pre == ans){
                    return false;
                }
            }
            pre = ans;
            sign = 1;
            n >>= 1;
        }
        return true;
    }
};

分析：存储并判断即可

错误：有一点小问题，很快调通

Leetcode 476

给你一个整数 num ，输出它的补数。

class Solution {
public:
    int findComplement(int num) {
        uint t = 1u << 31;
        while (! (t & num)) {
            num |= t;
            t >>= 1;
        }
        return ~num;
    }
};

分析：前边补1，然后就可以直接取反了

错误：没有思路

Leetcode 260

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        map<int,int> mp;
        for(int i=0;i<nums.size();++i){
            ++mp[nums[i]];
        }
        vector<int> result;
        for(const auto &[a,b] : mp){
            if(b == 1){
                result.push_back(a);
            }
        }
        return result;
    }
};

分析：哈希表算了。。。

一遍AC

总结

这东西和计组挺相关的，面试中应该不会怎么考察这种数学题，但不失为一种运算加速的好办法。