292.Nim遊戲
思考：當石頭數為：1,2,3時，你先手，拿1~3塊石頭。肯定能直接獲勝。如果當石頭數為4時，你有三種拿的可能1,2,3.此時剩餘的為3,2,1.這時候你的朋友相當于是“場面上剩下1~3塊石頭，并且他先手”，那麼這種情況你就肯定輸了。同理，當5塊石頭時，你拿起1~3塊，剩下的為4,3,2。剛剛已經讨論了場面剩下4塊的時候，無論你怎麼選都是輸，那麼對于你的朋友也是一樣。當8塊石頭時，你隻能挑1~3塊。剩下7~5塊。這時該你的對手挑，是以肯定能挑出隻剩4塊的情況。規律就是：當桌子上的石頭書為4的倍數時候，你肯定就輸，否則你就能赢。
class Solution {
public:
bool canWinNim(int n) {
if(n%4){
return true ;
}
else{
return false;
}
}
};
344.翻轉字元串
一開始出了個錯誤：Char 39: error: no matching function for call to 'Solution::reverseString(std::vector<char>&)'，我還以為送出了的函數咋錯了呢，後來發現題目改了“ string reverseString(string s)改成了void reverseString(vector<char>& s)”，跟符合題目的要求了吧！
解析：這樣就不能直接調用STL 中的reverse函數，一個reverse(s.begin(),s.end())來直接解決問題了！
思考：首先是不要另外的數組配置設定額外的空間，這種就說我們不能重新弄一個stack<char>類型來存儲了。并且要原地修改輸入數組，使用O(1)的額外空間解決問題。
class Solution {
public:
void reverseString(vector<char>& s) {
for(int i = 0,j = s.size()-1;i <= j ;i++,j--){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
};
557、反轉字元串的單詞III
思考：一開始我想的用flag來控制，當遇到' '的時候就flag =1 ，然後可以reverse，reverse之後再把flag = 0.
class Solution {
public:
string reverseWords(string s) {
int flag = 0;
auto word_begin = s.begin();
for(auto iter = s.begin();iter!=s.end();iter++){
if(*iter == ' '){
flag = 1;
}
if(flag == 1){
reverse(word_begin,iter);
word_begin = iter + 1 ;
flag = 0;
}
}
reverse(word_begin,s.end());
return s;
}
};
後來看了别人寫的代碼，我才想到。。直接判斷目前的字元是不是' '不就行了？是的話就reverse，不是就繼續循環。reverse（iter1，iter2），iter2表示要逆轉的字元的下一位。正好循環到' '。并且把word_begin 更新到 目前疊代器iter2的下一位，表示下一個單詞的開頭。
class Solution {
public:
string reverseWords(string s) {
auto begin = s.begin();
for(auto iter = s.begin();iter!=s.end();++iter){
if(*iter==' '){
reverse(begin,iter);
begin = iter+1;
}
}
reverse(begin,s.end());
return s;
}
};
136.隻出現一次的數字
思考：通過哈希表來構造，每個數字出現的次數。
構造哈希表：map<類型1，類型2>。
class Solution {
public:
int singleNumber(vector<int>& nums) {
map<int,int> hash_map;
for(int i = 0 ; i < nums.size();i++){
if(hash_map.find(nums[i]) == hash_map.end()){
hash_map[nums[i]] = 0;
}
hash_map[nums[i]]++;
}
for(int i = 0 ; i < nums.size();i++){
if(hash_map[nums[i]]==1){
return nums[i];
}
}
return 0;
}
};
或者提取hash_map當中的映射。
class Solution {
public:
int singleNumber(vector<int>& nums) {
map<int,int> hash_map;
for(auto item : nums){
if(hash_map.find(item) == hash_map.end()){
hash_map[item] = 0;
}
hash_map[item]++;
}
for(auto item : hash_map){
if(hash_map[item.first]==1){
return item.first;
}
}
return 0;
}
};
本體應該使用：“異或”操作，異或：0和1，兩者相等為0,不等為1。【最快的操作】
因為題目中，兩次，一次。說明整個數組數字都是出現2次，隻有一個出現1次。
初始化result為0，和每一位進行異或操作，如[2,2,1]。這個數組，0異或2 = 2；2異或2 = 0；1異或0 = 1.求得最後需要的隻出現一次的就是result。因為一個數字和自身異或為0。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for(int i = 0 ; i < nums.size();i++){
result ^= nums[i];
}
return result;
}
};
169、求衆數
思考:使用哈希表建立映射，出現次數多于n / 2 的就是我們想要找到的結果。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int vec_size = nums.size();
map<int,int> hash_map;
for(int i = 0 ; i < vec_size;i++){
if(hash_map.find(nums[i])==hash_map.end()){
hash_map[nums[i]] = 0 ;
}
hash_map[nums[i]] ++ ;
}
for(int i = 0 ; i < vec_size;i++){
if(hash_map[nums[i]] > vec_size / 2 ){
return nums[i];
}
}
return 0;
}
};
第二種解法：摩爾投票法。在任何數組中，出現次數大于該數組長度一半的值隻能有一個。
摩爾投票法的基本思想很簡單，在每一輪投票過程中，從數組中找出一對不同的元素，将其從數組中删除。這樣不斷的删除直到無法再進行投票，如果數組為空，則沒有任何元素出現的次數超過該數組長度的一半。如果隻存在一種元素，那麼這個元素則可能為目标元素。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums[0];
int times = 1;
for(int i = 1 ; i < nums.size();i++){
if(nums[i] != n){
times--;
if(times <= 0){
n = nums[i+1]; //目前這位數把出現次數消耗完了，是以應該選取的新的候選數字
//肯定是目前數位的下一位。
}
}
else{
times++;
}
}
return n;
}
};