算法题：加油站
2017-12-05
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油gas[ i ]，并且从第 i 个加油站前往第 i+1 个加油站需要消耗汽油cost[ i ]。
你有一辆油箱容量无限大的汽车，现在要从某一个加油站出发绕环路一周，一开始油箱为空。
写一个函数求可环绕环路一周时出发的加油站的编号，若不存在环绕一周的方案，则返回-1。
注意事项：
1、数据保证答案唯一。
2、O(n)时间和O(1)额外空间
格式：
输入行依次输入一个表示每个加油站的汽油的容量的数组 gas 和一个表示加油站之间耗油量的数组 cost ，
最后输出可环绕一周的加油站的编号，如果不存在则返回 -1。
样例输入
gas = [ 1，1，3，1 ]
cost = [ 2，2，1，1 ]
样例输出
2
*/
/*
* 方法：
* sum 从第一个加油站开始遍历，统计经过的加油站减去加油站之间的消耗的汽油的和，小于0，此加油站开始不可取
* total统计每个加油站减去加油站之间的消耗的汽油的总和
* num 确定的加油站开始值
* */
public class GasStation {
private int sum = 0;
private int total = 0;
private int num = 0;
public int GasCircle(int gas[],int cost[]){
for(int i = 0;i<gas.length;i++){
sum = sum + gas[i] - cost[i];
total = total + gas[i] - cost[i];
if(sum < 0){
num = i;
sum = 0;
}
}
if(total < 0){
return -1;
}else{
return num + 1;
}
}
public static void main(String[] args) {
int []gas = {1,1,3,1};
int []cost= {2,2,1,1};
GasStation gasstation = new GasStation();
System.out.println(gasstation.GasCircle(gas, cost));
}
}
如有错误和疑问欢迎指出赐教
