网站备案信息查询一站式自媒体服务平台
小哆啦解题记：加油站的奇幻冒险
小哆啦开始力扣每日一题的第十三天
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;
}
小哆啦运行代码，果然比之前快了很多，它开心地拍手大笑：“小智果然厉害！”
终点：智慧的结晶
小哆啦和小智站在环形路的终点，看着一路解题的过程。
小智问：“现在你明白了吗？解题最重要的是理解本质，不一定非要用蛮力。”
小哆啦点点头，笑着总结：
- 暴力法：虽然简单，但效率低，适合小规模问题。
- 优化法：从全局思维入手，利用规律筛选不可能的起点，大幅提升效率。
它拍了拍小智的肩膀，笑道：“下次再遇到这样的题，我肯定会用聪明的办法！”
小智笑着回应：“有你这份心，编程的路一定越走越宽！”
两人沿着环路继续前行，向着下一个谜题进发。