Code – 第238页

LeetCode 55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

题目解释：从下标为0的地方开始，A[i]表示当前i处能够跳跃的最大长度。（也就是也就是i处最远能跳到下标i + nums[i]处。）判断能不能跳啊跳到最后一个下标的地方。

分析：设立distance为当处在i下标的时候，前面所能够达到的所有长度的最大值（因为是最大值，所以0~最大值的所有下标都可以遍历到），当i <= distance的所有下标都可以遍历，然后更新distance的值为distance = max(distance, i + nums[i]);
最后判断能够最远到达的distance是否够的到最后一个下标n-1，不能的话返回false，能的话返回true

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int distance = 0;
        for(int i = 0; i < nums.size() - 1 && i <= distance; i++) {
            distance = max(distance, i + nums[i]);
        }
        return distance >= (nums.size() - 1);
    }
};

class Solution {

public:

bool canJump(vector<int>& nums) {

int distance = 0;

for(int i = 0; i < nums.size() - 1 && i <= distance; i++) {

distance = max(distance, i + nums[i]);

}

return distance >= (nums.size() - 1);

}

};

LeetCode 134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

分析：gas[i] – cost[i]为车行驶的代价。要想能走完一圈，必须时刻保持从出发点到终点始终行驶代价总和temp >= 0～假设从0开始出发，累积temp0一直是>=0的。到点A的时候发现<0了。此时可以想：从0~A的temp0小于0，而前面的0~某点的代价总和一直是>=0的，所以可以得知前面任何一点都不能作为出发点了，因为temp0 – 0~某点的代价总是小于0的不满足题意。所以只能从下一个结点开始尝试。从A+1结点开始出发，累积temp1一直是>=0的。到点B的时候发现<0了。此时可以想：从A+1 ~ B的temp1小于0，那么前面的A+1到某点的代价总和一直是>=0的，所以可以得知前面任何一点都不能作为出发点了，因为temp1 – A+1~某点的代价总是小于0不和题意的。所以就从下一点开始尝试….
2.终于有一次可以从D开到n-1这个点了。只要看能不能车再从0开到D-1了。也就是想看temp2+temp0+temp1的过程中可不可能总代价小于0.结论是只要所有点总代价total>=0，那么一定可以开一圈。可以这么证明：total>=0 temp0 和temp1都是在最后一个点game over的前面都是正数那么ok，最后一个数是导致<=0的点，但是去掉了temp0这个负数，总代价毫无疑问还是大于0的不用说。所以说最后只要total>=0那么就一定可以走结束一圈。啊哦- -我竟然说了这么多=_=

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        if(gas.empty())
            return -1;
        int total = 0, temp = 0, index = 0;
        for(int i = 0; i < gas.size(); i++) {
            total += gas[i] - cost[i];
            if(temp >= 0) {
                temp += gas[i] - cost[i];
            } else {
                temp = gas[i] - cost[i];
                index = i;
            }
        }
        return total >= 0 ? index : -1;
    }
};

class Solution {

public:

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

if(gas.empty())

return -1;

int total = 0, temp = 0, index = 0;

for(int i = 0; i < gas.size(); i++) {

total += gas[i] - cost[i];

if(temp >= 0) {

temp += gas[i] - cost[i];

} else {

temp = gas[i] - cost[i];

index = i;

}

return total >= 0 ? index : -1;

}

};

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