【算法】【优选算法】位运算（下）

一、：⾯试题 01.01.判定字符是否唯⼀

题目链接：：⾯试题 01.01.判定字符是否唯⼀
题目描述：

题目解析：

• 给一个字符串，看字符串中字符是否有重复，有返回false，没有返回true。

1.1 位图

解题思路：

• 因为这个字符串全是小写字符，所以只有26个字符，并且求得是是不是有重复。
• 那么我们就可以使用一个int的32个比特位来表示，字符’a’到’z’分别对应二进制的0到25下标。
• 如果下标变成1，后出现了该下标对应的字母，那么就是有重复字符。
• 拿到二进制第 i 位是1还是0：(x >> i) & 1
• 将二进制第 i 位变为1：x = x | (1 << i)

解题代码：

//时间复杂度：O(N)
//空间复杂度：O(1)
class Solution {public boolean isUnique(String astr) {if(astr.length() > 26) return false;int bit = 0;for(int i = 0; i < astr.length(); i++) {int temp = bit;if( ( (temp >> astr.charAt(i) ) & 1) == 1) return false;bit = bit | ( 1 << astr.charAt(i));}return true;}
}

1.2 hash思路

解题思路：

• 使用一个hash数组来记录每个字符出现的次数，因为全是小写字母，只需申请有效空间即可。

解题代码：

//时间复杂度：O(N)
//空间复杂度：O(1)
class Solution {public boolean isUnique(String astr) {if(astr.length() > 26) return false;int[] hash = new int[26];for(int i = 0; i < astr.length(); i++) {if(hash[astr.charAt(i)-'a'] != 0) return false;hash[astr.charAt(i)-'a']++;}return true;}
}

1.3 暴力枚举

解题思路：

• 直接两层for循环遍历，第一层遍历字符，第二层在剩下字符串种找是否有相同字符。

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {public boolean isUnique(String astr) {if(astr.length() > 26) return false;for(int i = 0; i < astr.length(); i++) {for(int j = i+1; j < astr.length(); j++) {if(astr.charAt(i) == astr.charAt(j)) return false; }}return true;}
}

二、268.丢失的数字

题目链接：268.丢失的数字
题目描述：

题目解析：

• 给一个长度为n的数组，数组中在[ 0 , n ]中只有一个数字没包含，返回这个数字。

2.1 位运算，异或

解题思路：

• 将数组中的元素一一进行异或运算，同时与[ 0 , n ]的数字进行异或运算。
• 到最后这剩下数组中没有的元素，没有与相同数字进行异或运算，最后就只剩下他了。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int missingNumber(int[] nums) {int ret = 0;for(int i = 0; i < nums.length; i++) {ret = ret ^ i ^ nums[i];}return ret ^ nums.length;}
}

2.2 数学求和

解题思路：

• 先将[ 0 , n ]的和求出来。然后遍历数组，减去数组中元素。最后剩下的就是要求的数字。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int missingNumber(int[] nums) {int n = nums.length;int sum = (n+1) * n / 2;for(int i = 0; i < n; i++)sum -= nums[i];return sum;}
}

三、371.两整数之和

题目链接：371.两整数之和
题目描述：

题目解析：

• 不使用加法，算a+b

解题思路：

• 使用异或，异或是无进位相加。
• 那么我们只需要将要进位的地方记录下来，要进位的地方是两个数都是1才进位。也就是 按位与的结果，但是下一次异或的是，上一次按位与结果左移一位的结果。
• 所以我们最多按位异或，按位与32次。

解题代码：

//时间复杂度：O(1)
//空间复杂度：O(1)
class Solution {public int getSum(int a, int b) {while( b != 0) {int temp = a;a = a ^ b;b = (temp & b) << 1;}return a;}
}

四、137.只出现⼀次的数字 II

题目链接：137.只出现⼀次的数字 II
题目描述：

题目解析：

• 给一个数组，数组中只有一个元素只出现一次，其余全出现了3次，返回只出现一次的那个元素。

解题思路：

• 当我们将数组中元素的每一位比特位求和之后，假设只出现一次的数的比特位上是x，那么每位上的和都是3n+x。n就代表出现3次的元素的比特位求一次和的结果。
• 所以当我们将和对3取余后，那么该比特位上的值就和要求元素一样了。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int singleNumber(int[] nums) {int ret = 0;for(int i  = 0; i < 32; i++) {//求比特位之和int sum = 0;for(int x : nums) {sum += ( (x>>i) & 1);}//修改结果对应比特位sum %= 3;if(sum == 1) ret = ret | (1 << i);}return ret;}
}

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

题目链接：⾯试题 17.19.消失的两个数字
题目描述：

题目描述：

• 给一个数组，这个数组在[ 1 , nums.length + 2]区间有两个数不包含，找到并返回。

解题思路：

• 其实这道题跟上一篇的第六道是一道题。
• 先将所有的元素（数组元素和[ 1 , nums.length + 2] 的数）全部异或在一起，就相当于两个只出现一次的元素异或在一起。
• 在去出上诉异或结果，最右边的1。这位上两个数字是不相同的。
• 所以再次遍历数组与结果数组异或，如果该位上与第二步结果相同放一个下标，不同放另一个下标。最后得到的就是结果了

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int[] missingTwo(int[] nums) {int n = nums.length;int[] ret = new int[2];int last = 0;for(int i = 0; i <= n+2; i++) {if(i < n) last ^= nums[i];last ^= i;}last = last & -last;for(int i = 0; i <= n+2; i++) {if(i < n) {if((last & nums[i]) == 0)  ret[0] ^= nums[i];else ret[1] ^= nums[i];}if((last & i) == 0) ret[0] ^= i;else  ret[1] ^= i;}return ret;}
}