位运算算法题

一.判断字符是否唯一

 法一：

        我们直接借助一个字符数组来模拟哈希表统计字符串即可，并且我们没有必要先将所有字符都放入字符数组中，边插入边判断，当我们要插入某个字符的时候，发现其已经出现了，此时必然重复，直接返回false。

        时间复杂度：O(n)，最坏情况下只需要遍历一次字符串即可

        空间复杂度：O(1)，我们只是用了固定的常数级的额外空间：26个char的字符数组

法二：

        因为字符串只包含26个小写字母。我们可以用一个int变量的26个bit位来依次表示26个小写字母。0表示没出现，1表示出现，如果遍历到那个字符，发现其对应的二进制位为1，表示该字符重复出现，返回false。

        我们首先定义一个int变量mark来记录字符的出现次数。接着我们遍历字符串，我们让字符a对应0位置，以此类推。遍历字母的时候，先判断对应位是0还是1( (x>>i) & 1 )，如果是1直接返回，如果是0，则将该位修改成1( x |= ( 1<< i ) )

        时间复杂度：O(n)，最坏情况下只需要遍历一遍字符串即可

        空间复杂度：O(1)，只使用了一个int变量来标记字母

细节：如果字符串的长度大于26，则该字符串一定存在重复字符。直接返回false。

// C++
// 法一：

class Solution 
{
public:
    bool isUnique(string astr) 
    {
        int hash[26] = {0};
        for(auto e : astr)
        {
            if(hash[e-'a'] == 1) return false;
            else hash[e-'a'] = 1;
        }
        return true;
    }
};

// 法二：
class Solution 
{
public:
    bool isUnique(string astr) 
    {
        if(astr.size() > 26) return false;
        int mark = 0;
        for(auto e : astr)
        {
            int index = e-'a';
            if(((mark >> index) & 1) == 0) mark |= (1<<index);
            else return false;
        }
        return true;
    }
};

# Python
# 法二：

class Solution:
    def isUnique(self, astr: str) -> bool:
        if len(astr) > 26 :
            return False
        mark = 0
        for e in astr:
            index = ord(e) - ord('a')
            if ((mark >> index) & 1) == 1 :
                return False;
            else:
                mark |= (1<<index)
        return True

二.丢失的数字

 0~n这n+1个数中，有n个数放在了数组中，我们要找出那缺少的那个数

解法：

        我们借助异或运算符的性质：a^a = 0，a^0 = a，a^b^a = (a^a)^b.

        我们可以先将数组的元素都异或，然后在将0~n这n+1个数再异或，这样整个数据集就满足只有一个数出现了一次，其余都出现了两次。这样重复的数就可以通过异或操作变为0，最后剩下的数就是丢失。

        时间复杂度：O(n)，我们只需要遍历两遍数组，即可得到异或结果

        空间复杂度：O(1)，我们只是用了一个int变量来存储异或的结果。

// C++

class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        int mark = 0;
        for(auto e : nums) mark ^= e;
        for(int i=0; i<=nums.size(); ++i) mark ^= i;
        return mark;
    }
};

# Python

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        mark = 0
        for i in nums:
            mark ^= i
        for i in range(0,len(nums)+1):
            mark ^= i
        return mark

三.两整数之和

不使用加减运算符计算两个整数的和。如果笔试题遇到直接return x+y

解法：

         其实两整数相加的本质就是其对应的二进制位相加，相加无非就是进位与不进位两种情况。对于a、b来说，它们对应相加的二进制位无非下面四种情况：

        a          b

————————————————

        0    +    1    =    1

        1    +    0    =    1

        0    +    0    =    0

        1    +    1    =    0（2，需要进位：10）

        我们之间了解过，异或运算符就是无进位相加的结果，所以我们可以先计算出a+b的无进位相加的结果，然后再加上进位即可。

        那么怎么计算进位的结果呢？我们观察二进制位相加的可能性，只有11才会进位，所以我们可以借助&运算，只要有0，就不会进位，结果都是0，如果都是1，就需要进位结果就是1.所以我们就可以借助a&b来得到进位。但是我们进位是要进到前一位，所以我们还需要让a&b的结果左移一位。

        得到进位之后，我们在让a^b无进位相加上进位(a&b)<<1,这样就将这两部分加在了一起。但是这样相加之后，可能有出现了需要进位的情况，所以我们依旧得先进行无进位相加，接着求进位，将这两部分相加后重复该操作。知道进位为0.

 a      b

13 + 23

——————————————第一次

        00001101

        00010111

a^b 

        00011010

(a&b)<<1

        00001010

——————————————第二次

a = 00011010

b = 00001010

a^b

        00010000

(a&b)<<1

        00010100

——————————————第三次

a = 00010000

b = 00010100

a^b        

        00000100

(a&b)<<1

        00100000

——————————————第四次

a = 00000100

b = 00100000

a^b

        00100100

(a&b)<<1

        00000000

——————————————此时进位为0，结束循环，返回a^b

a^b = 00100100 = 36

// C++

class Solution 
{
public:
    int getSum(int a, int b) 
    {
        do
        {
            int tmp = a^b;
            b = (a&b)<<1;
            a = tmp;
        }while(b);
        return a;
    }
};

 四.只出现一次的数2

法一：

        我们可以借助哈希表来统计每个元素出现的次数，返回只出现了一次的元素即可

        时间复杂度：O(n)，遍历一遍数组和一遍哈希表即可

        空间复杂度：O(k)，k表示数组中不同元素的个数

法二： 

        我们可以依次求出最终结果的每一个二进制位的数是0还是1。具体的求答案的第i位二进制（i从0开始），对于非答案元素来说，它们都出现了三次，所以第i位的二进制要么是三个0，要么是三个1。所以对于所有的非答案元素来说，它们第i位的和一定是3的倍数。然后再加上答案第i位的二进制0/1，结果要么还是3的倍数，要么就是3的倍数+1.所以我们最后只要对第i位的和%3，就可以拿出答案的第i位的二进制。

        得到第i位之后，我们需要将第i位设置好，如果是0则不必，如果是1，则需要将第i位变成1 ret |= (1<<i)

        时间复杂度：O(32*n)， 我们需要遍历求出每一个二进制位，求每一个二进制时还需要遍历数组。

        空间复杂度：O(1)，只使用了一个变量存储最终结果

// C++

// 法一：
class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        unordered_map<int,int> mp;
        for(auto e : nums) mp[e]++;
        for(auto e : mp)
            if(e.second == 1) return e.first;
        return 0; // 为了符合语法规范
    }
};

// 法二：
class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;
        for(int i=0; i<32; ++i)
        {
            int tmp = 0;
            for(auto e : nums)
            {
                tmp += (e>>i)&1;
            }
            if(tmp % 3) ret |= (1<<i);
        }
        return ret;
    }
};

五.面试题 17.19. 消失的两个数字

1~n有n-1个数，数组中少了两个数，所以数组的大小加上2就是N。

这道题其实是之前两道题的结合版。数组中少个两个数，当我们求出N之后，将1~N和数组中的数结合其实，这道题不就变成了一个数组中，只有两个数出现了一次，其他都出现了两次，求这两个数。

解法：

        将数组和1~N这N个数都异或在一起，然后通过异或结果的最右侧的二进制是0还是1进行分类，重新进行异或，分类异或的结果就是答案

        时间复杂度：O(n)，本质上我们就是遍历了4遍数组

        空间复杂度：O(1)，只使用了两个变量来存储结果

// C++

class Solution 
{
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        // 求出N，然后转换成求一个数组所有的数都出现了两次，只有两个数出现了1次
        int n = nums.size()+2;
        int mark = 0;
        for(auto e : nums) mark ^= e;
        for(int i=1; i<=n; ++i) mark ^= i;
        int lao = mark & (-mark); // 找出最右侧的1

        int x1 = 0, x2 = 0;
        for(auto e : nums)
        {
            if(e & lao) x1 ^= e;
            else x2 ^= e;
        }
        for(int i=1; i<=n; ++i)
        {
            if(i & lao ) x1 ^= i;
            else x2 ^= i;
        }
        return {x1,x2};
    }
};