企业网站用什么系统好,教育wordpress模板下载地址,电子商务网站规划与建设摘要,设计网页图片目录 一、#xff1a;⾯试题 01.01.判定字符是否唯⼀1.1 位图1.2 hash思路1.3 暴力枚举 二、268.丢失的数字2.1 位运算#xff0c;异或2.2 数学求和 三、371.两整数之和四、137.只出现⼀次的数字 II五、⾯试题 17.19.消失的两个数字 一、#xff1a;⾯试题 01.01.判定字符是… 目录 一、⾯试题 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 位变为1x 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 i1; 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 (n1) * n / 2;for(int i 0; i n; i)sum - nums[i];return sum;}
}三、371.两整数之和
题目链接371.两整数之和 题目描述
题目解析
不使用加法算ab
解题思路
使用异或异或是无进位相加。那么我们只需要将要进位的地方记录下来要进位的地方是两个数都是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那么每位上的和都是3nx。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 ( (xi) 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 n2; i) {if(i n) last ^ nums[i];last ^ i;}last last -last;for(int i 0; i n2; 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;}
}
