当前位置：首页 > news >正文

小哆啦解题记：加油站的奇幻冒险

news 2025/7/12 20:17:49

小哆啦解题记：加油站的奇幻冒险

小哆啦开始力扣每日一题的第十三天

https://leetcode.cn/problems/gas-station/description/

在环形道路上，矗立着一串加油站，宛如等待挑战的谜题。这条路上的每个加油站都有一桶汽油，而开车到下一个加油站需要消耗一定的油量。问题是，能否从某个加油站出发，绕环路一周，回到原点？

小哆啦站在第一个加油站，双手叉腰，暗自思忖：“这么多加油站，总有一个是答案！不就是找个起点嘛，我肯定行！”

第一站：暴力出发，初尝苦涩

小哆啦决定从第一个加油站出发，一路尝试。它脑袋一拍，说：“简单！一个一个试，总能找到答案！”

它掏出自己的万能笔记本，开始写下计划：

从加油站 i 出发，模拟行驶，看是否能绕一圈回到原点。
如果油量不足，则换到下一个加油站，继续尝试。
如果尝试了所有加油站都不行，那就返回 -1。

于是，小哆啦写下了这段代码：

function canCompleteCircuitBruteForce(gas: number[], cost: number[]): number {const n = gas.length;for (let start = 0; start < n; start++) {let tank = 0;let valid = true;for (let i = 0; i < n; i++) {const current = (start + i) % n;tank += gas[current] - cost[current];if (tank < 0) {valid = false;break;}}if (valid) return start;}return -1;
}

小哆啦模拟了一遍，虽然结果对了，但它累得满头大汗。
“一个个试效率也太低了！”它嘀咕道，“我要找到更快的方法！”

就在这时，小哆啦的朋友，小智从远处走来。他拍了拍小哆啦的肩膀，笑着说：
“笨蛋，暴力试法虽然能解题，但要多聪明些，咱们得用点技巧！”

第二站：小智的点拨，优化路径

小智提了个问题：“你知道，如果所有加油站的油量总和小于总消耗，会发生什么吗？”
小哆啦认真思考了一会儿，回答道：“那肯定跑不完一圈啊！”
小智点点头：“对了！所以，第一步就是计算总油量。如果总油量不够，直接返回 -1，没必要继续试了。”

“可如果总油量够呢？”小哆啦问。
小智笑了笑：“那你还得聪明点儿。注意到没？如果当前油箱的油量在某个加油站变成负的，那从这之前的任何一个加油站出发都没戏。直接从下一个加油站开始试就行了！”

小哆啦恍然大悟：“所以，不需要暴力试法，只要一次遍历就能搞定！”
它重新设计了算法：

用 totalTank 记录总油量和总消耗的差值。如果最终 totalTank 小于 0，直接返回 -1。
用 currentTank 记录当前油箱的油量。
遍历每个加油站，如果 currentTank < 0，说明起点无效，更新起点为下一个加油站。

小哆啦写下了优化后的代码：

function canCompleteCircuitOptimized(gas: number[], cost: number[]): number {let totalTank = 0; // 总油量let currentTank = 0; // 当前油量let startStation = 0; // 起始加油站for (let i = 0; i < gas.length; i++) {totalTank += gas[i] - cost[i];currentTank += gas[i] - cost[i];if (currentTank < 0) {startStation = i + 1;currentTank = 0;}}return totalTank >= 0 ? startStation : -1;
}

小哆啦运行代码，果然比之前快了很多，它开心地拍手大笑：“小智果然厉害！”