liuchuo – 第241页 – 我不管，反正我最萌～

LeetCode 91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).
The number of ways decoding “12” is 2.

分析：和爬楼梯的那道题leetcode 70. Climbing Stairs有类似之处～～建立一个与String等长的dp数组～0.如果说当前s[i]不等于0,那先令dp[i] = dp[i-1] 1.如果s[i-1]与s[i]能够构成1~26里面的数字，那就把s[i-1]与s[i]构成一个整体，dp[i] += dp[i-2]; 最后返回数组的最后一个值dp[len-1]

class Solution {
public:
    int check(char a) {
        return a != '0';
    }
    int func(char a, char b) {
        return a == '1' || a == '2' && b <= '6';
    }
    int numDecodings(string s) {
        int len = s.length();
        vector<int> dp(len, 0);
        if(len == 0 || s[0] == '0') 
            return 0;
        if(len == 1)
            return check(s[0]);
        dp[0] = 1;
        dp[1] = check(s[1]) + func(s[0], s[1]);
        for(int i = 2; i < len; i++) {
            if(check(s[i])) 
                dp[i] = dp[i-1];
            if(func(s[i-1], s[i])) 
                dp[i] += dp[i-2];
        }
        return dp[len-1];
    }
};

class Solution {

public:

int check(char a) {

return a != '0';

}

int func(char a, char b) {

return a == '1' || a == '2' && b <= '6';

}

int numDecodings(string s) {

int len = s.length();

vector<int> dp(len, 0);

if(len == 0 || s[0] == '0')

return 0;

if(len == 1)

return check(s[0]);

dp[0] = 1;

dp[1] = check(s[1]) + func(s[0], s[1]);

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

if(check(s[i]))

dp[i] = dp[i-1];

if(func(s[i-1], s[i]))

dp[i] += dp[i-2];

}

return dp[len-1];

}

};

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];

}

};