Java-加油站问题-创新互联

• 前言
• 一、加油站问题
• 二、问题分析
• 总结

贪心法

提示：以下是本篇文章正文内容，下面案例可供参考

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

注：此处原题输出的是索引编号

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/gas-station
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

把这个题理解成下边的图就可以。
每个节点表示添加的油量，每条边表示消耗的油量。题目的意思就是问我们从哪个节点出发，还可以回到该节点。只能顺时针方向走。

其实如果把题目换个角度考虑可能就比较好理解了，如果总油量减去总消耗大于等于零那么一定可以跑完一圈，因此要跑完一圈就要保证在各个站点的加油站 剩油量 gas[i] - cost[i]>=0。

局部最优：若从start累加到end 的和 curSum<0 ，起始位置至少要是 end+1 ，因为从 end 开始一定不行。

全局最优：找到可以跑一圈的起始位置。

代码及运行结果：

package gas_station;

import java.util.Scanner;

public class Gas {public static int canCompleteCircuit(int[] gas, int[] cost) {int cursum = 0;// 从前一个加油站作为start开始，到当前加油站的剩余量
		int sum = 0;// 总的油量是否支持返回起点
		int start = 0;// 设置起点

		for (int i = 0; i< gas.length; i++) {	cursum += gas[i] - cost[i];
			sum += gas[i] - cost[i];
			if (cursum< 0) {		// cursum<0表示从上一个加油站无法直达当前加油站，所以将起点放到下一个加油站，并把cursum清零
				start = gas[i + 1];
				cursum = 0;
			}
		}
		if (sum< 0) {	return -1;
		}
		return start;
	}

	public static void main(String[] args) {System.out.println("输入加油站序号");
		Scanner sc1 = new Scanner(System.in);
		String src1 = sc1.next().toString();
		String[] sr1 = src1.split(",");
		int[] gas = new int[sr1.length];
		for (int i = 0; i< gas.length; i++) {	gas[i] = Integer.parseInt(sr1[i]);
		}

		System.out.println("输入加油站蓄油量");
		Scanner sc2 = new Scanner(System.in);
		String src2 = sc2.next().toString();
		String[] sr2 = src2.split(",");
		int[] cost = new int[sr1.length];
		for (int i = 0; i< cost.length; i++) {	cost[i] = Integer.parseInt(sr2[i]);
		}

		int result = canCompleteCircuit(gas, cost);
		System.out.println("加油站地点为：" + result + "号加油站");
	}

}

此处我的输出是加油站的序号，与原题有所区别

如果有不清楚可以标注断点，dubug观察 一下

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧