leetcode算法之位运算

1.判断字符是否唯一

判断字符是否唯一

class Solution {
public:
    bool isUnique(string astr) {
        //利用鸽巢原理做优化
        if(astr.size()>26) return false;

        int bitMap = 0; //使用位图来存储
        for(auto ch:astr)
        {
            int i = ch-'a';
            if((bitMap>>i)&1 == 1) return false;
            bitMap |= (1<<i);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.丢失的数字

丢失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for(auto x:nums) ret^=x;
        for(int i=0;i<=nums.size();i++) ret^=i;
        return ret;
    }
};
1
2
3
4
5
6
7
8
9

3.两整数之和

两整数之和

class Solution {
public:
    int getSum(int a, int b) {

        while(b!=0)
        {
            int x = a^b;
            unsigned int carry = (unsigned int)(a&b)<<1;
            a = x;
            b = carry;
        }
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.只出现一次的数字II

只出现一次的数字II

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i=0;i<32;i++)
        {
            int sum = 0;
            for(auto x:nums)
            {
                if((x>>i)&1 == 1) sum++;
            }
            sum %=3;
            if(sum == 1)
            {
                ret |= (1<<i);
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5.消失的两个数字

消失的两个数字

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        //将所有的数异或在一起
        int tmp = 0;
        for(auto x:nums) tmp^=x;
        for(int i=1;i<=nums.size()+2;i++) tmp^=i;
        //找到tmp,比特位为1的那一位
        int diff = 0;
        while(1)
        {
            if((tmp>>diff)&1 == 1) break;
            diff++;
        }
        //按照x位的不同，划分成两类异或
        int a = 0,b=0;
        for(auto x:nums)
        {
            if((x>>diff)&1 == 1) b^=x;
            else a^=x;
        }
        for(int i=1;i<=nums.size()+2;i++)
        {
            if((i>>diff)&1 == 1) b^=i;
            else a^=i;
        }
        return {a,b};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

6.位1的个数

位1的个数

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        for(int i=0;i<32;i++)
        {
            if((n>>i)&1 == 1) sum++;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11

7.比特位计数

比特位计数

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ret;
        for(int i=0;i<=n;i++)
        {
            int sum = 0;
            for(int j=0;j<32;j++)
            {
                if((i>>j)&1 == 1) sum++;
            }
            ret.push_back(sum);
        }
        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8.汉明距离

汉明距离

class Solution {
public:
    int hammingDistance(int x, int y) {
        int sum = 0;
        int temp = x^y;
        for(int i=0;i<32;i++)
        {
            if((temp>>i)&1 == 1) sum++;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12