消失的两个数字
消失的两个数字
“单身狗”进阶版思路
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int ret = 0;int n = nums.size();for(int i = 0; i < n; i++){ret ^= (nums[i] ^ i);}ret ^= (n ^ (n + 1) ^ (n + 2));// 按位异或的规则是相异为1// 找出从最低位开始第一次出现 1 的位置,这个位置一定对应两个数字的二进制位是一个为0 ,一个为1int flag = 0;while(!((ret >> flag) & 1)) flag++;vector<int> v1;vector<int> v2;for(int i = 0; i < n; i++){if(((nums[i] >> flag) & 1) == 1) v1.push_back(nums[i]);else v2.push_back(nums[i]);}for(int i = 1; i < n + 3; i++){if(((i >> flag) & 1) == 1) v1.push_back(i);else v2.push_back(i);}// 对 v1 和 v2 分别操作vector<int> v3;int tar = 0;for(int i = 0; i < v1.size(); i++){tar ^= v1[i];}v3.push_back(tar);tar = 0;for(int i = 0; i < v2.size(); i++){tar ^= v2[i];}v3.push_back(tar);return v3;}
};
只出现一次的数字 II
只出现一次的数字 II
思路:将所有数字的每一位比特位相加,这些比特位的和有如下规律:
只需要定义一个整形变量,通过上述方法计算出它的每一个比特位即可!
class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0; // 只出现一次的数字for(int i = 0; i < 32; i++){// 修改第 i 位的值// 将每个数的第 i 个比特位加起来int sum = 0;for(int j = 0; j < nums.size(); j++){sum += ((nums[j] >> i) & 1);}sum %= 3;ret |= (sum << i);} return ret;}
};
两整数之和
两整数之和
class Solution {
public:int getSum(int a, int b) {// ^ 是无进位相加,只需要每次找到进的位,再相加,等到进位为 0 的时候,就结束了int sum = a ^ b;size_t carry = (size_t)((a & b) << 1); // carry 是进的位while(carry){a = sum, b = carry;sum = a ^ b;carry = size_t((a & b) << 1);}return sum;}
};
^ 异或运算是:两个数对应比特位相同为0,相异为1,也叫 不进位相加
只需要利用按位异或运算符进行不进位相加运算,然后每次加上它的进位即可!直到进位为0!
判断字符是否唯一
判定字符是否唯一
两种方法:哈希表和位图(位图是进阶方法)
哈希表
class Solution {
public:bool isUnique(string astr) {int a[26] = { 0 };for(int i = 0; i < astr.size(); i++){a[astr[i] - 'a'] ++ ;}for(int i = 0; i < 26; i++){if(a[i] > 1) return false;}return true;}
};
位图
和哈希表思路一样,但是将标记存在32个比特位中,利用位运算来控制比特位的值!
class Solution {
public:bool isUnique(string astr) {int n = astr.size();if(n > 26) return false;int bit_set = 0; // 一个位图整形for(int i = 0; i < n; i++){int a = bit_set >> (astr[i] - 'a'); // bit_set 移位后的数if((a & 1) == 0) {bit_set |= (1 << (astr[i] - 'a'));}else if((a & 1) == 1) return false;}return true;}
};