下面是这个算法实现：

classSolution{public:vector<int>singleNumber(vector<int>&nums){// 第一步，对所有元素进行异或，最终的结果就是两个只出现一次数的异或结果intdiff =0;for(intnum :nums){diff ^=num;}// 找到diff中任何为1的位，可以使用diff & -diff快速找到// 这个操作可以隔离出diff最右端的1unsignedintdiff_unsigned =diff;diff_unsigned &=-diff_unsigned;// 使用找到的这一位将数组中的数字分成两组vector<int>results(2,0);// 最终结果for(intnum :nums){if((num &diff_unsigned)==0){// 第一组，与diff_unsigned对应位为0results[0]^=num;}else{// 第二组，与diff_unsigned对应位为1results[1]^=num;}}returnresults;}};

在这个代码中：

• diff_unsigned最终会被设置为两个目标数字的异或结果。这给了我们一种找到最右边的1的方法。ones将会记录每个位只出现一次的情况，而twos将会记录每个位出现两次的情况

  对于每个数字num及其每一位，我们更新ones和twos：

  1. 在第i个位置上，如果ones里的位是1，则表示num要么是第一次遇到i位为1，要么是第四次。这个1所在的位将用于分辨哪些数字在该位为0或1 —— 这正是对数组进行划分的依据

     6.电话号码的字母组合

     题目链接：17.电话号码的字母组合
     题目描述：

     这个问题可以通过回溯法解决，这是一种通过穷举所有可能的解来找到全部解的算法。如果出现的是一个新的1（即 num中的1，而 twos中并没有记录），twos就会记录它。我们维护一个 current字符串，它保存当前的部分组合。这会出现加到三的情况，我们随后会处理。我们在整体数组中使用循环来考虑每个数字的影响。因为异或操作具有交换律和结合律，同时一个数字和自己进行异或会变成0，所以最终剩下的结果就是那两个只出现一次的数字的异或结果

     这个结果中至少有一个位是1（否则这两个数相同），我们可以找到这个数中的任何一个为1的位，用它来把原数组分成两组，一组在该位上是1，一组在该位上是0。即使刚才 ones ^ num把某些位变成了1，若那些位在 twos中已经出现过两次，我们必须确保它们在 ones中不变成1

结合二者，ones在每次迭代结束时仅保留那些恰好出现一次的位。

& ~ones：这个按位与操作保证如果在 ones中有1（意味着这个位已经出现了一次），我们不会在 twos中加入该位。由于除了一个数字以外，其它数字都出现了三次，我们可以构造一个数字的每一位相加后，模3的结果就是这个只出现一次的数字的相应位

思路如下：

使用两个整数变量ones和twos。例如，假设我们有一个4位的系统：

正数 2的二进制表示:  0010反码 (invert):      1101加1得到负数 -2:      1110

观察发现，从正数2的二进制表示到负数-2的表示，最右边的1以及之前的所有0都保持不变，而最右边的1之后的所有位都翻转了。

classSolution{public:intsingleNumber(vector<int>&nums){intones =0,twos =0;for(intnum :nums){ones =(ones ^num)&~twos;twos =(twos ^num)&~ones;}returnones;}};

当我们讨论处理出现三次的数字和一个只出现一次的数字时，ones和 twos的位操作确实是难以理解的 ，分解这两行代码：

对于每一个新的数字 num，我们用 ones和 twos来跟踪彼此独立的状态：

1. ones = (ones ^ num) & ~twos;

这里，我们正更新 ones以包含出现一次的位。~twos是对 twos取反，意味着取出 twos中为0的位。最终，由于所有出现三次的数字在这两个变量中都被消去，ones会留下那个出现一次的唯一位

5.只出现一次的数字III

题目链接：260.只出现一次的数字III
题目描述：

此类问题可以通过位运算（异或操作）来解决。基本思想是从左到右遍历数字字符串，对于每个数字，向当前的字母组合中添加对应的每个字母，然后对剩余的字符串重复这个过程。函数的工作流程是这样的：

1. 确定终止条件：如果 current的长度与输入数字字符串的长度相同，说明当前递归路径已经走到头，我们找到了一个完整的字母组合，将其添加到结果中。如果是第四次，我们已经在twos里记录了两次，所以这次应该把ones里的该位清零，否则保持不变

2. 同理，如果twos里的位是1，则是第二次遇到i位为1或者是第五次。换句话说，diff_unsigned &= -diff_unsigned;将结果的所有位都置为0，除了最右边的1所在的位。

   在解决问题时，我们首先会通过对所有数字进行异或得到 diff，这代表了两个只出现一次的数字的差异。只有那些在 twos中没有记录（即还没达到两次）的1才应该加入 ones。

   下面是递归解决实现：

   classSolution{public:vector<string>letterCombinations(string digits){if(digits.empty())return{};// 如果输入为空，直接返回空数组vector<string>mappings ={// 数字到字母的映射"","","abc","def",// '0','1','2',..."ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string>result;string current;backtrack(result,digits,0,current,mappings);returnresult;}private:voidbacktrack(vector<string>&result,conststring&digits,intindex,string&current,constvector<string>&mappings){if(index ==digits.length()){// 如果到达了数字字符串的末尾，就添加当前的字母组合到结果中result.push_back(current);return;}string letters =mappings[digits[index]-'0'];// 获取当前数字对应的所有字母for(charletter :letters){// 遍历这些字母current.push_back(letter);// 添加当前的字母backtrack(result,digits,index +1,current,mappings);// 继续处理下一个数字current.pop_back();// 回溯，移除当前字母，以便尝试下一个字母}}};

   这段代码定义了一个辅助函数 backtrack，用来递归寻找所有可能的字母组合。

   

   🔥个人主页：Quitecoder

   🔥专栏：Leetcode刷题

   
   

   目录

   • 1.只出现一次的数字
   • 2.杨辉三角
   • 3.删除有序数组中的重复项
   • 4.只出现一次的数字II
   • 5.只出现一次的数字III
   • 6.电话号码的字母组合

   1.只出现一次的数字

   题目链接：136.只出现一次的数字
   题目描述：

   这道题很简单，我们只需要遍历一遍数组，利用异或操作的性质（一个数与自身异或结果为0，任何数与0异或还是其本身）

   classSolution{public:intsingleNumber(vector<int>&nums){intvalue =0;for(autov:nums){value^=v;}returnvalue;}};

   2.杨辉三角

   题目链接：118.杨辉三角
   题目描述：

   这道题我们需要构造二维数组，典型的vector的嵌套使用

   
   首先，我们先构建二维数组，开辟行数大小：

   vector<vector<int>>v(numRows);

   接着对每一行进行开辟空间，并将两端初始化为1

   for(inti=0;i<numRows;i++){v[i].resize(i+1);v[i][0]=1;v[i][i]=1;}

   注意，resize是会进行初始化的，我们没有传值，默认为零

   所以我们只需要遍历一遍，遍历到的位置为0，进行相加操作

   完整代码如下：

   classSolution{public:vector<vector<int>>generate(intnumRows){vector<vector<int>>v(numRows);for(inti=0;i<numRows;i++){v[i].resize(i+1);v[i][0]=1;v[i][i]=1;}for(inti=0;i<numRows;i++){for(intj=0;j<i;j++){if(v[i][j]==0){v[i][j]=v[i-1][j]+v[i-1][j-1];}}}returnv;}};

   3.删除有序数组中的重复项

   题目链接：26.删除有序数组中的重复项
   题目描述：

   这题是一道简单的双指针思路的题，由于已经排序好，我们只需要设置两个索引，一个向后遍历，若与前面的索引指向值不相同，则对前面的值进行修改

   lass Solution {public:intremoveDuplicates(vector<int>&nums){if(nums.size()==0){return0;}intslow =0;for(intfast =1;fast <nums.size();fast++){if(nums[fast]!=nums[slow]){slow++;nums[slow]=nums[fast];}}returnslow +1;}};

   完成了值的覆盖过程

   4.只出现一次的数字II

   题目链接：137.只出现一次的数字II
   题目描述：

   这个问题的解决方案基于位操作和有限状态自动机的原理。对于 num中新出现的1，ones中还没有记录，这将被加进 ones

3. & ~twos：接下来的按位与操作与 ~twos结合表示：我们删除 twos中已经出现两次的位。首先，我们可以通过对所有数组元素执行异或操作来找出两个只出现一次的元素的异或结果。
   diff 变量首先被转换成一个无符号整数 diff_unsigned，然后对它进行取负和按位与操作，以避免未定义行为。

   通过这个位的差异，我们可以将所有的数字分成两组来进一步操作，每组包含一个只出现一次的数字以及成对出现的数字。然后再对这两个组分别进行异或操作，即可得到这两个只出现一次的数字。如果在 twos中的位是1，且对应的 num中的位也是1，那么它们会重置为0，因为现在这个位出现了第三次，而我们的目标是找到出现了一次和两次的位。这样就保证了即使 diff 的最高有效位是1，我们也不会超出无符号整型的范围

   然后使用 diff_unsigned &= -diff_unsigned;来保留最右边的1，这是两个独特数字在二进制表示中第一个不同的位。这样每组就包含了一个只出现一次的数字和一些成对出现的数字。我们要处理的数字是32位整数，因此，我们需要考虑每一位相加后的结果。

   总结来说，这两步操作是相互独立并且排他的：它们保证一个位在 ones或 twos中出现，但不会同时出现。现在，如果我们对2和-2执行按位与操作：

   正数 2:                0010负数 -2:               1110按位与:                0010

   按位与操作的结果就是只有最右边的1保留了下来，其它所有位都变成了0。如果某个位同时在 ones和 twos中出现，这意味着这个位出现了3次，并且最终会被忽略。为了更好地理解这个技巧，我们需要先了解计算机中的数字表示——特别是补码表示法，因为这个技巧与负数的二进制表示相关

   在补码表示中，一个负数是通过取其正值的二进制表示的反码（每个位取反）然后加1得到的。如果是第五次，我们既要在ones里面加1，同时也要在twos里面清零该位，否则保持不变

4. 由于我们只需要考虑每个位上1出现的次数，所以任何时候位上的1出现3次，我们都应该清零

最后，ones保留的就是每位上出现一次的结果，而twos将会是0。

回溯处理：每次递归调用完成后，需要将之前添加的字母移除，以便对当前位置尝试不同的字母。