leetcode----134. Gas Station

本文主要是介绍leetcode----134. Gas Station，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：

https://leetcode.com/problems/gas-station/

大意：

给定一个整型数组gas和一个整型数组cost。

gas[i]意为：汽车到第i个位置时，可以加油gas[i] 

cost[i]意为：汽车从i地行驶至(i + 1) % cost.length 地时需要消耗汽油  。

求从某一地起，满足可以顺时针行驶一周。

规定：当找不到此地时，返回-1。如果可以找到此地，则此地唯一。

思路：

从数组其实位置0开始，顺时针走到数组末尾。在每走到一个地点时：

1. 记录当前的位置i
2. 记录当前所剩的油all
3. 记录从某一地index走，走到i时汽油的数量（同时记录index）

最后首先判断all是否大于等于0：如果小于0，表明不存在满足题意的位置可以使得汽车行驶一圈；如果大于等于0，表明存在这样的位置，此时再根据题意知该位置唯一，则可知该位置肯定就是index（因为index之前的一个index肯定有一段是总耗油小于0，不然不会更新index）

代码：

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int index = 0, i = 0; // index意为从该位置起，可以顺时针至数组末尾 i为数组当前位置int rem = 0, all = 0; // rem为从index起，到i位置还剩多少油 若小于0 则重置index和rem  all表示走完一圈后所剩的油while (i < gas.length) {rem += gas[i] - cost[i];all += gas[i] - cost[i];if (rem < 0) {rem = 0;index = i + 1; // 表明从之前的index到i是无法达到的（油不够）}i++;}// all小于0 表示对循环一周后的油为负数  即无法循环一周if (all < 0)return -1;// 可以循环一周 再结合条件index唯一，可以直接返回indexreturn index;}
}

结果：

结论：

思考思考思考 

 

 

这篇关于leetcode----134. Gas Station的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---