leetcode最大數，【leetcode】只出現一次的數字（位運算）

LeetCode136：只出現一次的數字

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。

解題思路：

這里可以使用異或運算。即兩個相同的數字異或為0，而0與任何數字異或都是其本身。把數組所有的數都異或，相同的數字異或是為0，那么剩下的就是那個只出現一次的數字。

leetcode最大數？代碼如下：

int test(vector<int> v){int temp=0;for(auto& i:v){temp^=i;}return temp;
}

LeetCode137：只出現一次的數字-Ⅱ

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現了三次。找出那個只出現了一次的元素。說明：你的算法應該具有線性時間復雜度。你可以不使用額外空間來實現嗎？

解題思路
本題對上述做了一些改進，變成了其余元素出現三次！感覺難了比較多。我們有了第一題的解題思路，可能會先想到也用異或來解決，但是位運算中并沒有直接的使得三個相同的數字運算為0的方法！！！

leetcode解析、可以遍歷所有數,讓每個數的二進制的同一位相加，對一個二進制位出現?1的次數對?3取余,若余數為?1,那么我們目標數字的這一位也就是?1.（ps：如果再出個相同數字出現4次的話？方法同理！）

簡單的例子，比如

[1,2,2,2]?其轉換成二進制就是[01,10,10,10],我們可以知道第一位(從右往左)的二進制總共出現了1次1,那么我們的目標數其二進制在第一位就是1,而相對的第二位出現了3次1,那么我們的目標數的二進制在這一位就不是1。

leetcode最長無重復字符串。就這樣可以去到得到目標數的二進制的每一位的數字。接著再把其目標數的二進制的每一位的數字進行按位或處理就得得到目標數。

代碼如下：

int test(vector<int> v)
{int reslut=0;for(int i=0;i<64;++i)//寫64個變量(知道范圍的寫32位應該也行?)記錄每位的二進制1出現的次數{int t =0;for(auto& a:v){t+=(a>>i)&1;  //得到每個數的二進制同一位為1的次數}reslut |=(t%3)<<i;}return reslut;
}

思考：得到二進制的每一位的數字，用按位或處理就可以得到目標數。

用個例子來說明：

一個二進制數 1101，我們可以得到其每一位的數字（其他幾位沒有的，就用0補上）

第一位：0001

第二位：0000；

第三位：0100；

第四位：1000；

把這四個進行按位或處理(有1為1，所有都是0?為0），所以結果是1101。