2019-01-26 第二天(#189, #41, #299)

#189 Rotate Array

初见 (O(n^2)复杂度）

我觉得这个应该算是brute force。先用back()获取最后一个元素，用erase()擦除最后一个元素，再在数组头用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()这个函数在数组头插入的话时间复杂度是O(n）,那这么下来整体的时间复杂度就是O(n^2)。
我以为这个会超过时间限制，但是居然也打败了31.91%的人，可喜可贺可喜可贺。

辅助数组 （O(n)空间复杂度）

这个算是比较直观的解法了，具体而言就是把需要rotate的元素移出来存到另一个数组ans里，然后再把剩余元素push到ans中。这种方法出来的rotate元素会和所需要的刚好相反，可以翻转一下。

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版本。

三次翻转 (O(1)空间复杂度）

这个方法说实话我自己肯定想不出来，但是在网站的solution里面有，去YouTube看了看也是主流的方法之一，权当背下来吧。
这个方法说白了就是把整个数组分成两部分：需要rotate“走”的部分，和剩余的部分。
举个例子：
数组[1 2 3 4 5 6 7]，k = 3
那这个地方需要rotate走的就是[5 6 7]这一块，剩下的就是[1 2 3 4]；
先把所有的元素翻转过来：[7 6 5 4 3 2 1]
然后翻转rotate走的部分：[5 6 7 4 3 2 1]
最后翻转剩下部分：[5 6 7 1 2 3 4]
三次翻转就可以完成这个rotate的过程。
代码实现：

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()这个函数接受的第二个参数应该指向需要翻转元素的后一个位置。
这个算法的时间复杂度为O(n)，空间复杂度为O(1)（不需要占用额外空间）。

#41 First Missing Positive

题目地址：https://leetcode.com/problems/first-missing-positive/
这个题显然可以用sorting解决，但是题目要求O(n)的复杂度，就不放上来了。

辅助数组(O(n)空间复杂度）

解法的核心思想是"Put its number in its right place"。
对于这道题来说，不需要考虑负数，也不需要考虑值大于数组长度的数（因为要找的是“最小缺失正数”，如果数组内出现了不连续，那么最小缺失正数的值必然小于数组长度）那么我只需要建立一个新的数组，然后把元素放到对应值作为下标的位置就好。
例如说nums[3] = 5，那我就让新数组ans[4]=5。
这样之后排出来的新数组算是部分排好序的，那再对这个新数组遍历一遍就能知道答案。

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)空间复杂度）

这题的要求其实是空间复杂度为常数。那么如果不能建立辅助数组，要重新对这个数组部分排序就只能用交换元素的方法了。
交换一次并不能达到效果，只要当前下标对应的值不是所需要的值，就必须一直交换。举个例子：
数组[5 3 1 2 4]。
第一次交换:
[4 3 1 2 5]
此时nums(0)处的数字依然不是1（换言之，这个地方的元素并不“对”），我们要一直交换到它为1为止：
[2 3 1 4 5]
继续：
[3 2 1 4 5]
[1 2 3 4 5]
这就完成了nums(0)处的交换，之后对nums(1)到nums(4)上都进行同样的判断。但由于此时整个数组已经是完全排序好了，之后的下标处就不需要再交换了。
代码如下：

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;
    }
};

理论上来说这个方法应该是比用辅助数组的方法慢的（时间复杂度严格说应该是O(3n)，辅助数组是O(2n)），实际上leetcode的运行结果也是如此。但是O(3n)=O(2n)=O(n)，再加上O(1)的空间复杂度，这个算法也可以说是最优解之一。

#299 Bulls and Cows

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

初见（Hash Table）

既然输入只有0到9一共10个数字，那不用Hash Table做简直是天理难容。把除了bull之外的情况都统计下来，只要双方数字都不为0的情况下就代表出现了cow的情况，这时候取其中较小的计数作为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;
    }
};

实际上只需要遍历数组一次（第二个for循环遍历的是长度为10的定长数组），时间复杂度为O(n)。