C++算法之位运算（十分钟带你速通）上

位运算基础运算有0就是0示例|运算有1就是1示例^运算相同为0相异为1示例后面学到其它位运算再补面试题 01.01. 判定字符是否唯一 - 力扣LeetCode解法一使用哈希表思路1、0~26的小写字母所以我们开25空间的哈希表数组2、扫描一次字符串当出现第一次就再继续扫描如果同样的也就是我们可以特判此时大于1就是重复了直接false否则继续扫描扫描完没有重复就trueclass Solution { public: bool isUnique(string astr) { // 创建一个长度为26的整型数组用来记录26个小写字母出现的次数 // 下标0对应a下标1对应b...下标25对应z // 初始值全部为0表示所有字母都还没出现过 int haxi[26] {0}; // 遍历字符串中的每一个字符 // i从0开始到字符串长度-1结束 for (int i 0; i astr.size(); i) { // 计算当前字符对应的数组下标 // 例如a-a0b-a1c-a2 // 这样就能把字母映射到数组的对应位置 int index astr[i] - a; // 将该字母的出现次数加1 // 第一次出现0变成1第二次出现1变成2 haxi[index]; // 检查该字母是否已经重复出现 // 如果出现次数大于1说明之前已经出现过一次了 // 现在又遇到一次所以字符串中有重复字符 if (haxi[index] 1) { return false; // 发现重复直接返回false结束函数 } } // 如果遍历完整个循环都没有返回false // 说明所有字符都只出现了一次没有重复 return true; } };解法二位图利用位图思想每一个比特位代表的是字符并且int变量里面的32位足够表示所有的小写字母了当比特位里面如果是0就是没有出现如果是1就表示出现过了注意优化当他的字符串要是27位是不是就表示他必定有重复的字符串class Solution { public: bool isUnique(string astr) { // 优化 if(astr.size()26)return false; int arr0; for(auto c : astr) { // 字符转数字 int i c -a; // 取字符是不是1是1就是出现过 if(((arri) 1) 1)return false; // 出现过了装进去 arr | 1i; } return true; } };268. 丢失的数字 - 力扣LeetCode这题隐约在牛客周赛刷到过好像cf也有年代太久了那我这次就带大家学一下自己也复习一遍方法一哈希表开一个哈希表扫描一下原来的数组把数组里面的数字映射到哈希表然后哈希表改成1最后在扫描一下哈希表如果是0就是丢失的数字class Solution { public: int missingNumber(vectorint nums) { int haxi[10005] {0}; for(auto c : nums) { haxi[c]1; } for(int i0;in;i) { if(haxi[i]0) { return i; } } return -1; } };方法二高斯求和把数字的1~n的下标给求和起来记住一定是下标最后的值减去数组里面的值就是丢失的数字。例如【301】下标求和是66-3-12那这个不就是丢失的数字吗class Solution { public: int missingNumber(vectorint nums) { int n nums.size(); int sum (1n)*n; int result sum/2; for(auto c : nums) { result-c; } return result; };方法3位运算消消乐异或和最简单的理解异或和就是一样的可以消掉例如【301】【0123】013是不是消掉了剩下2class Solution { public: int missingNumber(vectorint nums) { int ret0; for(auto c : nums) ret^c; for(int i0;inums.size()1;i) ret^i; return ret; };