前置知识储备
掌握基础位操作符是理解后续算法的前提。
经典题目实战
判定字符是否唯一
思路分析: 利用【位图】的思想,每一个【比特位】代表一个【字符】。一个 int 类型的变量有 32 位,足够表示所有的小写字母。若某一位为 0,表示该字符未出现;若为 1,则表示已出现。 这里可以用一个整数直接充当哈希表。
class Solution {
public:
bool isUnique(string astr) {
// 利用鸽巢原理优化,小写字母最多 26 个
if(astr.size() > 26) return false;
int bitmap = 0;
for(auto i : astr){
int e = i - 'a';
// 先判断字符是否出现过
if(((bitmap >> e) & 1) == 1) return false;
// 把当前字符加入到位图中
bitmap |= 1 << e;
}
return true;
}
};
消失的数字
思路分析: 设数组大小为 n,原序列应为 [0, n],现缺失一个数。如果我们将数组中的所有数,以及 [0, n] 范围内的所有数全部【异或】在一起,根据异或的自反性(消消乐规则),成对出现的数字会抵消,最终剩下的就是缺失的那个数字。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret = 0;
// 与数组中所有元素异或
( i : nums) ret ^= i;
( i = ; i <= nums.(); i++) ret ^= i;
ret;
}
};

