Leetcode刷题总结-1.贪心篇

Leetcode刷题总结

贪心算法刷题心得、总结（实时更新）

前言

动态规划和贪心算法有一些相似之处，但是也有一些区别，动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，贪心算法而是从局部直接选最优的，贪心算法的题目有些也可以用动态规划方法去解，我就直接用动态规划算法了，因为动态规划的解法比贪心更加直观一些。

一、贪心题思路

1. 力扣 53 题最大子数组和， https://leetcode.cn/problems/maximum-subarray/ ；
   思路：这道题是寻找具有最大和的连续子数组，我们定义一维数组dp，dp[i]的含义是包含下标i的子数组中，具有最大和的子数组；接下来寻找递推公式，递推公式就是说到当前的下标为i的子数组中具有最大和的子数组为上一个具有最大和的子数组加上当前的值（dp[i-1]+num[i]），以及当前的值num[i]；因为要求的是连续子数组，如果dp[i-1]+num[i]不是最优的，那就从num[i]从头开始找最大和的子数组。
2. 力扣 376 题摆动序列， https://leetcode.cn/problems/wiggle-subsequence/submissions/ ；
   思路：这道题求的是最大摆动子序列，那么我们为了避免每次遍历到一个数时，都要和前一个数以及下一个数比较，我们定义二维dp数组1，dp[i][0]、dp[i][1]分别表示到当前下标为i的数为山谷和山峰的时候的最大摆动子序列，dp[i][0] = max(dp[i][0], dp[j][1] + 1)，这个式子表示当前数作为山峰的时候；
   dp[i][1] = max(dp[i][1], dp[j][0] + 1)，这个式子表示的是当前数作为山谷的时候，由于我们不知道最大摆动子序列最优是多少，因此在下标i作为山峰和山谷的摆动子序列长度都要求，遍历之前的所有最大摆动子序列去找当前数作为山峰和山谷的最大摆动子序列长度；最后把和数组长度相等的dp数组中的dp[i][0]、dp[i][1]取最大值就是要求的结果。
3. 力扣 122 题 买卖股票的最佳时机II， https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ ；
   思路：买卖股票的最佳时机这道题目是思路是将第i天的最大利润的状态表示为持有股票和不持有股票的最大利润状态，因为我们不知道哪天买入、哪天卖出的利润最大，因此在第i天的时候要么保持买入状态、要么是第i天买入的股票，两者利润较大的为持有状态的最大利润；同时，在第i天要么保持不持有的状态，要么是第i天卖出的股票，两者利润较大的为不持有状态的最大利润，最后求dp数组最后一天的持有和不持有的最大值为最大利润。
4. 力扣 55 题 跳跃游戏、45题 跳跃游戏II， https://leetcode.cn/problems/jump-game/ 、 https://leetcode.cn/problems/jump-game-ii/submissions/；
   思路：首先两道题有公共点就是，都是求最后是否能到达终点，但是第一道题是问能否到达终点，而第二道题是在能到达终点的基础上，问最少需要多少步；第一题的解题思路就是一个循环来遍历当前的下标i能覆盖的范围，在该范围内找最大的i+num[i]（也就是最大覆盖范围），然后看能否到达终点即可；但是跳跃游戏II这道题难度就大了很多，要求最小步数，思路是在当前下标i的覆盖范围内，找到下一个最大的覆盖范围，如果当前节点覆盖范围未达到终点，那就再走一步，在下一步的覆盖范围内继续寻找最大覆盖范围并判断是否到达终点。
5. 力扣 1005 题 K 次取反后最大化的数组和， https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/ ；
   思路：这道题是要求K 次取反后最大化的数组和，这道题使用贪心的思路，贪心的点在于贪绝对值较大同时小于0的数，都尽量进行取反，如果k剩下的次数是偶数的话就不用管了；如果k剩下的次数是技术的话，就贪最小的数进行取反一次，最后把数组中的数相加得到结果即可。
6. 力扣 134 题 加油站， https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ ；
   思路：这道题要求我们从一个站出来，到下一个站消费的油要比获得的少，要求从一个站点出发能够回到该站点；那么我们可以把消耗量减去获得量得到一个两者差值的数组，然后curSum等于开始到当前下标的差值的和，如果小于0，就把start=i+1，curSum清零，所有差值和记为totalSum，如果totalSum小于0，直接返回-1表示不能找一个站点能绕一圈，否则就返回start。
7. 力扣 860 题 柠檬水找零， https://leetcode.cn/problems/lemonade-change/ ；
   思路：柠檬水找零的思路就是把零钱的数量存储下来，然后找零的时候就去优先找面值较大的找零，没有面值较大的就用面值较小的，如果要找零的时候需要的零钱数量为0，就返回false。
8. 力扣 406 题 根据身高重建队列， https://leetcode.cn/problems/queue-reconstruction-by-height/；
   思路：这道题的思路就是首先根据身高从大到小去排列，同时第一个参数相同的话，第二个参数比较小的优先放在前面，根据身高排列好的话，再根据第二个参数排列去插入相应的下标，是满足身高排列的，就满足要求了，最后返回值就可以了。
9. 力扣 452 题 用最少数量的箭引爆气球， https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/；
   思路：用最少的箭引爆气球这个题目的思路就是在遍历的过程中找到下一个气球的左边界是否小于上一个气球的右边界，如果不是的话，那记录箭的数目的变量加1；如果小于的话，那就寻找下一个气球的右边界、上一个气球的右边界中最小的值记录下来，继续与下一个气球的左边界比较即可。
10. 力扣 435 题 无重叠区间， https://leetcode.cn/problems/non-overlapping-intervals/；
    思路：无重叠区间这道题的思路是首先对区间按照左边界的大小进行排序，然后去比较当前区间的右边界与上一个区间的左边界大小，如果当前区间的右边界小于上一个区间的左边界，那么把两者的右边界的较小值赋给当前区间的右边界（这里我也是想半天才明白为什么要取两者的最小值，刚开始没取最小值代码没通过），原因为我们要寻找的是最少需要移除的区间，所以我们必须判断下一个区间与当前区间、上一个区间的重叠性，因此必须用当前区间、上一个区间的最小右边界才能判断下一个区间是否与这两个区间重叠。
11. 力扣 763 题 划分字母区间， https://leetcode.cn/problems/partition-labels/；
    思路：划分字母区间这道题目需要一个技巧，先找到每个字母的最远下标并记录下来，然后去遍历整个字符串，如果当前遍历的字符的下标等于该字符的最远下标，那么就可以划分出来一个区间了，同时更新左边界的值为下一个字符的下标。
12. 力扣 56 题 合并区间， https://leetcode.cn/problems/merge-intervals/；
    思路：合并区间这道题目和无重叠区间这道题米很像，有一点区别，那道题但会最少删除的区间个数，而这里是让你返回把区间合并后的区间，这里的思路比较好想，有重叠的话，直接把两个区间的最大右边界赋给新的区间的右边界即可。
13. 力扣 738 题 单调递增的数字， https://leetcode.cn/problems/monotone-increasing-digits/；
    思路：给一个数，去寻找各个位上单调递增且小于等于它的数，首先一个问题就是怎么知道这个是几位数（这个地方我是想对10取余，再除以10，遍历得到位数），比较好的做法是把它转换为字符串，直接就可以得到它是几位数，同时在遍历的时候，必须从个位数开始往后遍历，因为这样我们可以利用之前的结果（如果从最高位开始遍历的话，比如高的位比低的位数字大，高位减1低位给了9，那后面低的位数的结果不能用你这个结果，因为后面更低位的数字可能小于9），这里比较的时候，给定一个标志位，如果高的位比低的位数字大，那就把高位减1，低位的下标赋给变量flag，flag用来判断需要给定9的最高下标（从垓下标到最低位位的下标都赋值为9），然后用flag赋值即可。

总结

本文主要是分享贪心算法求解问题的思路，贪心算法的题目一般要取最大或者取最小的值的过程，就是要从局部最优推出全局最优。