LeetCode上Tag为贪心算法(Greedy)的题目整理

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;

}

};

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.假设从0开始出发，累积temp0一直是>=0的。到点A的时候发现<0了。此时可以想：从0~A的temp0小于0，而前面的0~某点的代价总和一直是>=0的，所以可以得知前面任何一点都不能作为出发点了，因为temp0 – 0~某点的代价总是小于0的不满足题意。所以只能从下一个结点开始尝试。
1.从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;

}

};

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

}

};

122. Best Time to Buy and Sell Stock II
My Submissions QuestionEditorial Solution
Total Accepted: 83388 Total Submissions: 198240 Difficulty: Medium
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
分析：贪心算法，在每一小段上升序列中最大差值累加得到结果。就是说在股票价格处于上升期的时候，在最低点买入，在最高点卖出。而且可知，每一小段的最大差值就是这段序列的最后一个点的价格减去这段序列第一个点的价格，与每一次从第一个点与第二点的差值一直累加所得结果相同：ans += prices[i] – prices[i – 1];

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++) {
            if(prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
};

class Solution {

public:

int maxProfit(vector<int>& prices) {

int ans = 0;

for(int i = 1; i < prices.size(); i++) {

if(prices[i] > prices[i - 1])

ans += prices[i] - prices[i - 1];

}

return ans;

}

};

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版