区块链技术博客
www.b2bchain.cn

[M贪心] lc134. 加油站(贪心)

这篇文章主要介绍了[M贪心] lc134. 加油站(贪心)的讲解,通过具体代码实例进行20756 讲解,并且分析了[M贪心] lc134. 加油站(贪心)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=20756

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

    • 1. 题目来源
    • 2. 题目说明
    • 3. 题目解析

1. 题目来源

链接:lc134. 加油站

2. 题目说明

[M贪心] lc134. 加油站(贪心)

3. 题目解析

本题属于,单调队列优化 dp,能做到 O ( n ) O(n) O(n) 的时间,但也需要开一个 O ( n ) O(n) O(n) 的单调队列。但是这个是很套路的做法,可推广到其它众多问题。

但,在此仅针对本题,有一个贪心, O ( n ) O(n) O(n) 的做法,且空间为 O ( 1 ) O(1) O(1),不具有推广性。

思路:

  • 首先,暴力解法就是枚举所有起点,环形走,加上加油站的油量,减去花费油量。这样就能找到那个唯一解,时间复杂度就是 O ( n 2 ) O(n^2) O(n2)
  • 贪心思路:
    • 假设从起点 i,走到 j 时,无法再到达 j+1 下一个加油站
    • 那么必然从 i+1j-1 的任何一点作为起点都无法到达 j+1 这个加油站
    • 因为首先 i 是能够到达 i+1j 之间的所有加油站的,那么意味着最次到达这些站点的时候剩余油量都是大于等于 0 的。但是如果将该点作为起点,该点的油量初始就是 0,必然是不可能到达 j+1 这个加油站的
    • 所以不必要再枚举 i+1j 的所有加油站作为起点。故每个加油站只被枚举一次,所有是 O ( n ) O(n) O(n) 的做法

代码:

class Solution { public:     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {         int n = gas.size();         for (int i = 0, j; i < n; ) {       // 枚举起点             int cnt = 0;                    // 剩余油量             for (j = 0; j < n; ++j) {       // 从第i站开始走过几个站                 int k = (i + j) % n;        // 走k个站,环形处理方式                 cnt += gas[k] - cost[k];                 if (cnt < 0) break;             }             if (j == n) return i;             i += j + 1;                     // 跳过中间的不可能作为起点的加油站         }         return -1;     } }; 

本文转自互联网,侵权联系删除[M贪心] lc134. 加油站(贪心)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » [M贪心] lc134. 加油站(贪心)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们