LeetCode-Solution

By-YWG

按解题方法

Backtracking Questions

https://discuss.leetcode.com/topic/46161/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning

Array

1-Two Sum

1-直接搜索答案

//笨办法，直接搜索答案，O(n^2) 126ms, 30.94%
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i, j;
        int n = nums.size();
        vector<int> ans;
        for(i=0; i< n-1; i++){
            for(j=i+1; j<n; j++){
                if(nums[i]+nums[j] ==target){
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
            }
        }
    }
};

2-使用哈希表

用一个哈希表边走边记录，减少重复查询。

9ms， 80.97%
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //STL 中 unordered_map 对应哈希表 查找复杂度O（1）。
        unordered_map<int, int> h;
        vector<int> ans;
        for(int i=0; i<nums.size(); i++){
            int remain = target - nums[i];
            if(h.find(remain)!=h.end()){
                ans.push_back(i);
                ans.push_back(h[remain]);
                return ans;
            }
            else{
                h[nums[i]]=i;
            }
        }
    }
};

3-Fail失败的尝试

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        unordered_map<int, int> h;
        //先使用map存储index和值得映射，这里key不重复
        for(int i=0; i<nums.size(); i++){
            h[nums[i]]=i;
        }

        sort(nums.begin(), nums.end());
        int l=0, r=nums.size()-1; // left and right pointer.
        while(l<r){
            int sum = nums[l] + nums[r];
            if(sum==target){
                ans.push_back(h[nums[l]]);
                ans.push_back(h[nums[r]]);
                return ans;
            }
            else if(sum<target){
                l++;
            }
            else if(sum>target){
                r--;            
            }
        }
    }
};

11-Container With Most Water

这道题意思是从这组高度值里选出两个后，计算其能盛水的面积，其他的可以忽略。

1-Two Pointers

最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到左边大于右边为止就行了。

如果将较短的边向中间移后，新的边还更短一些，其实可以跳过，减少一些计算量

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size()-1;
        int area = 0;
        while(left<right){
            int current_height = min(height[left], height[right]), current_width = right-left;
            area = max(area, current_height*current_width);
            if(height[left]<height[right])
                left++;
            else
                right--;
        }
        return area;
    }
};

15

1-On^2

固定一个，变成2 Sum

注意优化代码，避免重复计算，

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3)
            return new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        Set<List<Integer>> tmpAns = new HashSet<>();
        Arrays.sort(nums);
        for(int a=0; a<nums.length-2; a++){
            if(a>0 && nums[a]==nums[a-1])
                continue;
            int remain = -nums[a];
            int b=a+1, c = nums.length-1;
            while (b<c){
                if(nums[b]+nums[c]<remain){
                    b++;
                }
                else if(nums[b]+nums[c]>remain){
                    c--;
                }
                else {
                    List<Integer> entry = new ArrayList<>();
                    entry.add(nums[a]);
                    entry.add(nums[b]);
                    entry.add(nums[c]);
                    tmpAns.add(entry);
                    while(b<c && nums[b]==nums[b+1])    
                        b++;
                    b++;
                    while(b<c && nums[c]==nums[c-1])
                        c--;
                    c--;
                }
            }
        }
        for(List<Integer> entry : tmpAns){
            ans.add(entry);
        }
        return ans;
    }
}

16-3Sum Closest

1-Two Pointers-O(n^2)

通过移动left和right尽量使diff为0

参考No.167Two Sum II

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n=nums.size(); //n>0
        int sum=nums[0]+nums[1]+nums[2], current_sum;
        int abs_min_diff = abs(target-sum), abs_current_diff;
        for(int i=0; i<n-2; i++){
            int left =i+1, right=n-1;
            while(left<right){
                current_sum = nums[i]+nums[left]+nums[right];
                abs_current_diff = abs(target-current_sum);
                if(abs_min_diff>abs_current_diff){
                    sum = current_sum;
                    abs_min_diff = abs_current_diff;
                }
                if(current_sum==target)
                    return current_sum;
                else if(current_sum<target)
                    left++;
                else 
                    right--;
            }
        }
        return sum;
    }
};

18

1-4-3-2sum

可以剪枝增加效率

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums.length<4)
            return ans;
        Arrays.sort(nums);
        for (int a=0; a<nums.length-3; a++){
            if (a>0 && nums[a]==nums[a-1])
                continue;
            for(int b=a+1; b<nums.length-2; b++){
                if (b>(a+1) && nums[b]==nums[b-1])
                    continue;
                int remain = target - nums[a] - nums[b];
                int c = b+1, d=nums.length-1;
                while (c<d){
                    if(nums[c]+nums[d]<remain)
                        c++;
                    else if(nums[c]+nums[d]>remain)
                        d--;
                    else {
                        ans.add(Arrays.asList(nums[a], nums[b], nums[c], nums[d]));
                        while (c<d && nums[c]==nums[c+1])
                            c++;
                        c++;
                        while (c<d && nums[d]==nums[d-1])
                            d--;
                        d--;
                    }
                }
            }
        }
        return ans;
    }
}

26-Remove Duplicates from Sorted Array

参考27

1-双指针操作

// 91.82%
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int index=0, val;
        if(nums.size()==0)
            return 0;
        else{
            val=nums[index];
            for(int i=0; i<nums.size(); i++){
                if(nums[i]!=val){
                    val = nums[i];
                    nums[++index]=nums[i];
                }
            }
            return (index+1);
        }
    }
};

//更清楚易懂
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        else{
            int pointer_1=0, pointer_2;
            for(pointer_2=1; pointer_2<nums.size(); pointer_2++){
                if(nums[pointer_2]!=nums[pointer_1]){
                    nums[++pointer_1]=nums[pointer_2];
                }
            }
            return pointer_1+1;
        }
    }
};

27-Remove Element

1-需要移动每个元素

//8.23%
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index=0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i]!=val){
                nums[index++]=nums[i];
            }
        }
        return index;
    }
};

2-

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0, n=nums.size();
        while(i<n){
            if(nums[i]==val){
                nums[i]=nums[n-1];
                n--;
            }
            else{
                i++;   
            }
        }
        return i;
    }
};

31

http://bangbingsyb.blogspot.com/2014/11/leetcode-next-permutation.html

import java.util.Arrays;

class Solution {
    public void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    public void reverse(int[] a, int i, int j){
        while(i<j)
            swap(a, i++, j--);
    }
    public  void nextPermutation(int[] nums) {
        int numsSize = nums.length;
        if(numsSize<2)
            return;
        int i = numsSize-2;

        while(i>=0 && nums[i]>=nums[i+1])
            i--;

        if(i<0){
            reverse(nums, 0, numsSize-1);
            return;
        }
        else{
            int j = i+1;
            while(j<numsSize && nums[j]>nums[i])
                j++;
            j--;
            swap(nums, i, j);
            reverse(nums, i+1, numsSize-1);
        }
    }
}

33-Search in Rotated Sorted Array

1-Binary Search-写的乱，需要整理。

同No.153, 第一次写的比较乱。

思路：

左右两部分总有一个是有序的。先判断哪一部分是有序的。再判断target是否在有序的那一部分，是的话搜索这一部分。不是的话继续搜素另一部分。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size()==0)
            return -1;
        int left = 0, right = nums.size()-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]<nums[right]){
                if(nums[mid]>target || nums[right]<target)
                    right = mid-1;
                else{
                    int new_left = mid, new_right=right;
                    while(new_left<=new_right){
                        int new_mid = new_left+(new_right-new_left)/2;
                        if(nums[new_mid]<target)
                            new_left = new_mid+1;
                        else if(nums[new_mid]>target)
                            new_right = new_mid-1;
                        else 
                            return new_mid;
                    }
                    return -1;
                }
            }
            else if(nums[mid]>nums[right]){
                if(nums[mid]<target || nums[left]>target)
                    left = mid+1;
                else{
                    int new_left = left, new_right=mid;
                    while(new_left<=new_right){
                        int new_mid = new_left+(new_right-new_left)/2;
                        if(nums[new_mid]<target)
                            new_left = new_mid+1;
                        else if(nums[new_mid]>target)
                            new_right = new_mid-1;
                        else 
                            return new_mid;
                    }
                    return -1;
                }
            }
            else{
                if(nums[mid]==target)
                    return mid;
                else 
                    return -1;
            }
        }
        return -1;
    }
};

//整理后的新代码
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0)
            return -1;
        int left=0, right=n-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(target==nums[mid]){
                return mid;
            }
            //[left, mid] are sorted.
            else if(nums[left]<=nums[mid]){
                if(target<nums[mid] && target>=nums[left])
                    right = mid-1;
                else
                    left = mid+1;
            }
            //[mid, right] are sorted
            else{
                if(target>nums[mid] && target<=nums[right])
                    left = mid+1;
                else 
                    right = mid-1;
            }
        }
        return -1;
    }
};

2-Binary Search

不是特别容易理解。
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0)
            return -1;
        int left=0, right=n-1;
        // find the index of the smallest value using binary search.
        // Loop will terminate since mid < right, and left or right will shrink by at least 1.
        // Proof by contradiction that mid < right: if mid==right, then left==right and loop would have been terminated.
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]>nums[right])
                left = mid+1;
            else
                right = mid;
        }
        // left==right is the index of the smallest value and also the number of places rotated.

        int min_value_index = left;
        left=0, right=n-1;
        // The usual binary search and accounting for rotation.

        while(left<=right){
            int mid = left+(right-left)/2;
            int real_mid = (mid+min_value_index)%n;
            if(nums[real_mid]<target)
                left = mid+1;
            else if(nums[real_mid]>target)
                right = mid-1;
            else
                return real_mid;
        }
        return -1;
    }
};

//和上面思路相差不大，但是在第二次二分查找时根据nums[n-1]与target的关系确定是在哪一部分进行二分查找。
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0)
            return -1;
        int left=0, right=n-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]>nums[right])
                left = mid+1;
            else
                right = mid;
        }

        int min_value_index = left;

        if(target ==  nums[min_value_index])
            return min_value_index;

        left = (target<=nums[n-1]) ? min_value_index : 0;
        right = (target>nums[n-1]) ? min_value_index-1 : n-1;

        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]<target)
                left = mid+1;
            else if(nums[mid]>target)
                right = mid-1;
            else
                return mid;
        }
        return -1;
    }
};

34

import com.sun.org.apache.regexp.internal.RE;

class Solution {
    public int leftBinarySearch(int[] nums, int val){
        int left = 0, right = nums.length-1;
        while (left<=right){
            int mid = (right-left)/2 + left;
            if (nums[mid]>=val){
                right = mid-1;
            }
            else if(nums[mid]<val) {
                left = mid+1;
            }
        }
        if (right+1 <= nums.length-1 && nums[right+1]==val){
            return right+1;
        }
        else
            return -1;
    }
    public int rightBinarySearch(int[] nums, int val){
        int left = 0, right = nums.length-1;
        while (left<=right){
            int mid = (right-left)/2 + left;
            if (nums[mid]>val){
                right = mid-1;
            }
            else if(nums[mid]<=val) {
                left = mid+1;
            }
        }
        if (left-1>=0 && nums[left-1]==val){
            return left-1;
        }
        else
            return -1;
    }
    public int[] searchRange(int[] nums, int target) {
        if(nums.length<1)
            return new int[] {-1, -1};
        int left = leftBinarySearch(nums, target);
        int right = rightBinarySearch(nums, target);
        if (left==-1 || right==-1)
            return new int[] {-1, -1};
        else
            return new int[] {left, right};
    }
}

35-Search Insert Position

1-Map+顺序查找-O（n）

//9ms, 8.95%
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        unordered_map<int, int> h;
        for(int i=0; i<nums.size();i++){
            h[nums[i]]=i;
        }
        if(h.find(target)!=h.end()){
            return h[target];
        }
        else{
            for(int i=0; i<nums.size();i++){
                if(nums[i]>target){
                    return i;
                }
            }
            return nums.size();
        }
    }
};

Oh, Crap.竟然用map，已经排好序，二分查找。扫一遍也可以啊。 对上一个的更改。扫一遍

//6ms, 35.48%
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i=0; i<nums.size();i++){
            if(nums[i]==target){
                return i;
            }
            if(nums[i]>target){
                return i;
            }
        }
        return nums.size();
    }
};

3-二分查找

注意确定边界条件

6ms 36.06%
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l=0, r=nums.size()-1, m; //left, right, middle
        while(l<=r){
            m = (l+r)/2;
            if(nums[m]==target){
                return m; //可以在最后返回
            }
            else if(nums[m]>target){
                r=m-1;
            }
            else{
                l=m+1;
            }
        }
        // (1) At this point, low > high. That is, low >= high+1
        // (2) From the invariant, we know that the index is between [low, high+1], so low <= high+1. Follwing from (1), now we know low == high+1.
        // (3) Following from (2), the index is between [low, high+1] = [low, low], which means that low is the desired index
        // Therefore, we return low as the answer. You can also return high+1 as the result, since low == high+1
        return l;
    }
};

39-Combination Sum

1-Backtracking

先将数组排序，枚举所有可能组合。递归求解

因为我们可以任意组合任意多个数，看其和是否是目标数，而且还要返回所有可能的组合，所以我们必须遍历所有可能性才能求解。为了避免重复遍历，我们搜索的时候只搜索当前或之后的数，而不再搜索前面的数。因为我们先将较小的数计算完，所以到较大的数时我们就不用再考虑有较小的数的情况了。这题是非常基本且典型的深度优先搜索并返回路径的题。本题需要先排序，不然过不了Leetcode。

class Solution {
public:
    void csombination_sum(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combination, int begin){
        if(!target){
            ans.push_back(combination);
            return;
        }
          //因为每个元素可以使用多次，所以循环的是元素，
        for(int i=begin; i!=candidates.size() && target>=candidates[i]; i++){
            combination.push_back(candidates[i]);
            combination_sum(candidates, target-candidates[i], ans, combination, i);
            combination.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //排序，避免重复搜素
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> combination;
        combination_sum(candidates, target, ans, combination, 0);
        return ans;
    }
};

2-DP

This is just like a coin change/knapsack problem. We need to create a vector of the size of target. and for each o(1)...o(target) we get the values. and if in between we find any sum == target, add that into the result

Hnn, I use the same idea as you did. I can help illustrate the idea.

Thinking about there is an opt[] array, each element in the array is a vector>. We do DP from opt[0] to opt[target].

// base case

opt[0] = [[]]

// iteration

opt[i] =

1. add candidates[j] to each list in opt[i-candidates[j]] if i > candidates[j] .Add each list to opt[i]
2. create candidates[j] as a new vector if i == candidates[j] .Add this list to opt[i]

应该比较耗内存

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector< vector< vector<int> > > combinations(target + 1, vector<vector<int>>());
        combinations[0].push_back(vector<int>());
        for (auto& score : candidates)
            for (int j = score; j <= target; j++){
                auto sls = combinations[j - score];
                if (sls.size() > 0) {
                    for (auto& s : sls)
                        s.push_back(score);
                    combinations[j].insert(combinations[j].end(), sls.begin(), sls.end());
                }
            }
        return combinations[target];
    }
};

40-Combination Sum II

1-DFS

注意：

1. 元素只能用一次
2. candidate中有重复元素。

其他同No.39

class Solution {
public:
    void solve(vector<int>& candidates, vector<vector<int>>& ans, vector<int>&combination, int target, int begin_index){
       if(!target){
            ans.push_back(combination);
       } 
       else{
            for(int i=begin_index; i<candidates.size() && candidates[i]<=target; i++){
                if(i>begin_index && candidates[i]==candidates[i-1])
                    continue;
                else{
                    combination.push_back(candidates[i]);
                    solve(candidates, ans, combination, target-candidates[i], i+1);
                    combination.pop_back();
                }
            }
       }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> combination;
        solve(candidates, ans, combination, target, 0);
        return ans;
    }
};

42-Trapping Rain Water

1-Fail-TLE 314 / 315 test cases passed.

class Solution {
public:
    int trap(vector<int>& height) {
        int m = height.size(), n=0, sum=0;
        for(int i=0; i<m; i++)
            n = max(n, height[i]);

        for(int i=0; i<m; i++){
            for(int j=1; j<=n; j++){
                if(j>height[i]){
                    int is_left_wall=0, is_right_wall=0;
                    for(int x=i-1; x>=0; x--){
                        if(height[x]>=j){
                            is_left_wall=1;
                            break;
                        } 
                    }
                    for(int x=i+1; x<m && is_left_wall; x++){
                        if(height[x]>=j){
                            is_right_wall=1;
                            break;
                        }
                    }
                    if(is_left_wall==1 && is_right_wall==1)
                        sum++;
                }
            }
        }
        return sum;
    }
};

2-O(2n)

对于 a[i]，所能存储的最多的水取决于i之前最高的高度和之后最高的高度，如果min(left, right) > a[i], 那么差即为所能存取的水量。

先从左到右遍历计算每个元素的left_max_height, 再从右向左计算right_max_heigh, 第二遍遍历同时可以进行计算，不需要多余的空间。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), sum =0;
        if(n==0)
            return 0;
        int left_max_height[n];
        left_max_height[0]=0;
        int max_height=0;
        for(int i=1; i<n; i++){
            max_height = max(max_height, height[i-1]);
            left_max_height[i]=max_height;
        }
        max_height=0;
        for(int i=n-2; i>=0; i--){
            max_height = max(max_height, height[i+1]);
            int container = min(max_height, left_max_height[i]);
            if(container > height[i])
                sum = sum + container - height[i];
        }
        return sum;
    }
};

3-O(n)

用两个指针分别指向左边和右边，两板之间所能装水的高度就是短板的高度。

如果左边是短板，移动左边指针。

​ 如果移动后的指针>=短板高度，那么该位置无法装水，继续寻找新的短板高度。

​ 如果移动后指针所指高度<短板高度，装入相应的水，继续移动，看能否继续装水。

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2)
            return 0;
        int  left=0, right = height.size()-1, sum =0;
        while(left<right){
            int min_height = min(height[left], height[right]);
            if(min_height == height[left]){
                left++;
                while(left<right && height[left]<min_height)
                    sum = sum + min_height - height[left++];
            }
            else{
                right--;
                while(left<right && height[right]<min_height)
                    sum = sum + min_height - height[right--];
            }
        }
        return sum;
    }
};

4-Stack-O（n）

https://discuss.leetcode.com/topic/4939/a-stack-based-solution-for-reference-inspired-by-histogram

一层一层算

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> s;
        int max_water(0);
        int i(0);
        while (i<height.size()) {
            if (s.empty()||height[i]<=height[s.top()]) {
                s.push(i++);
            } else {
                int bot=height[s.top()];
                s.pop();
                max_water+=s.empty()?0:((min(height[i],height[s.top()])-bot)*(i-s.top()-1));
            }
        }
        return max_water;
    }
};

48-Rotate Image

1-两次变换

先沿对角线旋转一次，再沿y轴中线旋转一次即可

还有一种解法，首先以从对角线为轴翻转，然后再以x轴中线上下翻转即可得到结果，如下图所示(其中蓝色数字表示翻转轴)：

1 2 3　　　 　　 9 6 3　　　　　 7 4 1

4 5 6　　-->　　 8 5 2　　 --> 　 8 5 2　　

7 8 9 　　　 　　7 4 1　　　　　 9 6 3

class Solution {
public:
    void transform_a(vector<vector<int>>& matrix){
        int n = matrix.size();
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
    void transform_b(vector<vector<int>>& matrix){
        int n = matrix.size();
        int mid = n/2;
        for(int i=0; i<n; i++){
            for(int j=0; j<mid; j++){
                swap(matrix[i][j], matrix[i][n-1-j]);
            }
        }
    }
    void rotate(vector<vector<int>>& matrix) {
        transform_a(matrix);
        transform_b(matrix);
    }
};

2-

对于90度的翻转有很多方法，一步或多步都可以解，我们先来看一种直接的方法，对于当前位置，计算旋转后的新位置，然后再计算下一个新位置，第四个位置又变成当前位置了，所以这个方法每次循环换四个数字，如下所示：

1 2 3 7 2 1 7 4 1

4 5 6 --> 4 5 6　　 --> 　 8 5 2　　

7 8 9 9 8 3　　　　　 9 6 3

class Solution {
public:

    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i=0; i<n/2; i++){
            for(int j=i; j<n-1-i; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = tmp;
            }
        }
    }
};

53-Maximum Subarray

1-DP

同 No.121

每一步，我们维护两个变量，一个是全局最优，就是到当前元素为止最优的解是，一个是局部最优，就是必须包含当前元素的最优的解。接下来说说动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。假设我们已知第i步的global[i]（全局最优）和local[i]（局部最优），那么第i+1步的表达式是： local[i+1]=Math.max(A[i], local[i]+A[i])，就是局部最优是一定要包含当前元素，所以不然就是上一步的局部最优local[i]+当前元素A[i]（因为local[i]一定包含第i个元素，所以不违反条件），但是如果local[i]是负的，那么加上他就不如不需要的，所以不然就是直接用A[i]； global[i+1]=Math(local[i+1],global[i])，有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。

//12.24%
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int current_max = nums[0], max_sum = nums[0];
        for(int i=1; i<nums.size(); i++){
            current_max = max(nums[i], current_max+nums[i]);
            max_sum = max(max_sum, current_max);
        }
        return max_sum;
    }
};

2-Divide&Conquer

假设数组A[left, right]存在最大值区间i, j，以mid = (left + right)/2 分界，无非以下三种情况：

subarray A[i,..j] is (1) Entirely in A[low,mid-1] (2) Entirely in A[mid+1,high] (3) Across mid 对于(1) and (2)，直接递归求解即可，对于(3)，则需要以min为中心，向左及向右扫描求最大值，意味着在A[left, Mid]区间中找出A[i..mid], 而在A[mid+1, right]中找出A[mid+1..j]，两者加和即为(3)的解。

参考Data Structures and Algorithm Analysis in C写的,一点点区别在于全是负数的时候仍然至少要取一个元素.

//24.55%
class Solution {
public:
    int max_3(int a, int b, int c){
        a = max(a, b);
        a = max(a, c);
        return a;
    }
    int max_sub_sum(vector<int>&nums, int left, int right){
        int max_left_sum, max_right_sum;
        int max_left_border_sum, max_right_border_sum;
        int left_border_sum, right_border_sum;
        int middle, i;

        if(left==right){
            if(nums[left]>0)
                return nums[left];
            else{
                return 0;
            }
        }
        middle = left + (right-left)/2;
        max_left_sum = max_sub_sum(nums, left, middle);
        max_right_sum = max_sub_sum(nums, middle+1, right);

        max_left_border_sum = 0;
        left_border_sum = 0;
        for(i=middle; i>=left; i--){
            left_border_sum += nums[i];
            max_left_border_sum = max(left_border_sum, max_left_border_sum);
        }

        max_right_border_sum = 0;
        right_border_sum = 0;
        for(i=middle+1; i<=right; i++){
            right_border_sum += nums[i];
            max_right_border_sum = max(right_border_sum, max_right_border_sum);
        }

        return max_3(max_left_sum, max_right_sum, max_left_border_sum+max_right_border_sum);
    }
    int maxSubArray(vector<int>& nums) {
        //Pre_Condition: at least one element, or nums.size()-1 will error.
        int res=max_sub_sum(nums, 0, nums.size()-1);
        if(res==0){
            int tmp=nums[0];
            for(int i=1; i<nums.size(); i++){
                tmp=max(tmp, nums[i]);   
            }
            res = tmp;
        }
        return res;
    }
};

另一种写法，更好看一点

class Solution {
public:
    int max_sub_sum(vector<int>&nums, int left, int right){
        if(left>right){
            return INT_MIN;
        }
        int middle = left + (right-left)/2;

        int max_left_sum = max_sub_sum(nums, left, middle-1);
        int max_right_sum = max_sub_sum(nums, middle+1, right);

        int max_left_border_sum = 0;
        int left_border_sum = 0;
        for(int i=middle-1; i>=left; i--){
            left_border_sum += nums[i];
            max_left_border_sum = max(left_border_sum, max_left_border_sum);
        }

        int max_right_border_sum = 0;
        int right_border_sum = 0;
        for(int i=middle+1; i<=right; i++){
            right_border_sum += nums[i];
            max_right_border_sum = max(right_border_sum, max_right_border_sum);
        }

        return max(max(max_left_sum, max_right_sum), max_left_border_sum+nums[middle]+max_right_border_sum);
    }
    int maxSubArray(vector<int>& nums) {
        int n = nums.size()-1;
        return max_sub_sum(nums, 0, n);
    }
};

54

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> path = new ArrayList<>();
        if(matrix.length<1 || matrix[0].length<1){
            return path;
        }
        int rowStart = 0;
        int rowEnd = matrix.length-1;
        int colStart = 0;
        int colEnd = matrix[0].length-1;
        while(true){
            //right
            for(int j = colStart; j <= colEnd; j++){
                path.add(matrix[rowStart][j]);
            }
            rowStart++;
            if(rowStart > rowEnd)
                break;
            //down
            for(int i=rowStart; i<= rowEnd; i++){
                path.add(matrix[i][colEnd]);
            }
            colEnd--;
            if(colStart > colEnd)
                break;
            //left
            for(int j=colEnd; j>=colStart; j--){
                path.add(matrix[rowEnd][j]);
            }
            rowEnd--;
            if(rowStart > rowEnd)
                break;
            //up
            for(int i=rowEnd; i>=rowStart; i--){
                path.add(matrix[i][colStart]);
            }
            colStart++;
            if(colStart > colEnd)
                break;
        }
        return path;
    }
}