LeetCode-134. Gas Station(JAVA)加气站问题

    xiaoxiao2021-03-26  6

    134. Gas Station

    There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

    You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

    Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

    Note: The solution is guaranteed to be unique

    沿环形路线有N个加油站,其中气体在车站i是量是gas[i]。你有车有无限容量的气罐,从加油站i到下一个加油站站点i+1,要消耗cost[i]的气体。你开始旅程时,气罐是空的。回到起始加油站的指数,选择一个起点开始旅游,如果你能在周围环形旅行一次,就返回开始的加油站索引,否则返回-1。 注意: 答案保证是唯一的。

    首先先要明白:如果一个数组的总和非负,那么一定可以找到一个起始位置,从他开始绕数组一圈,累加和一直都是非负的。

    如果从i出发,那么gas[i]-cost[i](dif[i])一定是大于0的,程序中有判断。如果dif[i]+dif[i+1]+……+dif[k-1]>=0,而dif[i]+dif[i+1]+……+dif[k-1]+dif[k]<0,此时需要重新设置开始点,那么需要从I+1开始吗?dif[i]肯定大于0,所有从i

    +1开始,肯定不可能到达k点,少加了一个正数。那么需要设置开始点为K+1;

    public int canCompleteCircuit(int[] gas, int[] cost) { // 记录访问的起始点 int start = 0; // 加的气和消耗的气的总差值(从0开始) int total = 0; // 从start位置开始,加的气和消耗的气的总差值 int sum = 0; for (int i = 0; i < gas.length; i++) { int dif = gas[i] - cost[i]; sum += dif; total += dif; // 走到i站是负数,说明走不到i站, // 也不能选取起始站到i站中的任何一战 if (sum < 0) { sum = 0; // 下一站作为起始点 start = i + 1; } } return total >= 0 ? start : -1; }

    转载请注明原文地址: https://ju.6miu.com/read-500034.html

    最新回复(0)