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

文章目录

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

创新互联是一家以重庆网站建设公司、网页设计、品牌设计、软件运维、成都网站营销、小程序App开发等移动开发为一体互联网公司。已累计为效果图设计等众行业中小客户提供优质的互联网建站和软件开发服务。

---

前言

贪心法

---

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

一、加油站问题

在一条环路上有 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元起，快前往官网查看详情吧

文章名称：Java-加油站问题-创新互联
文章源于：http://6mz.cn/article/dggdgi.html