代码随想录一刷笔记_贪心算法
60+在408的算法考察难度和深度上还是收手了👍)
贪心算法理论基础
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
第一个难点是如何判断该使用贪心算法了,需要 手推/特殊值/举反例 的方法。
贪心算法的解题步骤:
找到局部最优是什么,然后推导出全局最优。
455 分发饼干
这一题的优化技巧在于,饼干分配掉之后是不会再使用了,所以可以使用一个指针指向最大尺寸的饼干,分配掉之后向前递减即可。省去了一重for循环 & 判定当前饼干是否分配的空间。
376 摆动序列
回溯
这一题先是使用了回溯的方法解决,虽然进行了一定的剪枝操作,但还是被一个很长的测试样例卡住了。事实证明,回溯是一种暴力算法,效率不是很高。
贪心算法
例如 [33,53,12,64,50,41,45,21,97,35,47,92,39,0] 这一个测试样例,可以画出这样的图

可以得到的最长的摆动序列就是荧光笔标注的地方。记录每一个波峰和波谷,去除其他的元素,想起来挺有道理的,但是数学证明略(其实是不会)。。。。
用一个变量记录下一个应该收录的元素应该是在波峰还是波谷,然后记录最长的长度即可。
PS. 这个是我一开始的解法版本,错误只出在一个逆天(特别长)的测试用例上, 找这个问题找了许久。
1 |
|
想法是这样的,由于我要找的是有几个上升序列和下降序列,所以我只要记录这条趋势里的一个数字即可,然后就造成了一种类似抖动幅度变小的结果。

后来改成了和前一个数字进行比较
1 |
|
虽然说仍然记录的不是波峰和波谷的那几个数据,但是是记录了有几条上升/下降趋势。
PS.. 题解的版本是根据当前数值和前一个&后一个的差值判断是不是在波峰/波谷上。
PS… 遇到问题还是得数形结合,干瞪眼了好久没想到好的办法。。。。
53 最大子序和
尝试
尝试作答,但是被逆天的测试样例击败了(好多涉及“0”的问题,包括数组中本就有0,以及连续的数据中相加和为0等)。
1.ed
想法是这样的, 先标记数组中从开头(赋值给startIndex)数和从结尾(赋值为endIndex)数第一个为正数的数,然后对这一段截取的序列进行如下操作:
- 分别从开头和结尾进行遍历,如果当前的数(为正数)和后/前一个数的和为正数,则退出循环,认为当前的这一段就是最大的子数组
- 进行求和。
2.ed
在遇到可能出现连续的多个负数,这几个负数的和的绝对值比相邻的正数大的情况。所以我声明了一个新的向量path,将相邻的数据求和进行后置入path中。
但是,在测试过程中遇到了比如[2,-1,-1,2,0,-3,3]
、[3,-3,2,-3]
的逆天数据,因为首尾指向数据和相邻的和为0的问题,所以其最大子数组和为单个数字。
3.ed
尝试打了一堆补丁,但总会冒出些新样例出来。。。。麻了。。。。
1 |
|
解法
暴力解法 -> 两层for循环
题解第一个给出的是两层for循环,不过现在的测试样例里面塞进去了逆天数据,过不了了。
贪心算法
看了题解之后,我明显意识到把简单问题复杂化了,只需遍历一遍数组,当总和在变大时累加,当总和开始变小时重置总和重新计算。。。。
服了。。。
fin.
122 买卖股票的最佳时机Ⅱ
这一题的前提条件是肯定是赚的(操盘手是个炒股糕手!📈)
如果要赚钱的话,肯定是不在同一天进行买入/卖出的操作。
可以把整个的收入分为好几段,一次买入+卖出记为一次操作,有两个情况:
买入时
- 如果当天股价和后一天的股价相同,是否要买(如何去重)?
- 不要买!因为买第二天的股即可,这里不存在利息的问题。
- 如果当天股价和后一天的股价相同,是否要买(如何去重)?
卖出时
- 如果后一天的股价比当天股价要高?
- 如果高的话,等一天再卖
- 如果后一天的股价比当天股价要高?
PS
题解给出的答案更为简单,只需要遍历一遍数组,然后计算出递增的情况下的涨幅即可。不需要声明额外的变量,节约了空间。
55 跳跃游戏
递归
看到这题,试用了一下递归方法,从可以跨越的最大步数向前递归,可以实现,但是又又又又遇到了逆天测试🤣。
递归部分的代码如下:
1 |
|
贪心
题解将跳几步这个离散的问题化为可以跳跃的范围,遍历一遍数组,判定跳跃的范围能否到终点。
贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
与解相比使用了三元运算符,打败了100%的人👍
1 |
|
欸,确实想不到。。。。
56 跳跃游戏Ⅱ
回溯
不出意外就又是出意外了
又因为某个逆天测试超时了😂
贪心
我的解法是定义一个数组,记录当前到达这个位置的最短步数,然后找到能够到达数组结尾的最短步数。
解答的方法更进一步,通过记录
当前覆盖最远距离下标
,走的最大步数
,下一步覆盖最远距离下标
三个变量查找最小步数。在每次的覆盖范围内(除去已经遍历的值外),找到能够覆盖最远覆盖范围的量。
- 优化版本
- 因为题目里明确表示给出的数据是能跳跃到终点的,所以可以只寻找最远覆盖范围到
nums.size() - 2
的位置。 - 在遍历到
nums.size() - 2
的位置的时候,肯定会在这个位置或者之前肯定有一步ans++
操作。
- 因为题目里明确表示给出的数据是能跳跃到终点的,所以可以只寻找最远覆盖范围到
- 优化版本
1005 K次取反后最大化的数组和
本题还是挺好想的,先把所有负数取反,然后就是对操作后数组中的最小值进行一个操作。
134 加油站
题目的这一个解释有点复杂了。我是这样理解的:
维护了cost
和gas
两个数组,汽车想要成功到达下一站,就需要满足 当前剩余的油量
+ gas[i]
> cost[i]
。
双层for循环
先使用了双层for循环的方法,从第1个开始遍历,时间复杂度是O(n^2)。
果不其然,没有通过所有的测试
贪心
我的想法是按gas
数组的递减顺序来查
那么该怎么排序呢?应该要用到模板函数
题解方法一(不是很能体现贪心的局部最优的思想,也许不算是贪心,但是是一个好解法):
先按照之前计算剩余油量的方法遍历一遍数组,记录最终剩余的油量以及遍历过程中剩余油量的最小值
min
。- 如果最终剩余油量是 < 0的,则说明不存在解
- 从反向遍历数组,找到当前剩余油量正好为最小值的相反数的位置。
关于这个反向遍历数组,个人理解是这样的:
- 首先,如果存在解的话,保证了只有唯一解,所以按照正确的index开始遍历一圈下来,最后剩余的汽油量一定是>0的
- 也就是说,只有解是存在的话,无论从哪一个index出发,遍历一圈,最后的剩余都是正数
- 经过前面一遍正向的遍历,我们得到了剩余油量的最小值
min
- 我们要保证这个解最终成立的话,每经过一个点,剩余量都需要为正,也就是途径的
min
均为正;而我们要找的,就是倒推找到唯一能使这个盈余与这个最小值的差值为正的地方。
感觉描述的很抽象,写完后有一种似懂非懂的感觉😥😥
题解方法二:
结合
当前剩余的油量
+gas[i]
>cost[i]
的想法,可以交换表达式的位置得到:当前剩余的油量
+gas[i]
-cost[i]
> 0定义
rest[i] = gas[i] - cost[i]
局部最优:当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行
135 分发糖果
这一题虽然标记的是hard
,但是按照贪心的思想还是很好实现的。
局部最优
满足在连续的三个数中,中间的数分别和左边与右边比较并且满足要求。
因为是从左往右比较的(先与左边比较再与右边比较,可能在修改数值时左边不满足了),所以需要遍历两遍。
看了下答案,也是这个解法😄
860 柠檬水找零
这一题,因为只有5,10,20三种零钱,所以只需遍历以下即可。
406 根据身高重建队列
这一题有身高和前面有多少个比他高这两个元素,所以在排列的时候需要分一下主次,这个我是想到了的。因为他的输出是需要从小到大排序的,所以我把排序思维定式在了从小到大排上面。
通过观察示例,我发现身高+序列有一个特点,就是后面的相加和都比前面的大,但是吭哧吭哧写完代码后发现这只是一个巧合罢了😥
这道题使用了一种很巧的方法,因为第二个数值记录的是往前看有几个比他高的人。所以,先对队列进行从大到小的排序(身高如果相同的话,第二个数值大的在后面);然后把这些元组插入一条新的队列中,这样就能保证后插入的始终是比已在队列中的元组身高要低,不会影响到第二个数值的排序。
有一种类似栈的感觉,将数据从大到小压入,就很难形容是什么脑回路能想到这个解法的。。。。
452 用最少数量的箭引爆气球
我的想法
这一题是要找n个数,使得存储的范围里能够至少包含其中一个数。
我声明了一个布尔型向量,遍历测试样例的向量组,当找到一个在这个范围的数时,将这个范围对应的index的向量标记为true;当这个布尔型向量全为true时,表示已经完成了任务。
题解
题解的方法就很简单了。
不需要将已经射中的气球进行标记,只是进行了一次遍历。
每当遍历到一个不和第一个数组范围不重合的情况时,进行更新,这时候说明增加了一只箭。
另外,因为给出的样例数组时不需要输出的,所以甚至不需要声明一个边界向量,直接对原数组进行修改操作即可。
435 无重叠区间
在初次看到这一题的时候确实是一点想法都没有,然后想到了qfe的提醒,翻了下评论区,看到了这样一条评论:
然后想了一会儿,怎么着,突然悟了。
这两题的共同点是,这一题和452 用最少数量的箭引爆气球
的要求是类似的,都是需要输出个数。所以,我不需要最后给出我删除的是哪几个向量组合,我也可以和452
那一题的题解一样直接在原数组基础上进行操作,只要记下总共的删去个数即可。
步骤如下:
首先,肯定是先对原数组进行排序啦,满足这样的排序标准:① 第一个数较小的靠前;② 第一个数相同,则第二个数较小靠前;
结果是求得无重复区间,所以我们在遇到有重时使用留小范围,筛去大范围的策略。
可以分为这五种情况(tips:由于已经排过序了,所以下一段的起始肯定是逐渐递增的):
① 当前范围与上一段相同,直接删去;
② 当前范围小于上一段,按照“保小”的原则,留下这一段;
③&④ 当前范围的起始 >= 前一段,结束 <= 下一段,保留上一段;
⑤ 当前范围与上一段没有重合,不管。
763 划分字母区间
这一题,emmmm,最后用时竟然是0ms(啪唧啪唧啪唧啪唧)

我的想法
按照题面硬想确实没什么思路,不妨试试先思考局部最优是什么。
一个字母区间里面最起码是要包含第一个字母的,那不妨先摘出以当前第一个字母为始,并以这个字母为结尾的范围。
然后,往后面的范围里查找是否有与摘出的部分相同的元素,如果重了,则将范围的结尾移动到此处。当然,这里需要注意,新的范围里可能会引进新的字母,所以需要重复查询避免(这里似乎也只能使用 do while,写这么久leetcode还是第一次用来着)
最后,输出向量组,开香槟!
题解
题解的想法很是巧妙,他是使用额外的大小为26的数组记录当前字母最后出现的位置(小技巧🐥)!
这样遍历一遍之后,就很ez了,只需比对当前下标是否和最后出现位置相等即可,反之更新边界位置的值。
56 合并区间
这一题没有什么特别的地方。还是按照排序序列,然后遍历一遍。
题解给出了一个关于获得向量组最后数组的方法很有意思,能省好多代码。
1 |
|
738 单调递增的数字
这个问题的关键在于找到关键的问题(bushi),找到哪一个是最大的递增数字。
可以采取类似写竖式求减法的样子,如果前一位数字比当前的要大,则将当前位赋值为9,前一位数字减1;当然,标记最后作此操作的位置,这个数字后面的数字均可以为9,此时达到最大值。