Leetcode second round:9/3( all done!!)

today‘s mission: 53 - 73(the end)  🐑🐑🐑

53： maximum subarray
两个Method: 分治法recursionO(nlogn)， 一维dpO(N)，正增益，负增益
一维dp：
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int local = 0;
        int gmax = nums[0];
        for (int i= 0; i < nums.size(); i++) {
            local = max(nums[i], nums[i] + local); //local 表示包含当前元素的最大值
            gmax = max(gmax, local);
        }
        return gmax;
    }
};
54： spiral matrix

55:   length of last word

这个题目可以从后面往前扫，这样做肯定是比从前面往后扫要快很多，先过滤掉末尾的空格，然后再计算第一个word的长度。

61. rotate list
update的solution, form a loop, use only one helper pointer
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k == 0) return head;
        ListNode* fast = head;
        int count = 1;
        while(fast->next) {
            fast = fast->next;
            count++;
        }
        k = k % count;
        if (k == 0) return head;
        fast->next = head;
        int step = count - k;
        while (step > 0) {
            fast = fast->next;
            step--;
        }
        head = fast->next;
        fast->next = NULL;
        return head;
    }
};

62: unique path
63: unique path II
64: minimal path sum
这三个题目都是很基础的dp题，之前解题都会用 二维数组 解决二维dp的问题，但是作为dp来说最能优化的就是它的空间了， 这三个题目我们都可以用滚动数组来解决。 即用一个动态的数组，每计算一行或者一列之后，数组里面的值都是相应更新。

66 ：plus one
最高位在vector的头，所以需要从vector的尾巴加起，这个题目要注意的是当vector的头的值为9的时候，是需要从新开辟个数组在前面加1的。但是这样做不管情况好坏，时间复杂度都是O(n), 但是大部分情况下，只需要对一位加1就可以了啊！这样做时间复杂度超级低！

这个题的点在于： 当所有位都是9的时候，需要开辟一个新的vecotor，首位是1，其他位是0。
时间复杂度： O（n）空间复杂度: 一般情况下O（1），最差情况下O（n）
  vector<int> plusOne(vector<int>& digits) {
        if (digits.size() == 0) return digits;
        int i = 0;
        for (i = digits.size()-1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            } else {
                digits[i] = 0;
            }
        }
        if (i < 0 ) {
            vector<int> tmp(digits.size()+1, 0);
            tmp[0] = 1;
            return tmp;
        }
    }
67:   add binary
这个题目跟上面那个plus one的题目解法是一样的，就是按位往前加， 维持一个进位 cnt， 在开始的时候最好让其中一个string 作为最终数组，这样的话，一开始就需要把两个string 的大小统一。这个题目之前的有一个版本是对两个linklist进行加，其实做法是一样的，就只是在细节处理上不同。
follow up: 如果是数组怎么处理？ 其实是一样的，只是数组最后要重新开辟一个n+1的数组
                  如果是linklist怎么处理？ 其实也是一样的，只是linklist的头前面要加一个新的节点。
class Solution {
public:
    string addBinary(string a, string b) {
        if (a.size() == 0) return b;
        if (b.size() == 0) return a;
        if (a.size() < b.size()) return addBinary(b, a);
        int i = a.size()-1;
        int j = b.size()-1;
        int cnt = 0;
        while (i >= 0 || j >= 0) {
            if (j >= 0 ) {
                int tmp = (a[i] - '0' + b[j] - '0');
                a[i] = ((tmp + cnt)%2 + '0');
                cnt = (tmp + cnt)/2;
                i--;
                j--;
            } else {
                int tmp = a[i] - '0';
                a[i] = (tmp+cnt)%2 + '0';
                cnt = (tmp + cnt)/2;
                i--;
            }
        }
        if (cnt == 1) {
            char c = '1';
            a = c + a;
        }
        return a;
    }
};
68:

73: set matrix zeros
time complexity: O(n^2), space complexity: O(1)
4步法， 利用本身数组的第一行和第一列作为一个mark,
step1: 两个标记位，看第一行有没有0， set flag1; 看第一列有没有0， set flag2
step2:  对每一个元素进行扫描，遇到有0的元素，set行， 列为一个0；
step3:  扫描第一行和第一列，将相应标记位的对应行和列置为0
step4：看看第一行和第一列需不需要置为0
74：search a 2D matrix
search a 2D matrixII的简化版，两种方法都可以做，时间复杂度都是一样的， O(logm + logn)