欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > IT业 > 217.贪心算法:加油站(力扣)

217.贪心算法:加油站(力扣)

2024/11/30 8:45:06 来源:https://blog.csdn.net/weixin_63779802/article/details/140379088  浏览:    关键词:217.贪心算法:加油站(力扣)

代码解决

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curtotol = 0; // 当前累积油量int tatol = 0; // 总的油量减去总的花费油量int start = 0; // 起始加油站的索引// 遍历所有加油站for (int i = 0; i < gas.size(); i++){curtotol += gas[i] - cost[i]; // 计算当前累积油量tatol += gas[i] - cost[i]; // 计算总的油量减去总的花费油量// 如果当前累积油量小于0,则无法到达下一个加油站if (curtotol < 0){start = i + 1; // 重置起点为下一个加油站curtotol = 0; // 重置当前累积油量}}// 如果总的油量小于总的花费油量,则无法完成环路if (tatol < 0) return -1;// 返回起始加油站的索引return start;}
};

核心思想

  1. 遍历每个加油站
    • 计算从当前起点开始的累积油量。如果累积油量不足以到达下一个加油站,则从下一个加油站重新开始。
    • 如果总的油量 tatol 小于总的花费油量,说明无论从哪个加油站出发都无法绕环路一周,直接返回 -1
    • 否则,返回最后一次重置起点的位置 start

假设 gas = [1, 2, 3, 4, 5]cost = [3, 4, 5, 1, 2]

  1. 遍历加油站:

    • i = 0: curtotol = 1 - 3 = -2, tatol = -2, start = 1, curtotol = 0
    • i = 1: curtotol = 2 - 4 = -2, tatol = -4, start = 2, curtotol = 0
    • i = 2: curtotol = 3 - 5 = -2, tatol = -6, start = 3, curtotol = 0
    • i = 3: curtotol = 4 - 1 = 3, tatol = -3
    • i = 4: curtotol = 5 - 2 = 6, tatol = 0
  2. 最终 tatol >= 0,返回 start = 3

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com