柳婼の blog – 第241页 – 我不管，反正我最萌～

LeetCode 330. Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

题目大意：
给一个有序非负整数列nums和一个整数n，最少需要添加多少个数可以使得[1,n]间的每一个数都可以被数列中若干个数的和来表示。输出最小需要添加多少个数字。

分析：
假设[0,t)是暂时能够满足题意的区间，当t<=n的时候，对于每下一个nums[i]：
0.如果nums[i]比t小，那么[0,t)区间内的每一个数加上nums[i]后，区间就被扩展为[0,t+nums[i])了。
1.如果nums[i]比t大，那么必须要加入一个数才能满足扩展区间后的连续性。能加入的这个数当然是越大越好，但是不能超过t，因为超过t的话就会有t之后这个数之前的区间不满足。所以可以令t=t+t，这是它能扩展的最大区间了。此时用cnt计数，cnt+1表示加入了一个数（这个数是t）。
注意点：一开始全都用的int结果在测试用例Last executed input:[1,2,31,33] 2147483647 这个用例下面超时了
后来机智的想了一下发现是如果t当前的值很大又执行了t = t + t会溢出导致t变成了一个很小的值，然后再while肯定超时啦。
所以把int t = 1改为long long int类型就AC啦。啦啦啦。

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int len = nums.size();
        long long int t = 1;
        int cnt = 0;
        int i = 0;
        while(t <= n) {
            if(i < len && nums[i] <= t) {
                t = t + nums[i];
                i++;
            } else {
                t = t + t;
                cnt++;
            }
        }
        return cnt;
    }
};

class Solution {

public:

int minPatches(vector<int>& nums, int n) {

int len = nums.size();

long long int t = 1;

int cnt = 0;

int i = 0;

while(t <= n) {

if(i < len && nums[i] <= t) {

t = t + nums[i];

i++;

} else {

t = t + t;

cnt++;

}

return cnt;

}

};

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

}

};