2016网站设计,怎么和其它网站做友情链接,百度网页游戏排行榜,29网站建设全部一.判断字符是否唯一 法一#xff1a; 我们直接借助一个字符数组来模拟哈希表统计字符串即可#xff0c;并且我们没有必要先将所有字符都放入字符数组中#xff0c;边插入边判断#xff0c;当我们要插入某个字符的时候#xff0c;发现其已经出现了#xff0c;此时必然重复…一.判断字符是否唯一 法一 我们直接借助一个字符数组来模拟哈希表统计字符串即可并且我们没有必要先将所有字符都放入字符数组中边插入边判断当我们要插入某个字符的时候发现其已经出现了此时必然重复直接返回false。 时间复杂度O(n)最坏情况下只需要遍历一次字符串即可 空间复杂度O(1)我们只是用了固定的常数级的额外空间26个char的字符数组 法二 因为字符串只包含26个小写字母。我们可以用一个int变量的26个bit位来依次表示26个小写字母。0表示没出现1表示出现如果遍历到那个字符发现其对应的二进制位为1表示该字符重复出现返回false。 我们首先定义一个int变量mark来记录字符的出现次数。接着我们遍历字符串我们让字符a对应0位置以此类推。遍历字母的时候先判断对应位是0还是1( (xi) 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 | (1index);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 | (1index)return True
二.丢失的数字 0~n这n1个数中有n个数放在了数组中我们要找出那缺少的那个数
解法 我们借助异或运算符的性质a^a 0a^0 aa^b^a (a^a)^b. 我们可以先将数组的元素都异或然后在将0~n这n1个数再异或这样整个数据集就满足只有一个数出现了一次其余都出现了两次。这样重复的数就可以通过异或操作变为0最后剩下的数就是丢失。 时间复杂度O(n)我们只需要遍历两遍数组即可得到异或结果 空间复杂度O(1)我们只是用了一个int变量来存储异或的结果。 // Cclass Solution
{
public:int missingNumber(vectorint nums) {int mark 0;for(auto e : nums) mark ^ e;for(int i0; inums.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 xy
解法 其实两整数相加的本质就是其对应的二进制位相加相加无非就是进位与不进位两种情况。对于a、b来说它们对应相加的二进制位无非下面四种情况 a b ———————————————— 0 1 1 1 0 1 0 0 0 1 1 02需要进位10 我们之间了解过异或运算符就是无进位相加的结果所以我们可以先计算出ab的无进位相加的结果然后再加上进位即可。 那么怎么计算进位的结果呢我们观察二进制位相加的可能性只有11才会进位所以我们可以借助运算只要有0就不会进位结果都是0如果都是1就需要进位结果就是1.所以我们就可以借助ab来得到进位。但是我们进位是要进到前一位所以我们还需要让ab的结果左移一位。 得到进位之后我们在让a^b无进位相加上进位(ab)1,这样就将这两部分加在了一起。但是这样相加之后可能有出现了需要进位的情况所以我们依旧得先进行无进位相加接着求进位将这两部分相加后重复该操作。知道进位为0. a b 13 23 ——————————————第一次 00001101 00010111 a^b 00011010 (ab)1 00001010 ——————————————第二次 a 00011010 b 00001010 a^b 00010000 (ab)1 00010100 ——————————————第三次 a 00010000 b 00010100 a^b 00000100 (ab)1 00100000 ——————————————第四次 a 00000100 b 00100000 a^b 00100100 (ab)1 00000000 ——————————————此时进位为0结束循环返回a^b a^b 00100100 36 // Cclass Solution
{
public:int getSum(int a, int b) {do{int tmp a^b;b (ab)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 | (1i) 时间复杂度O(32*n) 我们需要遍历求出每一个二进制位求每一个二进制时还需要遍历数组。 空间复杂度O(1)只使用了一个变量存储最终结果 // C// 法一
class Solution
{
public:int singleNumber(vectorint nums) {unordered_mapint,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(vectorint nums) {int ret 0;for(int i0; i32; i){int tmp 0;for(auto e : nums){tmp (ei)1;}if(tmp % 3) ret | (1i);}return ret;}
};
五.面试题 17.19. 消失的两个数字 1~n有n-1个数数组中少了两个数所以数组的大小加上2就是N。
这道题其实是之前两道题的结合版。数组中少个两个数当我们求出N之后将1~N和数组中的数结合其实这道题不就变成了一个数组中只有两个数出现了一次其他都出现了两次求这两个数。
解法 将数组和1~N这N个数都异或在一起然后通过异或结果的最右侧的二进制是0还是1进行分类重新进行异或分类异或的结果就是答案 时间复杂度O(n)本质上我们就是遍历了4遍数组 空间复杂度O(1)只使用了两个变量来存储结果 // Cclass Solution
{
public:vectorint missingTwo(vectorint nums) {// 求出N然后转换成求一个数组所有的数都出现了两次只有两个数出现了1次int n nums.size()2;int mark 0;for(auto e : nums) mark ^ e;for(int i1; in; 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 i1; in; i){if(i lao ) x1 ^ i;else x2 ^ i;}return {x1,x2};}
};
