LeetCode OJ – 第35页

LeetCode 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

分析：建立一个n+1长度的数组dp，dp[i]表示i这个数构成平方和需要数字的最小个数。
当j*j<i的时候，temp中保存j从1开始每加1得到的dp[i-j*j] + 1的最小值～
当j*j=i的时候，dp[i]的值就直接为1～
从2一直到n可以计算出dp[i]的所有值～
最后return dp[n]的值～

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1);
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            int temp = 99999999;
            for(int j = 1; j * j <= i; j++) {
                if(j * j == i) {
                    temp = 1;
                    break;
                }
                temp = min(temp, dp[i-j*j] + 1);
            }
            dp[i] = temp;
        }
        return dp[n];
    }
};

class Solution {

public:

int numSquares(int n) {

vector<int> dp(n+1);

dp[1] = 1;

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

int temp = 99999999;

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

if(j * j == i) {

temp = 1;

break;

}

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

}

dp[i] = temp;

}

return dp[n];

}

};

LeetCode 304. Range Sum Query 2D – Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

啊喂，不要看下面代码这么长就跑啊。。。。逻辑还是十分简明清晰的。。。先用一个和方阵一样大小的方阵存储入所有它的左上角所有方块上数字的总和～～然后每次调用只要大方块减去两个多余的小方块再加上重复减去的小方块就是要求的总和啦～～还是很好想象滴～～记得要注意边界条件matrix.empty()、i == 0、j == 0的时候～～当时写了很多代码写完就直接submit solution竟然直接AC了。。。//#这也能AC系列#

class NumMatrix {
public:
    vector<vector<int>> v;
    NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        if(matrix.empty())
            return ;
        int n = matrix[0].size();
        v = vector<vector<int>> (m, vector<int>(n));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) {
                    v[i][j] = matrix[0][0];
                } else if(i == 0) {
                    v[i][j] = v[i][j-1] + matrix[i][j];
                } else if(j == 0) {
                    v[i][j] = v[i-1][j] + matrix[i][j];
                } else {
                    v[i][j] = v[i-1][j] + v[i][j-1] + matrix[i][j] - v[i-1][j-1];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1 == 0 && col1 == 0) {
            return v[row2][col2];
        } else if(row1 == 0) {
            return v[row2][col2] - v[row2][col1-1];
        } else if(col1 == 0) {
            return v[row2][col2] - v[row1-1][col2];
        } else {
            return v[row2][col2] - v[row1-1][col2] - v[row2][col1-1] + v[row1-1][col1-1];
        }
    }
};


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

class NumMatrix {

public:

vector<vector<int>> v;

NumMatrix(vector<vector<int>> &matrix) {

int m = matrix.size();

if(matrix.empty())

return ;

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

v = vector<vector<int>> (m, vector<int>(n));

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

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

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

v[i][j] = matrix[0][0];

} else if(i == 0) {

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

} else if(j == 0) {

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

} else {

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

}

int sumRegion(int row1, int col1, int row2, int col2) {

if(row1 == 0 && col1 == 0) {

return v[row2][col2];

} else if(row1 == 0) {

return v[row2][col2] - v[row2][col1-1];

} else if(col1 == 0) {

return v[row2][col2] - v[row1-1][col2];

} else {

return v[row2][col2] - v[row1-1][col2] - v[row2][col1-1] + v[row1-1][col1-1];

}

};

// Your NumMatrix object will be instantiated and called as such:

// NumMatrix numMatrix(matrix);

// numMatrix.sumRegion(0, 1, 2, 3);

// numMatrix.sumRegion(1, 2, 3, 4);

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;

}

};