leetcode（js）-每日一练之 加油站 题库编号134

leetcode（js）-每日一练之 加油站

1. 首先看到这道题的第一思路是，从0号加油站出发，按0-1-2-3-4-0的方向行驶，若中间没油了，则说明从0号加油站出发这种方案是不可行的，我们再改用从1号加油站出发的方案，。。。。。。一个一个试，直到某号加油站可以循环一周，我们最终的答案就是这号加油站，但是这样做有点暴力，不是最优解。
2. 接下来说一下比较完美的解法把，空间复杂度o（n），开始跟暴力解法相同，从0号加油站出发，向前走，直到行不通，接下来的做法与暴力解法不同了！！！注意！！！，行不通之后，直接把起始点转移到行不通的加油站上，有人会问，这样做是为啥子呢？ 看上面的样式图，会发现0号加油站出发， 1 2 号可以走，由于油量不足，没法走到3号加油站，从0号出发到1号向3号行驶时，1号从0号拿到的油量肯定大于等于0，若开头就从1号出发向3号行驶时，那么其从外部获得的油量肯定=0； 大于等于0的方案都无法实现，等于0肯定无法实现了，所以不用考虑1号，2号同理，直接把3号作为起始点即可！！
3. 在整个算法之前，要先判断旅途能不能完成：油总数一定要大于等于油总消耗量

var canCompleteCircuit = function(gas, cost) {
          
   
            let totalgas = 0;
            let totalcost = 0;
            for (let i = 0; i < gas.length; i++) {
          
   
                totalgas += gas[i];
                totalcost += cost[i];
            }
            if (totalgas < totalcost) {
          
   
                return -1;
            }
            let currentgas = 0;
            let start = 0;
            for (let i = 0; i < gas.length; i++) {
          
   
                currentgas = currentgas + gas[i] - cost[i];
                if (currentgas < 0) {
          
   
                    currentgas = 0;
                    start = i + 1;
                }
            }
            return start;
        };