LeetCode 75| 位运算

目录

338 比特位计数

136 只出现一次的数字

?1318 或运算的最小翻转次数

338 比特位计数

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int>res(n + 1);
        for(int i = 0;i <= n;i++)res[i] = cal(i);
        return res;
    }
    int cal(int num){
        int res = 0;
        for(int i = 0;i < 32;i++)res += (num >> i) & 1;
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(n)

136 只出现一次的数字

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

时间复杂度O(n)

空间复杂度O(1)

?1318 或运算的最小翻转次数

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int res = 0;
        while(a || b || c){
            if(c & 1){
                if((a & 1) == 0 && (b & 1) == 0)res++;
            }else{
                if(a & 1)res++;
                if(b & 1)res++;
            }
            a>>=1;
            b>>=1;
            c>>=1;
        }
        return res;
    }
};

时间复杂度O(n)//n为a,b,c 的最大二进制位数

空间复杂度O(1)