代码随想录一刷笔记_贪心算法

60+在408的算法考察难度和深度上还是收手了👍)

贪心算法理论基础

贪心的本质是选择每一阶段的局部最优,从而达到全局最优

第一个难点是如何判断该使用贪心算法了,需要 手推/特殊值/举反例 的方法。

贪心算法的解题步骤:

找到局部最优是什么,然后推导出全局最优。

455 分发饼干

这一题的优化技巧在于,饼干分配掉之后是不会再使用了,所以可以使用一个指针指向最大尺寸的饼干,分配掉之后向前递减即可。省去了一重for循环 & 判定当前饼干是否分配的空间。

376 摆动序列

回溯

这一题先是使用了回溯的方法解决,虽然进行了一定的剪枝操作,但还是被一个很长的测试样例卡住了。事实证明,回溯是一种暴力算法,效率不是很高。

贪心算法

例如 [33,53,12,64,50,41,45,21,97,35,47,92,39,0] 这一个测试样例,可以画出这样的图

2305adb002cca4053ce43f861db53f4

可以得到的最长的摆动序列就是荧光笔标注的地方。记录每一个波峰和波谷,去除其他的元素,想起来挺有道理的,但是数学证明略(其实是不会)。。。。

用一个变量记录下一个应该收录的元素应该是在波峰还是波谷,然后记录最长的长度即可。

PS. 这个是我一开始的解法版本,错误只出在一个逆天(特别长)的测试用例上, 找这个问题找了许久。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (nums.size() == 1) return 1;
int flag = 0;
int lastNum = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == lastNum) continue;
else if (nums[i] > lastNum && flag < 0) continue;
else if (nums[i] < lastNum && flag > 0) continue;
else {
result.push_back(nums[i]);
if (nums[i] > lastNum) flag = -1;
else flag = 1;
lastNum = nums[i];
}
}

想法是这样的,由于我要找的是有几个上升序列和下降序列,所以我只要记录这条趋势里的一个数字即可,然后就造成了一种类似抖动幅度变小的结果。

381a9a7ddffc8db38fdaa6d20998f1e

后来改成了和前一个数字进行比较

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i - 1] && flag != 1) { // 如果当前元素比前一个大且趋势不是上升
length++;
flag = 1; // 更新趋势为上升
} else if (nums[i] < nums[i - 1] && flag != -1) { // 如果当前元素比前一个小且趋势不是下降
length++;
flag = -1; // 更新趋势为下降
}
// 如果nums[i] == nums[i-1],什么都不做
}

虽然说仍然记录的不是波峰和波谷的那几个数据,但是是记录了有几条上升/下降趋势。

PS.. 题解的版本是根据当前数值和前一个&后一个的差值判断是不是在波峰/波谷上。

PS… 遇到问题还是得数形结合,干瞪眼了好久没想到好的办法。。。。

53 最大子序和

尝试

尝试作答,但是被逆天的测试样例击败了(好多涉及“0”的问题,包括数组中本就有0,以及连续的数据中相加和为0等)。

1.ed

想法是这样的, 先标记数组中从开头(赋值给startIndex)数和从结尾(赋值为endIndex)数第一个为正数的数,然后对这一段截取的序列进行如下操作:

  1. 分别从开头和结尾进行遍历,如果当前的数(为正数)和后/前一个数的和为正数,则退出循环,认为当前的这一段就是最大的子数组
  2. 进行求和。
2.ed

在遇到可能出现连续的多个负数,这几个负数的和的绝对值比相邻的正数大的情况。所以我声明了一个新的向量path,将相邻的数据求和进行后置入path中。

但是,在测试过程中遇到了比如[2,-1,-1,2,0,-3,3][3,-3,2,-3]的逆天数据,因为首尾指向数据和相邻的和为0的问题,所以其最大子数组和为单个数字。

3.ed

尝试打了一堆补丁,但总会冒出些新样例出来。。。。麻了。。。。

1
2
3
4
5
6
7
8
9
if (startNum > num) num = startNum;
if (endNum > num) num = endNum;
if (startIndex < endIndex) {
if(startIndex >= 0) {
if (path[startIndex] > num ) num = path[startIndex];
}
if (endIndex < path.size())
if (path[endIndex] > num) num = path[endIndex];
}

解法

暴力解法 -> 两层for循环

题解第一个给出的是两层for循环,不过现在的测试样例里面塞进去了逆天数据,过不了了。

贪心算法

看了题解之后,我明显意识到把简单问题复杂化了,只需遍历一遍数组,当总和在变大时累加,当总和开始变小时重置总和重新计算。。。。

服了。。。

fin.

122 买卖股票的最佳时机Ⅱ

这一题的前提条件是肯定是赚的(操盘手是个炒股糕手!📈)

如果要赚钱的话,肯定是不在同一天进行买入/卖出的操作。

可以把整个的收入分为好几段,一次买入+卖出记为一次操作,有两个情况:

  • 买入时

    • 如果当天股价和后一天的股价相同,是否要买(如何去重)?
      • 不要买!因为买第二天的股即可,这里不存在利息的问题。
  • 卖出时

    • 如果后一天的股价比当天股价要高?
      • 如果高的话,等一天再卖

PS

题解给出的答案更为简单,只需要遍历一遍数组,然后计算出递增的情况下的涨幅即可。不需要声明额外的变量,节约了空间。

55 跳跃游戏

递归

看到这题,试用了一下递归方法,从可以跨越的最大步数向前递归,可以实现,但是又又又又遇到了逆天测试🤣。

递归部分的代码如下:

1
2
3
4
5
6
7
8
9
10
bool travelsal(vector<int>& nums, int startIndex) {
if (startIndex + nums[startIndex] >= nums.size() - 1) return true;

int steps = nums[startIndex];
for (int i = steps; i > 0; i--) {
bool flag = travelsal(nums, startIndex + i);
if (flag) return true;
}
return false;
}

贪心

题解将跳几步这个离散的问题化为可以跳跃的范围,遍历一遍数组,判定跳跃的范围能否到终点。

贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点

与解相比使用了三元运算符,打败了100%的人👍

1
2
3
4
5
6
7
8
9
bool canJump(vector<int>& nums) {
int leap = 0;
for (int i = 0; i < nums.size(); i++) {
if (leap >= nums.size() - 1) return true;
if (i > leap) return false;
leap = i + nums[i] > leap ? i + nums[i] : leap;
}
return false;
}

欸,确实想不到。。。。

56 跳跃游戏Ⅱ

回溯

不出意外就又是出意外了

又因为某个逆天测试超时了😂

贪心

  • 我的解法是定义一个数组,记录当前到达这个位置的最短步数,然后找到能够到达数组结尾的最短步数。

  • 解答的方法更进一步,通过记录当前覆盖最远距离下标走的最大步数下一步覆盖最远距离下标三个变量查找最小步数。

    在每次的覆盖范围内(除去已经遍历的值外),找到能够覆盖最远覆盖范围的量。

    • 优化版本
      • 因为题目里明确表示给出的数据是能跳跃到终点的,所以可以只寻找最远覆盖范围到nums.size() - 2的位置。
      • 在遍历到nums.size() - 2的位置的时候,肯定会在这个位置或者之前肯定有一步ans++操作。

1005 K次取反后最大化的数组和

本题还是挺好想的,先把所有负数取反,然后就是对操作后数组中的最小值进行一个操作。

134 加油站

题目的这一个解释有点复杂了。我是这样理解的:

维护了costgas两个数组,汽车想要成功到达下一站,就需要满足 当前剩余的油量 + gas[i] > cost[i]

双层for循环

先使用了双层for循环的方法,从第1个开始遍历,时间复杂度是O(n^2)。

果不其然,没有通过所有的测试

贪心

我的想法是按gas数组的递减顺序来查

那么该怎么排序呢?应该要用到模板函数

  1. 题解方法一(不是很能体现贪心的局部最优的思想,也许不算是贪心,但是是一个好解法):

    先按照之前计算剩余油量的方法遍历一遍数组,记录最终剩余的油量以及遍历过程中剩余油量的最小值min

    • 如果最终剩余油量是 < 0的,则说明不存在解
    • 从反向遍历数组,找到当前剩余油量正好为最小值的相反数的位置。

    关于这个反向遍历数组,个人理解是这样的:

    • 首先,如果存在解的话,保证了只有唯一解,所以按照正确的index开始遍历一圈下来,最后剩余的汽油量一定是>0的
      • 也就是说,只有解是存在的话,无论从哪一个index出发,遍历一圈,最后的剩余都是正数
    • 经过前面一遍正向的遍历,我们得到了剩余油量的最小值min
    • 我们要保证这个解最终成立的话,每经过一个点,剩余量都需要为正,也就是途径的min均为正;而我们要找的,就是倒推找到唯一能使这个盈余与这个最小值的差值为正的地方。

    感觉描述的很抽象,写完后有一种似懂非懂的感觉😥😥

  2. 题解方法二:

    • 结合当前剩余的油量 + 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的提醒,翻了下评论区,看到了这样一条评论:image-20241125125254036

然后想了一会儿,怎么着,突然悟了。

这两题的共同点是,这一题和452 用最少数量的箭引爆气球的要求是类似的,都是需要输出个数。所以,我不需要最后给出我删除的是哪几个向量组合,我也可以和452那一题的题解一样直接在原数组基础上进行操作,只要记下总共的删去个数即可。

步骤如下:

  1. 首先,肯定是先对原数组进行排序啦,满足这样的排序标准:① 第一个数较小的靠前;② 第一个数相同,则第二个数较小靠前;

  2. 结果是求得无重复区间,所以我们在遇到有重时使用留小范围,筛去大范围的策略。

    可以分为这五种情况(tips:由于已经排过序了,所以下一段的起始肯定是逐渐递增的):

    c4f139a2fee359869ece151515053a4

    ① 当前范围与上一段相同,直接删去;

    ② 当前范围小于上一段,按照“保小”的原则,留下这一段;

    ③&④ 当前范围的起始 >= 前一段,结束 <= 下一段,保留上一段;

    ⑤ 当前范围与上一段没有重合,不管。

763 划分字母区间

这一题,emmmm,最后用时竟然是0ms(啪唧啪唧啪唧啪唧)

image-20241126231652039

我的想法

按照题面硬想确实没什么思路,不妨试试先思考局部最优是什么。

一个字母区间里面最起码是要包含第一个字母的,那不妨先摘出以当前第一个字母为始,并以这个字母为结尾的范围。

然后,往后面的范围里查找是否有与摘出的部分相同的元素,如果重了,则将范围的结尾移动到此处。当然,这里需要注意,新的范围里可能会引进新的字母,所以需要重复查询避免(这里似乎也只能使用 do while,写这么久leetcode还是第一次用来着)

最后,输出向量组,开香槟!

题解

题解的想法很是巧妙,他是使用额外的大小为26的数组记录当前字母最后出现的位置(小技巧🐥)!

这样遍历一遍之后,就很ez了,只需比对当前下标是否和最后出现位置相等即可,反之更新边界位置的值。

56 合并区间

这一题没有什么特别的地方。还是按照排序序列,然后遍历一遍。

题解给出了一个关于获得向量组最后数组的方法很有意思,能省好多代码。

1
2
3
vector<vector<int>> result;
result.push_back([1,1]);
if (result.back()[1] != 0) result.back()[1] = 0;

738 单调递增的数字

这个问题的关键在于找到关键的问题(bushi),找到哪一个是最大的递增数字。

可以采取类似写竖式求减法的样子,如果前一位数字比当前的要大,则将当前位赋值为9,前一位数字减1;当然,标记最后作此操作的位置,这个数字后面的数字均可以为9,此时达到最大值。


代码随想录一刷笔记_贪心算法
http://example.com/2024/11/11/code-8-greedy/
作者
Poivre
发布于
2024年11月11日
许可协议