贪心算法（11）（java）加油站

题目：在一条环路上有n个加油站，其中第i个加油站有汽油 gas[i]升.。
           你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油 cost[i]升。你从其中的一个加油站出发，开始时油箱为空。
           给定两个整数数组 gas 和 cost,如果你可以按顺而环招行驶一周，则返回出发时加油站的编号，否则返回-1。如果存在解,则保证它是唯一的.
示例1:
输入:gas = [1,2,3,4,5]，cost = [3,4,5,1,2]

输出:3

解释:
从3号加油站(索引为3 处)出发，可获得4升汽油。此时油箱有 =0+4=4升汽油
开往 4号加油站，此时油箱有4-1+5=8升汽油

开往0号加油站，此时油箱有8-2+1=7升汽油

开往 1号加油站，此时油箱有7-3+2=6升汽油

开往 2 号加油站，此时油箱有6-4+3=5升汽油
开往 3号加油站，你需要消耗5升汽油，正好足够你返回到3号加油站。
因此 ，3可为起始索引。

解法1：暴力->枚举

1.依次枚举所有起点；

2.从起点开始，模拟一遍加油的流程即可

public class Solution1 {public int canCompleteCircuit(int[]gas,int[] cost){int n=gas.length;for(int i=0;i<n;i++)//依次枚举所有的起点{int rest=0;//统计净收益for(int step=0;step<n;step++)//枚举向后走的步数{int index=(i+step)%n;//走step不之后的下标rest=rest+gas[index]-cost[index];if(rest<0){break;}}if(rest>=0){return i;}}return -1;}public static void main(String[] args) {Solution1 solution1=new Solution1();int []gas={1,2,3,4,5};int []cost={3,4,5,1,2};System.out.println(solution1.canCompleteCircuit(gas,cost));}
}

解法2：贪心:时间复杂度O（n)：

public class Solution2 {public int canCompleteCircuit(int[]gas,int[] cost){int n=gas.length;for(int i=0;i<n;i++)//依次枚举所有的起点{int rest=0;//统计净收益int step=0;for(;step<n;step++)//枚举向后走的步数{int index=(i+step)%n;//走step不之后的下标rest=rest+gas[index]-cost[index];if(rest<0){break;}}if(rest>=0){return i;}i=i+step;//贪心优化}return -1;}public static void main(String[] args) {Solution2 solution2=new Solution2();int []gas={1,2,3,4,5};int []cost={3,4,5,1,2};System.out.println(solution2.canCompleteCircuit(gas,cost));}}