【1】LeetCode 136 Single Number
題意：奇數個數，其中除了一個數只出現一次外，其他數都是成對出現，比如1,2,2,3,3...，求出該單個數。
解法：容易想到異或的性質，兩個相同的數異或為0，那么把這串數從頭到尾異或起來，最后的數就是要求的那個數。
哪些是I類II類工具？代碼如下：
class Solution { public:int singleNumber(vector<int>& nums) {int sum = 0;for(int i=0;i<nums.size();i++) sum ^= nums[i];return sum;} };
【2】LeetCode 137?Single Number II
題意：給一串數，除了一個數只出現一次外，其他數都出現了三次。求那個單個數。
解法：還是從位操作上考慮，把每個數寫成二進制列出來，每位對齊，可以發現，每一位上的1的個數要么是3的倍數，要么是3的倍數+1，那么把每一位的1個數加起來，模3即可的單個數的該位為0還是為1。
LeetCode、代碼如下：
class Solution { public:int singleNumber(vector<int>& nums) {int ans = 0;for(int i=0;i<32;i++) {int dream = (1<<i), cnt = 0;for(int j=0;j<nums.size();j++)cnt += (bool)(nums[j] & dream);cnt = cnt % 3;ans ^= (cnt << i);}return ans;} };
【3】LeetCode 260 Single Number III
題意：有一串數字，其中有兩個不同的數，各出現一次，其他的數都出現2次。找出這兩個數。
解法：看到其他數出現兩次，又想到異或操作，如果全部異或起來，得到的是那兩個數的異或。既然是兩個不同的數，那么異或的二進制里面必然是有1的，我們先找出這個1，然后逐個檢查，如果這位有1，那么異或到a，否則異或到b，最后的a,b即是這兩個值。找1可以找最后一個1，x&(-x)即可。
leetcode1120。代碼如下：
class Solution { public:vector<int> singleNumber(vector<int>& nums) {int xorsum = 0;for(int i=0;i<nums.size();i++) xorsum ^= nums[i];int lastdifferentbit = xorsum & (-xorsum);int a = 0, b = 0;for(int i=0;i<nums.size();i++) {if(nums[i] & lastdifferentbit) a ^= nums[i];else b ^= nums[i];}return vector<int>{a,b};} };
