#189 Rotate Array

初見 (O(n^2)復雜度）

我覺得這個應該算是brute force。先用back()獲取最后一個元素，用erase()擦除最后一個元素，再在數(shù)組頭用insert()插入該元素。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size();
        k %= size;
        for(int it = 0; it < k; it++){
            int temp = nums.back();
            nums.erase(nums.end()-1);
            nums.insert(nums.begin(), temp);
        }
    }
};

問題主要在insert()這個函數(shù)在數(shù)組頭插入的話時間復雜度是O(n）,那這么下來整體的時間復雜度就是O(n^2)。
我以為這個會超過時間限制，但是居然也打敗了31.91%的人，可喜可賀可喜可賀。

輔助數(shù)組 （O(n)空間復雜度）

這個算是比較直觀的解法了，具體而言就是把需要rotate的元素移出來存到另一個數(shù)組ans里，然后再把剩余元素push到ans中。這種方法出來的rotate元素會和所需要的剛好相反，可以翻轉(zhuǎn)一下。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size();
        k %= size;
        vector<int> ans;
        for(int it = 0; it < k; it++){
            int temp = nums.back();
            ans.push_back(temp);
            nums.erase(nums.end()-1);
        }
        
        reverse(ans.begin(), ans.end());
        
        for(int ind = 0; ind < nums.size(); ind++){
            ans.push_back(nums.at(ind));
        }
        
        nums = ans;
    }
};

這方法把時間復雜度降到了O(n)，但也有個缺點是它有O(n)的空間復雜度，還不如初見的那個brute force版本。

三次翻轉(zhuǎn) (O(1)空間復雜度）

這個方法說實話我自己肯定想不出來，但是在網(wǎng)站的solution里面有，去YouTube看了看也是主流的方法之一，權(quán)當背下來吧。
這個方法說白了就是把整個數(shù)組分成兩部分：需要rotate“走”的部分，和剩余的部分。
舉個例子：
數(shù)組[1 2 3 4 5 6 7]，k = 3
那這個地方需要rotate走的就是[5 6 7]這一塊，剩下的就是[1 2 3 4]；
先把所有的元素翻轉(zhuǎn)過來：[7 6 5 4 3 2 1]
然后翻轉(zhuǎn)rotate走的部分：[5 6 7 4 3 2 1]
最后翻轉(zhuǎn)剩下部分：[5 6 7 1 2 3 4]
三次翻轉(zhuǎn)就可以完成這個rotate的過程。
代碼實現(xiàn)：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int size = nums.size();
        k %= size;
      
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin()+k);
        reverse(nums.begin()+k, nums.end());
        
        
    }
};

要注意的是，reverse()這個函數(shù)接受的第二個參數(shù)應該指向需要翻轉(zhuǎn)元素的后一個位置。
這個算法的時間復雜度為O(n)，空間復雜度為O(1)（不需要占用額外空間）。

#41 First Missing Positive

題目地址：https://leetcode.com/problems/first-missing-positive/
這個題顯然可以用sorting解決，但是題目要求O(n)的復雜度，就不放上來了。

輔助數(shù)組(O(n)空間復雜度）

解法的核心思想是"Put its number in its right place"。
對于這道題來說，不需要考慮負數(shù)，也不需要考慮值大于數(shù)組長度的數(shù)（因為要找的是“最小缺失正數(shù)”，如果數(shù)組內(nèi)出現(xiàn)了不連續(xù)，那么最小缺失正數(shù)的值必然小于數(shù)組長度）那么我只需要建立一個新的數(shù)組，然后把元素放到對應值作為下標的位置就好。
例如說nums[3] = 5，那我就讓新數(shù)組ans[4]=5。
這樣之后排出來的新數(shù)組算是部分排好序的，那再對這個新數(shù)組遍歷一遍就能知道答案。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int size = nums.size();
        vector<int> ans(size, 0);
        
        for(auto it = nums.begin(); it != nums.end(); it++){
            if(*it <= size && *it > 0)
                ans.at(*it-1) = *it;
        }
        
        int smallest = 1;
        for(auto it = ans.begin(); it != ans.end(); it++){
            if(*it == smallest)
                smallest++;
        }
        
        return smallest;
    }
};

這個解法的時間復雜度為O(n)，空間復雜度為O(n)。

交換（O(1)空間復雜度）

這題的要求其實是空間復雜度為常數(shù)。那么如果不能建立輔助數(shù)組，要重新對這個數(shù)組部分排序就只能用交換元素的方法了。
交換一次并不能達到效果，只要當前下標對應的值不是所需要的值，就必須一直交換。舉個例子：
數(shù)組[5 3 1 2 4]。
第一次交換:
[4 3 1 2 5]
此時nums(0)處的數(shù)字依然不是1（換言之，這個地方的元素并不“對”），我們要一直交換到它為1為止：
[2 3 1 4 5]
繼續(xù)：
[3 2 1 4 5]
[1 2 3 4 5]
這就完成了nums(0)處的交換，之后對nums(1)到nums(4)上都進行同樣的判斷。但由于此時整個數(shù)組已經(jīng)是完全排序好了，之后的下標處就不需要再交換了。
代碼如下：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int size = nums.size();
        
        for(auto it = nums.begin(); it != nums.end();){
            if(*it <= size && *it > 0 && *it == nums.at(*it-1))
                it++;
            else if(*it <= size && *it > 0)
                iter_swap(it, nums.begin()+*it-1);
            else{
                *it = 0;
                it++;
            }
        }
        
        int smallest = 1;
        for(auto it = nums.begin(); it != nums.end(); it++){
            if(*it == smallest)
                smallest++;
        }
        
        return smallest;
    }
};

理論上來說這個方法應該是比用輔助數(shù)組的方法慢的（時間復雜度嚴格說應該是O(3n)，輔助數(shù)組是O(2n)），實際上leetcode的運行結(jié)果也是如此。但是O(3n)=O(2n)=O(n)，再加上O(1)的空間復雜度，這個算法也可以說是最優(yōu)解之一。

#299 Bulls and Cows

題目地址：https://leetcode.com/problems/bulls-and-cows/

初見（Hash Table）

既然輸入只有0到9一共10個數(shù)字，那不用Hash Table做簡直是天理難容。把除了bull之外的情況都統(tǒng)計下來，只要雙方數(shù)字都不為0的情況下就代表出現(xiàn)了cow的情況，這時候取其中較小的計數(shù)作為cow。

class Solution {
public:
    string getHint(string secret, string guess) {
        vector<int> nums(10, 0);
        vector<int> numbulls(10, 0);
        int size = secret.size();
        int bulls = 0;
        int cows = 0;
        for(int ind = 0; ind < size; ind++){
            if(secret.at(ind) == guess.at(ind))
                bulls++;
            else{
                int digit = guess.at(ind) - '0';
                int digitbull = secret.at(ind) - '0';
                nums.at(digit)++;
                numbulls.at(digitbull)++;
            }
            
        }
        for(int ind = 0; ind < nums.size(); ind++){
            if(nums.at(ind) > 0 && numbulls.at(ind) > 0){
                cows += min(nums.at(ind), numbulls.at(ind));
            }
        }
        
        string answer;
        answer = to_string(bulls) + "A" + to_string(cows) + "B";
        return answer;
    }
};

實際上只需要遍歷數(shù)組一次（第二個for循環(huán)遍歷的是長度為10的定長數(shù)組），時間復雜度為O(n)。