Code – 第239页

LeetCode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

update v2.0: //更高效的O(nlogn)方法～
维护一个数组vector<int> v～
将nums[0]加入数组，对于每一个来的数nums[i]，如果大于v.back()，就将它push入数组～
否则，就找到第一个比这个数大的位置，将该位置的数字替换为nums[i]～～
最终返回v数组的长度~~~就是最长字串的长度啦～

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        vector<int> v;
        v.push_back(nums[0]);
        for(int i = 1; i < n; i++) {
            if(nums[i] > v.back()) {
                v.push_back(nums[i]);
            } else {
                *lower_bound(v.begin(), v.end(), nums[i]) = nums[i];
            }
        }
        return v.size();
    }
};

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

int n = nums.size();

if(n == 0)

return 0;

vector<int> v;

v.push_back(nums[0]);

for(int i = 1; i < n; i++) {

if(nums[i] > v.back()) {

v.push_back(nums[i]);

} else {

*lower_bound(v.begin(), v.end(), nums[i]) = nums[i];

}

return v.size();

}

};

LeetCode 213. House Robber II

Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

分析：这题是上一题House Robber的升级版～～新加了环形的街道biu biu biu～～
所以就会考虑到，最后一个和第一个房子是不能够同时进入的~要不然会告诉警察叔叔～～
所以分为两种情况～～
0.不包括最后一个屋子～就抢劫0~n-2号屋子～
1.不包括第一个屋子～就抢劫1~n-1号屋子～
这样的话，return上面两种情况的最大值就好了～调用两次子函数求值，主函数取其最大值返回～

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        if(n == 2)
            return max(nums[0], nums[1]);
        return max(func(nums, 0, n-2), func(nums, 1, n-1));
    }
    int func(vector<int>& nums, int begin, int end) {
        int n = end - begin + 1;
        vector<int> dp(n);
        dp[0] = nums[begin];
        dp[1] = max(nums[begin], nums[begin+1]);
        for(int i = 2; i < n; i++) {
            int temp = dp[i - 2] + nums[begin+i];
            dp[i] = max(temp, dp[i-1]);
        }
        return dp[n - 1];
    }
};

class Solution {

public:

int rob(vector<int>& nums) {

int n = nums.size();

if(n == 0)

return 0;

if(n == 1)

return nums[0];

if(n == 2)

return max(nums[0], nums[1]);

return max(func(nums, 0, n-2), func(nums, 1, n-1));

}

int func(vector<int>& nums, int begin, int end) {

int n = end - begin + 1;

vector<int> dp(n);

dp[0] = nums[begin];

dp[1] = max(nums[begin], nums[begin+1]);

for(int i = 2; i < n; i++) {

int temp = dp[i - 2] + nums[begin+i];

dp[i] = max(temp, dp[i-1]);

}

return dp[n - 1];

}

};

LeetCode 96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

分析：二分查找树的定义是，左子树节点均小于root，右子树节点均大于root～所以可以用递推的方法，把v[i]表示i个数能够构成的二叉搜索树的个数～初始化边界值是 v[0]=1,v[1]=1,v[2]=2～当i>=3的时候，若以j为root结点，v[j-1]等于root结点左边的j-1个结点能构成的BST个数～v[i-j]等于root结点右边i-j个结点能构成的BST个数~//j+1~i的种数和0~i-j的种数一样。。所以就是v[i-j]～所以v[j-1] * v[i-j]等于以j为root结点能构成的BST种数～～j可以取1~i中的任意一个值，把这些所有计算出来的总数相加就是v[i]的值～～
所以 for(int j = 1; j <= i; j++) v[i] += v[j-1] * v[i-j];最后返回的值是v[n]的值，表示1~n能组成的BST的个数～～

class Solution {
public:
    int numTrees(int n) {
        vector<int> v(n+1);
        v[0] = 1;
        for(int i = 1; i <= n; i++) {
            v[i] = 0;
            if(i <= 2) {
                v[i] = i;
            } else {
                for(int j = 1; j <= i; j++) {
                    v[i] += v[j-1] * v[i-j];
                }
            }
        }
        return v[n];
    }
};

class Solution {

public:

int numTrees(int n) {

vector<int> v(n+1);

v[0] = 1;

for(int i = 1; i <= n; i++) {

v[i] = 0;

if(i <= 2) {

v[i] = i;

} else {

for(int j = 1; j <= i; j++) {

v[i] += v[j-1] * v[i-j];

}

return v[n];

}

};

LeetCode 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分析：特例是，当所有数都为负数的时候，要返回一个最小的负数，而非返回0。设temp的初始化值为nums[0]，i从1一直遍历到len-1：

0.ans始终为temp和ans值中较大的那一个。

1.当当前temp的值为正数的时候，来者nums[i]加temp。//此时如果nums[i]为负数对临时总和temp无贡献，则不会更新ans的值，我们临时把它收入temp的总和当中以备后用。如果nums[i]是正数，对临时总和temp有贡献，那就会更新ans的最大值。

2.当当前temp的值为负数的时候，temp的值直接=nums[i]。//之前的临时总和temp是个负数，对于来者nums[i]来说不管怎样nums[i]如果+temp都是在减少nums[i]，还不如直接将temp=0舍弃前面的负数和，取nums[i]当作当前的临时总和的值。

3.temp如果为0不用考虑怎样都行~

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if(len == 0)
            return 0;
        int ans = nums[0], temp = nums[0];
        for(int i = 1; i < len; i++) {
            if(temp > 0) {
                temp = temp + nums[i];
            } else {
                temp = nums[i];
            }
            ans = max(ans, temp);
        }
        return ans;
    }
};

class Solution {

public:

int maxSubArray(vector<int>& nums) {

int len = nums.size();

if(len == 0)

return 0;

int ans = nums[0], temp = nums[0];

for(int i = 1; i < len; i++) {

if(temp > 0) {

temp = temp + nums[i];

} else {

temp = nums[i];

}

ans = max(ans, temp);

}

return ans;

}

};

LeetCode 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

分析：用一个dp二维数组标记当前方格的最小值～

0.当i == 0 && j == 0的时候，dp[i][j] = grid[i][j];

1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以dp[i][j] = dp[i][j-1] + grid[i][j];

2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以dp[i][j] = dp[i-1][j] + grid[i][j];

3.其他情况下，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

最后直到一直递推输出到终点(m-1, n-1)的时候return dp[m-1][n-1];～～

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

class Solution {

public:

int minPathSum(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

if(m == 0 || n == 0)

return 0;

vector<vector<int>> dp(m, vector<int>(n));

for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) {

if(i == 0 && j == 0) {

dp[i][j] = grid[i][j];

} else if(i == 0) {

dp[i][j] = dp[i][j-1] + grid[i][j];

} else if(j == 0) {

dp[i][j] = dp[i-1][j] + grid[i][j];

} else {

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

}

return dp[m-1][n-1];

}

};

LeetCode 63. Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

分析：这道题是上一道题的升级版~加了障碍物~加不加障碍物差别就在于，当当前地域有障碍物的时候，a[i][j] = 0，其余的不变：
0.a[0][0] = 1; 1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以a[i][j] = a[i][j-1]; 2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以a[i][j] = a[i-1][j]; 3.其余情况，当前方格能由左边和上边两个方向过来，所以a[i][j] = a[i-1][j] + a[i][j-1]; 最后直到一直递推输出到终点(m-1, n-1)的时候return a[m-1][n-1];

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

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

int m = obstacleGrid.size();

int n = obstacleGrid[0].size();

int a[100][100];

for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) {

if(obstacleGrid[i][j] == 1) {

a[i][j] = 0;

} else if(i == 0 && j == 0) {

a[i][j] = 1;

} else if(i == 0) {

a[i][j] = a[i][j-1];

} else if(j == 0) {

a[i][j] = a[i-1][j];

} else {

a[i][j] = a[i-1][j] + a[i][j-1];

}

return a[m-1][n-1];

}

};