题解 | #加油站#

题目主要信息

在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。

请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。

题目数据可以保证最多有一个答案。

方法一：直接求解

具体方法

遍历数组，从每个加油站进行循环遍历，查看是否满足油箱剩余量大于消耗量。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        // write code here
        int len = gas.length;
        int index = 0;
        // 遍历每一个位置
        while(index<len){
           // 当前位置的油量和 
            int now = 0;
          // 循环次数
            int count = 0;
            boolean flag = true;
            while(count < len)
            {
              // 此时索引位置
                int temp = (index+count)%len;
              // 消费油量
                now -= cost[temp];
              // 加的油量
                now += gas[temp];
              // 如果此时剩余的油量小于0 说明当前轮次的循环不满足要求
                if(now < 0){
                    flag = false;
                    break;
                    //return false;
                }
                count++;
            }
            if(flag == true){
                return index;
            }else{
                index = index + count + 1;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$ ,两层循环。
• 空间复杂度：$O(1)O(1)$，存结果的遍历

方法二：贪心

具体方法

选择出发点，累加计算每一站得到的汽油量和消耗的汽油量，一旦有

sumCost > sumGas，就需要遍历下一个起始节点，但是这里需要用到贪心算法，否则会超出时间限制。

假设有两个站点x和y，如果x到不了y+1（但能到y），那么从x到y的任一点出发都不可能到达y+1。原因如下：

设x、y之间一点为a，从x出发到y积累的油一定比从a出发到y积累的油多，因为从x出发到a积累的油一定是非负的，设remain表示积累的油，即remain(x -> y) = remain(x -> a) + remain(a -> y)，因为都能到达，三项都是非负的，必然有remain(x -> y) >= remain(a -> y)，因此a点必然到不了y+1，所以在以下的代码中，不能是i += 1，而是i += count + 1，直接跳过中间count个节点。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        // write code here
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumGas = 0, sumCost = 0;
            int count = 0;
            // 遍历每一个点
            while (count < n) {
                int index = (i + count) % n;
                // 总的油量
                sumGas += gas[index];
                // 总的消耗
                sumCost += cost[index];
                // 跳出本轮循环
                if (sumCost > sumGas) {
                    break;
                }
                count++;
            }
            if (count == n) {
                return i;
            } else {
                // 贪心算法 从下一个位置开始遍历
                i += count + 1;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中 n为数组的长度。对数组进行了单次遍历。
• 空间复杂度：$O(1)O(1)$。两个存总油量和总消耗的变量