Joyce' Blog
0%

gas-station

发表于

题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

  • 如果题目有解，该答案即为唯一答案。
  • 输入数组均为非空数组，且长度相同。
  • 输入数组中的元素均为非负数。

题解

gas<cost的点一定不会是起点，根据这一点，筛选出可能是起点的编号，然后对每一个编号进行计算模拟行驶过程，若计算中出现负数，则考虑下一个；若结果为非负数，则直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
	int vsize = gas.size();
	vector<int> lefts,prob;
	int sum = 0;
	for (int i = 0; i < vsize; i++)
	{
		int t = gas[i] - cost[i];
		sum += t;
		lefts.push_back(t);
		if (t >= 0)
			prob.push_back(i);
	}
	if (sum < 0)return -1;

	//处理有可能是起点的编号集合
	int num = prob.size();
	int start = prob[0];
	for (int i = 0; i < num; i++)
	{
		start = prob[i];
		int oil = 0;
		int k = 0;
		while (k<vsize)
		{
			oil += lefts[(start + k) % vsize];
			if (oil < 0)
				break;
			k++;
		}
		if (oil >= 0)return start;
	}
	return start;
}

效率低得可怜，但至少是自创。

还看到一个高效巧妙的方法：为了让总油量剩余值（黑色折线）任意部分都不小于0（都在X轴以上），需要向上移动黑色折线，直到所有点都在X轴或X轴以上。此时，处在X轴的点即为出发点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
{
	int vsize = gas.size();
	int spare = 0;
	int minSpare = INT_MAX;
	int minIndex = 0;
	for (int i = 0; i < vsize; i++)
	{
		spare += (gas[i] - cost[i]);
		if (spare < minSpare)
		{
			minSpare = spare;
			minIndex = i;
		}
	}
	if (spare < 0)return -1;
	return (minIndex + 1) % vsize;
}