56-Merge Intervals

1-

首先按照start的大小来给所有interval排序，start小的在前。然后扫描逐个插入结果。如果发现当前interval a和结果中最后一个插入的interval b不重合，则插入a到b的后面；反之如果重合，则将a合并到b中。注意要给object排序需要定义一个compare structure作为sort函数的额外参数。

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool compare(Interval a, Interval b){
        return a.start < b.start;
    }
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        vector<Interval> result;
        for(int i=0; i<intervals.size(); i++){
            //not overlap
            if(result.empty()|| result.back().end <intervals[i].start) 
                result.push_back(intervals[i]);
            else
                result.back().end = max(result.back().end, intervals[i].end);
        }
        return result;
    }
};

2-

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        int n = intervals.size();
        if(n==0)
            return intervals;

        int starts[n], ends[n];
        for(int i=0; i<n; i++){
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        sort(starts, starts+n);
        sort(ends, ends+n);

        vector<Interval> result;
        // j is start of interval.
        for(int i=0, j=0; i<n; i++){
            if(i==n-1 || starts[i+1]>ends[i]){
                result.push_back(Interval(starts[j], ends[i]));
                j=i+1;
            }
        }
        return result;
    }
};

59-Spiral Matrix II

1-

分层，然后按照上右下左的顺序放入数组中。每个元素只访问一次，时间复杂度是O(n^2)

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 1));
        int cnt = 1, sum = n*n;
        int top = 0, bottom = n-1, left = 0, right = n-1;
        while(left<=right && top<=bottom){
            for(int j=left; j<=right; j++)
                ans[top][j] = cnt++;
            for(int i=top+1; i<=bottom; i++)
                ans[i][right] = cnt++;
            for(int j=right-1; j>=left; j--)
                ans[bottom][j] = cnt++;
            for(int i=bottom-1; i>top; i--)
                ans[i][left] = cnt++;
            left++;
            right--;
            top++;
            bottom--;
        }

        return ans;
    }
};

62-Unique Paths

1-DP

改进：可以初始化所有的元素为1，避免最开始两个for循环

对空间进行优化

class Solution {
public:
    int uniquePaths(int m, int n) {
        int result[m][n];
        memset(result, 0, sizeof(result));
        for(int i=0; i<m; i++)
            result[i][0]=1;
        for(int i=0; i<n; i++)
            result[0][i]=1;
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                result[i][j] = result[i-1][j] + result[i][j-1];
            }
        }
        return result[m-1][n-1];
    }
};

//优化空间使用
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> ans(n, 1);
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                ans[j] = ans[j-1]+ans[j];
            }
        }
        return ans[n-1];
    }
};

2-计算组合数

出现问题：

1. 溢出
2. 边乘边除不准
3. 边界情况未考虑

class Solution {
public:
    //求组合数
    int cnm(int m, int n){
        long long ans=1;
        if(m+m>n)
            m = n-m;
        for(int i=0; i<m; i++, n--)
            ans *= n;
        for(int i=1; i<=m; i++)
            ans /= i;
        return ans;
    }
    int uniquePaths(int m, int n) {
        if(m==1 || n==1)
            return 1;
        else
            return cnm(m-1, m+n-2);
    }
};

63-Unique Paths II

1-DP

滚动数组

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n=obstacleGrid[0].size();
        if( m==0 || obstacleGrid[0][0]==1)
            return 0;
        vector<int> ans(n, 0);
        ans[0]=1;
        for(int j=1; j<n; j++){
            if(obstacleGrid[0][j]==1 || ans[j-1]==0)
                ans[j]=0;
            else
                ans[j]=1;
        }
        for(int i=1; i<m; i++){
            if(obstacleGrid[i][0]==1 || ans[0]==0)
                ans[0]=0;
            else
                ans[0]=1;
            for(int j=1; j<n; j++){
                if(obstacleGrid[i][j]==1)
                    ans[j]=0;
                else{
                    ans[j]+=ans[j-1];
                }
            }
        }
        return ans[n-1];
    }
};

64-Minimum Path Sum

1-DP

同No.62

可以优化空间复杂度少一维

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<vector<int>> ans = grid;
        int m = grid.size(), n = grid[0].size();
        for(int i=1; i<m; i++){
            ans[i][0] += ans[i-1][0];
        }
        for(int j=1; j<n; j++){
            ans[0][j] += ans[0][j-1];
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                ans[i][j] += min(ans[i-1][j], ans[i][j-1]);
            }
        }
        return ans[m-1][n-1];
    }
};

66-Plus One

1-模拟四则运算，注意[9]的处理。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n=digits.size();
        digits[n-1]++;
        int is_carry=0;
        for(int i=n-1; i>0; i--){
            if(digits[i]==10){
                digits[i]=0;
                is_carry=1;
            }
            if(is_carry){
                digits[i-1]++;
                is_carry=0;
            }
        }
        if(digits[0]==10){
            digits[0]=0;
            digits.insert(digits.begin(),1);
        }
        return digits;
    }
};

2-另一种更精简的写法

将一个数字的每个位上的数字分别存到一个一维向量中，最高位在最开头，我们需要给这个数字加一，即在末尾数字加一，如果末尾数字是9，那么则会有进位问题，而如果前面位上的数字仍为9，则需要继续向前进位。具体算法如下：首先判断最后一位是否为9，若不是，直接加一返回，若是，则该位赋0，再继续查前一位，同样的方法，知道查完第一位。如果第一位原本为9，加一后会产生新的一位，那么最后要做的是，查运算完的第一位是否为0，如果是，则在最前头加一个1。代码如下：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i=digits.size()-1; i>=0; i--){
            if(digits[i]==9){
                digits[i]=0;
            }
            else{
                digits[i]++;
                return digits;
            }
        }
        if(digits[0]==0){
            digits.insert(digits.begin(),1);
            return digits;
        }
    }
};

75-

1-Counting sort

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cnt_0=0, cnt_1=0, cnt_2=0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i]==0)
                cnt_0++;
            else if(nums[i]==1)
                cnt_1++;
            else
                cnt_2++;
        }
        for(int i=0; i<cnt_0; i++)
            nums[i]=0;
        for(int i=cnt_0; i<cnt_0+cnt_1; i++)
            nums[i]=1;
        for(int i=cnt_0+cnt_1; i<nums.size(); i++)
            nums[i]=2;
    }   
};

2-Two Pointers

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red_index=0, blue_index = nums.size()-1;
        int i=0;
        while(i<=blue_index){
            if(nums[i]==0){
                swap(nums[red_index++], nums[i++]);
            }
            else if(nums[i]==2){
                swap(nums[blue_index--], nums[i]);
            }
            else
                i++;
        }
    }
};

73-Set Matrix Zeroes

1-O(mn)-O(1)

所需要的信息是知道哪些行、哪些列需要被重置为零。因为题目需要O（1）的空间复杂度。所以我将第一行、第一列用来标记这一行、列是否需要全部置为零。最后用两个变量is_first_row_zero, is_first_col_zero标记首行、首列是否需要置为零。

最后根据标记信息设置数组即可。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.size()<1 || matrix[0].size()<1)
            return;
        //0-第一行/列不存在0, 1-存在0
        int is_first_row_zero=0, is_first_col_zero=0;
        int m = matrix.size(), n = matrix[0].size();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i!=0 && j!=0 && matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
                else if(matrix[i][j]==0){
                    if(i==0)
                        is_first_row_zero=1;
                    if(j==0)
                        is_first_col_zero=1;
                }
            }
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[0][j]==0 || matrix[i][0]==0){
                    matrix[i][j]=0;
                }
            }
        }
        for(int i=0; is_first_col_zero && i<m; i++)
            matrix[i][0]=0;
        for(int j=0; is_first_row_zero && j<n; j++)
            matrix[0][j]=0;
    }
};

74-Search a 2D Matrix

1-Binary Search

写的思路比较乱。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(m<1)
            return false;
        int n = matrix[0].size();
        if(n<1)
            return false;
        int row_left=0, row_right=n-1;
        int col_top=0, col_bottem=m-1;

        while(col_top<col_bottem){
            int mid = col_top + (col_bottem-col_top)/2;
            if(matrix[mid][0]>target)
                col_bottem=mid-1;
            else if(matrix[mid][n-1]<target)
                col_top = mid+1;
            else {
                col_top = mid;
                col_bottem = mid;
            }
        }
        while(row_left<=row_right){
            int mid = row_left + (row_right-row_left)/2;
            if(matrix[col_top][mid]<target)
                row_left = mid + 1;
            else if(matrix[col_top][mid]>target)
                row_right = mid -1;
            else 
                return true;
        }
        return false;
    }
};

//重新整理后代码
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0 || matrix[0].size()==0)
            return false;
        int left = 0, right = matrix.size()-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(matrix[mid][0]==target)
                return true;
            else if(matrix[mid][0]>target)
                right = mid-1;
            else 
                left = mid+1;
        }
        // row (right, m]>target
        int row = right;
        if(row<0)
            return false;
        left = 0, right = matrix[0].size()-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(matrix[row][mid]==target)
                return true;
            else if(matrix[row][mid]<target)
                left = mid+1;
            else
                right = mid-1;
        }
        return false;
    }
};

Use binary search.

n m matrix convert to an array => matrix[x][y] => a[x m + y]

an array convert to n * m matrix => a[x] =>matrix[x / m][x % m];

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()<1 || matrix[0].size()<1)
            return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int left =0, right = m*n-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(matrix[mid/n][mid%n]<target)
                left = mid+1;
            else if(matrix[mid/n][mid%n]>target)
                right = mid-1;
            else
                return true;
        }
        return false;
    }
};

78-Subsets

1-DFS

同Combination Sum 系列O($2^{n}$)

class Solution {
public:
    void solve(vector<vector<int>>& ans, vector<int>& subset, vector<int>& nums, int begin_index, int cnt){
        if(cnt==0){
            ans.push_back(subset);
            return ;
        }
        else{
           for(int i=begin_index; i<nums.size(); i++){
                subset.push_back(nums[i]);
                solve(ans, subset, nums, i+1, cnt-1);
                subset.pop_back();
           } 
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> subset;
        ans.push_back(vector<int>());
        for(int i=1; i<=nums.size(); i++){
            solve(ans, subset, nums, 0, i);
        }
        return ans;
    }
};

/*排序复杂度O(nlogn), 所有状态数O(2^n),生成一个状态O(1),总复杂度O（2^n）
子集类问题类似Combination，以输入数组[1, 2, 3]分析，根据题意，最终返回结果中子集类的元素应该按照升序排列，故首先需要对原数组进行排序。题目的第二点要求是子集不能重复，至此原题即转化为数学中的组合问题。我们首先尝试使用 DFS 进行求解，大致步骤如下：

[1] -> [1, 2] -> [1, 2, 3]
[2] -> [2, 3]
[3]
*/
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.empty()) 
            return result;
        sort(nums.begin(), nums.end());
        vector<int> subset;
        dfs(nums, 0, subset, result);

        return result;
    }
private:
    void dfs(vector<int>& nums, int pos, vector<int>& subset, vector<vector<int>>& result){
        result.push_back(subset);

        for(int i=pos; i<nums.size(); i++){
            subset.push_back(nums[i]);
            dfs(nums, i+1, subset, result);
            subset.pop_back();
        }
    }
};

以数组[1, 2, 3]进行分析。下图所示为list及result动态变化的过程，箭头向下表示list.add及result.add操作，箭头向上表示list.remove操作。

2-复制数组，为每个subset逐个添加当前元素

添加数字构建subset

起始subset集为：[] 添加S0后为：[], [S0] 添加S1后为：[], [S0], [S1], [S0, S1] 添加S2后为：[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2] 红色subset为每次新增的。显然规律为添加Si后，新增的subset为克隆现有的所有subset，并在它们后面都加上Si。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> subset;
        result.push_back(subset);
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size(); i++){
            int n = result.size();
            for(int j=0; j<n; j++){
                subset = result[j];
                subset.push_back(nums[i]);
                result.push_back(subset);
            }
        }
        return result;
    }
};

3-Bit manipulation

由于S[0: n-1]组成的每一个subset，可以看成是对是否包含S[i]的取舍。S[i]只有两种状态，包含在特定subset内，或不包含。所以subset的数量总共有$2^{n}$个。所以可以用0~$2^{n-1}$的二进制来表示一个subset。二进制中每个0/1表示该位置的S[i]是否包括在当前subset中。

class Solution {
public:
    vector<int> num_to_set(vector<int>& nums, unsigned long long num){
        vector<int> subset;
        int i=0;
        while(num){
            if(num&1) 
                subset.push_back(nums[i]);
            num >>=1;
            i++;
        }
        return subset;
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        unsigned long long result_size = pow(2, nums.size())-1;
        for(unsigned long long i=0; i<=result_size; i++){
            result.push_back(num_to_set(nums, i));
        }
        return result;
    }
};

另一种写法:更简明

解释:

This is an amazing solution.Learnt a lot.Let me try to explain this to those who didn't get the logic.

 Number of subsets for {1 , 2 , 3 } = 2^3 .
 why ? 
case    possible outcomes for the set of subsets
  1   ->          Take or dont take = 2 
  2   ->          Take or dont take = 2  
  3   ->          Take or dont take = 2 

therefore , total = 2*2*2 = 2^3 = { { } , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }

Lets assign bits to each outcome  -> First bit to 1 , Second bit to 2 and third bit to 3
Take = 1
Dont take = 0

0) 0 0 0  -> Dont take 3 , Dont take 2 , Dont take 1 = { } 
1) 0 0 1  -> Dont take 3 , Dont take 2 ,   take 1       =  {1 } 
2) 0 1 0  -> Dont take 3 ,    take 2       , Dont take 1 = { 2 } 
3) 0 1 1  -> Dont take 3 ,    take 2       ,      take 1    = { 1 , 2 } 
4) 1 0 0  ->    take 3      , Dont take 2  , Dont take 1 = { 3 } 
5) 1 0 1  ->    take 3      , Dont take 2  ,     take 1     = { 1 , 3 } 
6) 1 1 0  ->    take 3      ,    take 2       , Dont take 1 = { 2 , 3 } 
7) 1 1 1  ->    take 3     ,      take 2     ,      take 1     = { 1 , 2 , 3 } 

In the above logic ,Insert S[i] only if (j>>i)&1 ==true   { j E { 0,1,2,3,4,5,6,7 }   i = ith element in the input array }

element 1 is inserted only into those places where 1st bit of j is 1 
   if( j >> 0 &1 )  ==> for above above eg. this is true for sl.no.( j )= 1 , 3 , 5 , 7 

element 2 is inserted only into those places where 2nd bit of j is 1 
   if( j >> 1 &1 )  == for above above eg. this is true for sl.no.( j ) = 2 , 3 , 6 , 7

element 3 is inserted only into those places where 3rd bit of j is 1 
   if( j >> 2 & 1 )  == for above above eg. this is true for sl.no.( j ) = 4 , 5 , 6 , 7 

Time complexity : O(n*2^n) , for every input element loop traverses the whole solution set length i.e. 2^n

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ans_size = pow(2, n);
        vector<vector<int>> ans(ans_size, vector<int>());

        for(int i=0; i<n; i++){
            for(int j=0; j<ans_size; j++){
                if((j>>i) & 1){
                    ans[j].push_back(nums[i]);
                }
            }
        }
        return ans;
    }
};

79

1-dfs

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length<1 || board[0].length<1){
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int i, int j, int charIndex){
        int m = board.length;
        int n = board[0].length;
        if(i<0 || j<0 || i>=m || j>=n){
            return false;
        }
        if(board[i][j] == word.charAt(charIndex)){
            if(charIndex == word.length()-1){
                return true;
            }
            char tmp = board[i][j];
            board[i][j] = '#';
            boolean flag = dfs(board, word,i-1, j, charIndex+1) ||
                    dfs(board, word, i, j-1, charIndex+1)||
                    dfs(board, word, i, j+1, charIndex+1)||
                    dfs(board, word, i+1, j, charIndex+1);
            board[i][j] = tmp;
            if (flag){
                return true;
            }
        }
        return false;
    }
}

80-Remove Duplicates from Sorted Array II

1-Two Pointers

同No.26只不过增加一个判断条件。

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

//index，新数组的最后一个坐标。index+1,新数组下一个元素插入的位置 / 新数组的长度
//nums[index]==nums[index-1]=nums[i]时无法插入,跳过

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<3)
            return nums.size();
        int index=1, n=nums.size();
        for(int i=2; i<n; i++){
            if(nums[i]!=nums[index-1]){
                nums[++index] = nums[i];
            }
        }
        return index+1;
    }
};

81-Search in Rotated Sorted Array II

1-Binary Search-最坏—O（n）

在No.33上新加判断条件使左边形成

参考No.154

假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0)
            return false;
        int left=0, right=n-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(target==nums[mid]){
                return true;
            }
              //新增判断条件
            else if(nums[mid]==nums[right])
                right--;
            //[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 false;
    }
};

88-Merge Sorted Array

1-Three Pointers 倒序

从后往前扫是因为这个题目中结果仍然放在A中，如果从前扫会有覆盖掉未检查的元素的可能性

//47.24%
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       int  p1=m-1, p2=n-1, p3=m+n-1;//pointer_1, pointer_2, pointer_3
       while(p1>=0 && p2>=0){
           if(nums1[p1]>=nums2[p2]){
               nums1[p3--]=nums1[p1--];
           }
           else{
               nums1[p3--]=nums2[p2--];
           }
       }
       while(p2>=0){
           nums1[p3--]=nums2[p2--];
       }
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       int  p1=m-1, p2=n-1, p3=m+n-1;//pointer_1, pointer_2, pointer_3
       while(p2>=0){
           if(p1<0 || nums1[p1]<nums2[p2]){
               nums1[p3--]=nums2[p2--];
           }
           else{
               nums1[p3--]=nums1[p1--];
           }
       }
    }
};

90-Subsets II

1-DFS

如果元素重复的话, 前一个元素已经处理过所有后一个元素的情况:

即 取num[i-1]=True, nums[i]=False ..... 和 num[i]=True... 两种情况是完全等价的。

class Solution {
public:
    void dfs(vector<int>&nums, int begin_index, vector<vector<int>>&ans, vector<int>& subset){
        ans.push_back(subset);
        for(int i=begin_index; i<nums.size(); i++){
            if(i>begin_index && nums[i]==nums[i-1])
                continue;
            else{
                subset.push_back(nums[i]);
                dfs(nums, i+1, ans, subset);
                subset.pop_back();
            }
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> subset;
        dfs(nums, 0, ans, subset);
        return ans;
    }
};

2-生成序列No.78方法2

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> subset;
        result.push_back(subset);
        sort(nums.begin(), nums.end());
        int begin=0;
        for(int i=0; i<nums.size(); i++){
            if(i==0 || nums[i]!=nums[i-1]){
                begin = 0;
            }
            int n = result.size();
            for(int j=begin; j<n; j++){
                subset = result[j];
                subset.push_back(nums[i]);
                result.push_back(subset);
            }
            begin = n;
        }
        return result;
    }
};

105

1-递归

REF：http://articles.leetcode.com/construct-binary-tree-from-inorder-and-preorder-postorder-traversal

In this questions, most of people just loop through inorder[] to find the root. However, by caching positions of inorder[] indices using a HashMap, the run time can drop from 20ms to 5ms.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int getIndex(int[] nums, int val){
        for(int i=0; i<nums.length; i++){
            if(nums[i]==val){
                return i;
            }
        }
        return -1;
    }
    public TreeNode build(int preStart, int preEnd, int inStart, int inEnd, int[] preorder, int[] inorder){
        if(preStart > preEnd || inStart > inEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        int rootIndex = getIndex(inorder,rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preStart+1,rootIndex-inStart+preStart, inStart, rootIndex-1, preorder, inorder);
        root.right = build(rootIndex-inStart+preStart+1, preEnd, rootIndex+1, inEnd, preorder, inorder);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length<1)
            return null;
        return build(0, preorder.length-1, 0, preorder.length-1, preorder, inorder);
    }
}

106

递归求解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int postEnd = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postEnd = postorder.length-1;
        return helper(inorder, postorder, 0, inorder.length-1);

    }
    public TreeNode helper(int[] inorder, int[] postorder, int instart, int inend){
        if(postEnd<0 || instart>inend)
            return null;
        TreeNode root = new TreeNode(postorder[postEnd--]);
        int rootIndex = 0;
        for (int i=0; i<=inend; i++){
            if (inorder[i]==root.val){
                rootIndex = i;
                break;
            }
        }

        root.right = helper(inorder, postorder, rootIndex+1, inend);
        root.left = helper(inorder, postorder, instart, rootIndex-1);
        return root;
    }
}

118-Pascal's Triangle

1-生成，添加

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<int> tmp;
        vector<vector<int>> ans;
        if(numRows<1){
            return ans;
        }
        else{
            tmp.push_back(1);
            ans.push_back(tmp);
            for(int i=1; i<numRows; i++){
                for(int j=i-1; j>0; j--){
                    tmp[j] = tmp[j]+tmp[j-1];
                }
                tmp.push_back(1);
                ans.push_back(tmp);
            }
            return ans;
        }
    }
};

2-

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for(int i=0; i<numRows; i++){
            ans.push_back(vector<int>(i+1, 1));
            for(int j=1; j<i; j++){
                ans[i][j] = ans[i-1][j-1] + ans[i-1][j];
            }
        }
        return ans;
    }
};

119-Pascal's Triangle II

Could you optimize your algorithm to use only O(k*) extra space?

1-需要逆向求值，避免数据被覆盖

// 53.88%
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans;
        if(rowIndex<0){
            return ans;
        }
        ans.push_back(1);
        for(int i=0; i<rowIndex; i++){
            for(int j=i; j>0; j--){
                ans[j] = ans[j-1]+ans[j];
            }   
            ans.push_back(1);
        }
        return ans;
    }
};

120-Triangle

1-DP

需要注意逆着求dp数组。因为顺着求会破坏数组的值。

也可以从下往上求，代码会更简单。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size()==0 || triangle[0].size()==0)
            return 0;
        int m = triangle.size(), n = triangle[m-1].size();
        vector<int> dp(n,0);
        dp[0]=triangle[0][0];
        for(int i=1; i<m; i++){
            dp[i] =  dp[i-1]+triangle[i][i];

            for(int j=i-1; j>=1; j--)
                dp[j] = min(dp[j-1],dp[j])+triangle[i][j];

            dp[0]+=triangle[i][0];
        }
        int min_sum=dp[0];
        for(int i=1; i<m; i++)
            min_sum = min(min_sum, dp[i]);
        return min_sum;
    }
};

//从下往上求.
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int n = triangle.size();
        vector<int> dp(triangle.back());
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};

121-Best Time to Buy and Sell Stock

1-Fail-TLE

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0;
        for(int i=0; i<prices.size()-1; i++){
            for(int j=i+1; j<prices.size(); j++){
                int diff =prices[j]-prices[i];
                if(diff>ans){
                    ans=diff;
                }
            }
        }
        return ans;
    }
};

2-Kadane's Algorithm

https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input

The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm.

这道题也可以给difference of the prices.

按照股票差价构成新数组 prices[1]-prices[0], prices[2]-prices[1], prices[3]-prices[2], ..., prices[n-1]-prices[n-2]。求新数组的最大子段和就是我们求得最大利润，假设最大子段和是从新数组第 i 到第 j 项，那么子段和= prices[j]-prices[j-1]+prices[j-1]-prices[j-2]+...+prices[i]-prices[i-1] = prices[j]-prices[i-1], 即prices[j]是最大价格，prices[i-1]是最小价格，且他们满足前后顺序关系。代码如下：

//44.46% 
class Solution {
public:
    int get_max(int a, int b){
        if(a>b)
            return a;
        else 
            return b;
    }
    int maxProfit(vector<int>& prices) {
        int current_max_diff=0, max_diff=0;
        for(int i=1; i<prices.size(); i++){
            /*    Don't use the code below. 
                current_max_diff = get_max(0, current_max_diff+prices[i+1]-prices[i]);
                vector的size()返回类型是Member type size_type is an unsigned integral type.

                当执行一个运算时（如这里的a>b），如果它的一个运算数是有符号的而另一个数是无符号的，那么C语言会隐                  式地将有符号 参数强制类型为无符号数，并假设这两个数都是非负的，来执行这个运算。
              */
            current_max_diff = get_max(0, current_max_diff+prices[i]-prices[i-1]);

            max_diff = get_max(current_max_diff, max_diff);
        }
        return max_diff;
    }
};

3-DP-Dynamic Programming

设dp[i]是[0,1,2...i]区间的最大利润，则该问题的一维动态规划方程如下：

dp[i+1] = max{dp[i], prices[i+1] - minprices} ,minprices是区间[0,1,2...,i]内的最低价格

我们要求解的最大利润 = max{dp[0], dp[1], dp[2], ..., dp[n-1]} 代码如下：

//44.46% 
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int current_min_price=INT_MAX, max_profit=0;
        for(int i=0; i<prices.size(); i++){
            current_min_price = min(current_min_price, prices[i]);
            max_profit=max(max_profit, prices[i]-current_min_price);
        }
        return max_profit;
    }
};

122-Best Time to Buy and Sell Stock II

1-Greedy

基本思想是锁定一个低价，然后在价格升到局部最高点（即下一天的价钱就下降了）时候，抛出股票，然后把下一天较低的价钱作为买入，接着计算。

对于一个上升子序列，比如：5，1，2，3，4，0 中的1，2，3，4序列来说，对于两种操作方案： 一，在1买入，4卖出； 二，在1买入，2卖出同时买入，3卖出同时买入，4卖出； 这两种操作下，收益是一样的。

//37.86%
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0;
        for(int i=1; i<prices.size(); i++){
            if(prices[i-1]<prices[i]){
                ans = ans+prices[i]-prices[i-1];
            }
        }
        return ans;
    }
};