目录
- 一、：⾯试题 01.01.判定字符是否唯⼀
- 1.1 位图
- 1.2 hash思路
- 1.3 暴力枚举
- 二、268.丢失的数字
- 2.1 位运算，异或
- 2.2 数学求和
- 三、371.两整数之和
- 四、137.只出现⼀次的数字 II
- 五、⾯试题 17.19.消失的两个数字
一、：⾯试题 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;}
}