当老司机学会了贪心算法 ??
时间:2021-09-10 16:31:49
手机看文章
扫描二维码
随时随地手机看文章
[导读]读完本文,可以去力扣解决如下题目:134.加油站(Medium)今天讲一个贪心的老司机的故事,就是力扣第134题「加油站」:题目应该不难理解,就是每到达一个站点i,可以加gas[i]升油,但离开站点i需要消耗cost[i]升油,问你从哪个站点出发,可以兜一圈回来。要说暴力解法,肯...
读完本文,可以去力扣解决如下题目:134.加油站(Medium)今天讲一个贪心的老司机的故事,就是力扣第 134 题「加油站」:
题目应该不难理解,就是每到达一个站点
题目应该不难理解,就是每到达一个站点
i
,可以加gas[i]
升油,但离开站点i
需要消耗cost[i]
升油,问你从哪个站点出发,可以兜一圈回来。要说暴力解法,肯定很容易想到,用一个 for 循环遍历所有站点,假设为起点,然后再套一层 for 循环,判断一下是否能够转一圈回到起点:int n = gas.length;
for (int start = 0; start < n; start ) {
for (int step = 0; step < n; step ) {
int i = (start step) % n;
tank = gas[i];
tank -= cost[i];
// 判断油箱中的油是否耗尽
}
}
很明显时间复杂度是 O(N^2),这么简单粗暴的解法一定不是最优的,我们试图分析一下是否有优化的余地。暴力解法是否有重复计算的部分?是否可以抽象出「状态」,是否对同一个「状态」重复计算了多次?以前讲动态规划算法时候,我曾经说过,变化的量就是「状态」。那么观察这个暴力穷举的过程,变化的量有两个,分别是「起点」和「当前油箱的油量」,但这两个状态的组合肯定有不下 O(N^2) 种,显然没有任何优化的空间所以说这道题肯定不是通过简单的剪枝来优化暴力解法的效率,而是需要我们发现一些隐藏较深的规律,从而减少一些冗余的计算。下面我们介绍两种方法巧解这道题,分别是数学图像解法和贪心解法。图像解法
汽车进入站点i
可以加gas[i]
的油,离开站点会损耗cost[i]
的油,那么可以把站点和与其相连的路看做一个整体,将gas[i] - cost[i]
作为经过站点i
的油量变化值:这样,题目描述的场景就被抽象成了一个环形数组,数组中的第i
个元素就是gas[i] - cost[i]
。有了这个环形数组,我们需要判断这个环形数组中是否能够找到一个起点start
,使得从这个起点开始的累加和一直大于等于 0。如何判断是否存在这样一个起点start
?又如何计算这个起点start
的值呢?我们不妨就把 0 作为起点,计算累加和的代码非常简单:int n = gas.length, sum = 0;
for (int i = 0; i < n; i ) {
// 计算累加和
sum = gas[i] - cost[i];
}
sum
就相当于是油箱中油量的变化,上述代码中sum
的变化过程可能是这样的:显然,上图将 0 作为起点肯定是不行的,因为sum
在变化的过程中小于 0 了,不符合我们「累加和一直大于等于 0」的要求。那如果 0 不能作为起点,谁可以作为起点呢?看图说话,图像的最低点最有可能可以作为起点:如果把这个「最低点」作为起点,就是说将这个点作为坐标轴原点,就相当于把图像「最大限度」向上平移了。再加上这个数组是环形数组,最低点左侧的图像可以接到图像的最右侧:这样,整个图像都保持在 x 轴以上,所以这个最低点 4,就是题目要求我们找的起点。不过,经过平移后图像一定全部在 x 轴以上吗?不一定,因为还有无解的情况:如果sum(gas[...]) < sum(cost[...])
,总油量小于总的消耗,那肯定是没办法环游所有站点的。综上,我们就可以写出代码:int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// 相当于图像中的坐标点和最低点
int sum = 0, minSum = Integer.MAX_VALUE;
int start = 0;
for (int i = 0; i < n; i ) {
sum = gas[i] - cost[i];
if (sum < minSum) {
// 经过第 i 个站点后,使 sum 到达新低
// 所以站点 i 1 就是最低点(起点)
start = i 1;
minSum = sum;
}
}
if (sum < 0) {
// 总油量小于总的消耗,无解
return -1;
}
// 环形数组特性
return start == n ? 0 : start;
}
以上是观察函数图像得出的解法,时间复杂度为 O(N),比暴力解法的效率高很多。下面我们介绍一种使用贪心思路写出的解法,和上面这个解法比较相似,不过分析过程不尽相同。贪心解法
用贪心思路解决这道题的关键在于以下这个结论:如果选择站点i
作为起点「恰好」无法走到站点j
,那么i
和j
中间的任意站点k
都不可能作为起点。比如说,如果从站点1
出发,走到站点5
时油箱中的油量「恰好」减到了负数,那么说明站点1
「恰好」无法到达站点5
;那么你从站点2,3,4
任意一个站点出发都无法到达5
,因为到达站点5
时油箱的油量也必然被减到负数。如何证明这个结论?假设tank
记录当前油箱中的油量,如果从站点i
出发(tank = 0
),走到j
时恰好出现tank < 0
的情况,那说明走到i, j
之间的任意站点k
时都满足tank > 0
,对吧。如果把k
作为起点的话,相当于在站点k
时tank = 0
,那走到j
时必然有tank < 0
,也就是说k
肯定不能是起点。拜托,从i
出发走到k
好歹tank > 0
,都无法达到j
,现在你还让tank = 0
了,那更不可能走到j
了对吧。综上,这个结论就被证明了。回想一下我们开头说的暴力解法是怎么做的?如果我发现从i
出发无法走到j
,那么显然i
不可能是起点。现在,我们发现了一个新规律,可以推导出什么?如果我发现从i
出发无法走到j
,那么i
以及i, j
之间的所有站点都不可能作为起点。看到冗余计算了吗?看到优化的点了吗?这就是贪心思路的本质,如果找不到重复计算,那就通过问题中一些隐藏较深的规律,来减少冗余计算。根据这个结论,就可以写出如下代码:int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int sum = 0;
for (int i = 0; i < n; i ) {
sum = gas[i] - cost[i];
}
if (sum < 0) {
// 总油量小于总的消耗,无解
return -1;
}
// 记录油箱中的油量
int tank = 0;
// 记录起点
int start = 0;
for (int i = 0; i < n; i ) {
tank = gas[i] - cost[i];
if (tank < 0) {
// 无法从 start 走到 i
// 所以站点 i 1 应该是起点
tank = 0;
start = i 1;
}
}
return start == n ? 0 : start;
}
这个解法的时间复杂度也是 O(N),和之前图像法的解题思路有所不同,但代码非常类似。其实,你可以把这个解法的思路结合图像来思考,可以发现它们本质上是一样的,只是理解方式不同而已。对于这种贪心算法,没有特别套路化的思维框架,主要还是靠多做题多思考,将题目的场景进行抽象的联想,找出隐藏其中的规律,从而减少计算量,进行效率优化。好了,这道题就讲到这里,希望对你拓宽思路有帮助。_____________