LeetCode——位运算

程序员文章站 2022-06-07 10:28:50

...

LeetCode——位运算

1、统计两个数的二进制表示有多少位不同
T461 Hamming Distance (Easy)
LeetCode——位运算

class Solution {
public:
    int hammingDistance(int x, int y) {
        int res=0;
        for(int i=0; i<32; ++i){
            if(x & (1<<i) ^ y & (1<<i)){
                ++res;
            }
            
        }
        return res;

    }
};

2、数组中唯一一个不重复的元素
T136. Single Number (Easy)
LeetCode——位运算

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> st;
        for(int num : nums){
            if(st.count(num))  st.erase(num);
            else st.insert(num);
        }
        return *st.begin();

    }
};

3、找出数组中缺失的那个数
T268. Missing Number (Easy)
LeetCode——位运算

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res=0;
        for(int i=0; i<nums.size(); ++i){
            res ^= (i+1) ^nums[i];
        }
        return res;

    }
};

4、数组中不重复的两个元素
T260. Single Number III (Medium)
LeetCode——位运算

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sum = 0;
        for(int num : nums){
            sum ^= num;
        }

        int lowbit = sum & (-sum);
        vector<int> res{0, 0};
        for(int num : nums){
            if(num & lowbit) res[0] ^= num;
            else  res[1] ^= num;
        }
        return res;

    }
};

5、翻转一个数的比特位
T190. Reverse Bits (Easy)
LeetCode——位运算

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

6、不用额外变量交换两个整数
程序员代码面试指南：P317

7、判断一个数是不是 2 的 n 次方
T231. Power of Two (Easy)
LeetCode——位运算

class Solution {
public:
    bool isPowerOfTwo(int n) {
        int cnt = 0;
        while(n > 0){
            cnt += (n&1);
            n >>= 1;
        }
        return cnt == 1;

    }
};

8、判断一个数是不是 4 的 n 次方
T342. Power of Four (Easy)
LeetCode——位运算

class Solution {
public:
    bool isPowerOfFour(int num) {
        while(num && (num % 4 == 0)){
            num /= 4;
        }
        return num == 1;

    }
};

9、判断一个数的位级表示是否不会出现连续的 0 和 1
T693. Binary Number with Alternating Bits (Easy)
LeetCode——位运算

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int bit = -1;
        while(n > 0){
            if(n & 1 == 1){
                if(bit == 1)  return false;
                bit = 1;
            }else{
                if(bit == 0) return false;
                bit = 0;
            }
            n >>= 1;
        }
        return true;

    }
};

10、求一个数的补码
T476. Number Complement (Easy)
LeetCode——位运算

class Solution {
public:
    int findComplement(int num) {
        bool start = false;
        for(int i=31; i>=0; --i){
            if(num & (1 << i)) start = true;
            if(start)  num ^= (1<<i);
        }
        return num;

    }
};

11、实现整数的加法
T371. Sum of Two Integers (Easy)
LeetCode——位运算

class Solution {
public:
    int getSum(int a, int b) {
        if(b==0) return a;
        int sum = a ^ b;
        int carry = (a & b & 0x7fffffff) << 1;
        return getSum(sum, carry);

    }
};

12、字符串数组最大乘积
T318. Maximum Product of Word Lengths (Medium)
LeetCode——位运算

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int res = 0;
        vector<int> mask(words.size(), 0);
        for(int i=0; i<words.size(); ++i){
            for(char c : words[i]){
                mask[i] |= 1 << (c - 'a');
            }
            for(int j=0; j<i; ++j){
                if(!(mask[i] & mask[j])){
                    res = max(res, int(words[i].size() * words[j].size()));
                }
            }
        }
        return res;

    }
};

13、统计从 0 ~ n 每个数的二进制表示中 1 的个数
T338. Counting Bits (Medium)
LeetCode——位运算

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res{0};
        for(int i=1; i<=num; ++i){
            if(i % 2 == 0) res.push_back(res[i/2]);
            else res.push_back(res[i/2]+1);
        }
        return res;

    }
};

LeetCode——位运算