位运算算法题

一.判断字符是否唯一

 法一：

        我们直接借助一个字符数组来模拟哈希表统计字符串即可，并且我们没有必要先将所有字符都放入字符数组中，边插入边判断，当我们要插入某个字符的时候，发现其已经出现了，此时必然重复，直接返回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 Falsemark = 0for 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;}
};

# Pythonclass Solution:def missingNumber(self, nums: List[int]) -> int:mark = 0for i in nums:mark ^= ifor i in range(0,len(nums)+1):mark ^= ireturn 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); // 找出最右侧的1int 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};}
};