首页 > 代码库 > 【leetCode百题成就】Gas Station解题报告
【leetCode百题成就】Gas Station解题报告
题目：
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station‘s index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
地址：
https://oj.leetcode.com/problems/gas-station/
思路：
O(n^2) 的不用闲扯，谁都懂。问题是O(n) 的算法应该如何设计。方法如下：
定义：
存油：卡车带进某个加油站的油量。依题意，初始存油为0.
0、设定初始起点和终点为0.
1、从起点开始，走到不能走为止，设此时不能走的结点为i。则0到i之间的所有结点都不可能为起点。因为从起点开始只有0升油，从起点经过的结点存油可能为正值但至少为0，所以如果以0存油开始，到i一样过不去。
2、起点倒退，追踪i点存油量，直到能过i点为止。
3、回到第一步
证明：
每个结点最多访问一次，O(n)
AC代码：
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int start = 0;
int fin = 0;
int oil = 0; // 带入的油
int tmpoil = 0;
int len = gas.size();
if (fin == lastPos(start,len))
return gas[0] >= cost[0] ? 0 : -1;
do
{
int tmpfin = fin; // 我在tmpfin能前进吗？
while (tmpfin != lastPos(start,len) && ((tmpoil = walk2next(oil,tmpfin,gas,cost))) >= 0)
{
tmpfin = nextPos(tmpfin,len);
oil = tmpoil;
}
if (tmpfin == lastPos(start,len))
return start;
fin = tmpfin;
do
{
start = lastPos(start,len);
if (start == fin)
return -1;
int tmp = gas[start] - cost[start]; // tmp指的是具体某点0油出发到下一点后的剩余油量
tmpoil += tmp;
} while (tmpoil < 0);
oil = tmpoil; // 补到能够进入下一点为止，此时oil为补够了的剩余量
fin = nextPos(fin,len); // 进入下一点
} while (fin != start); // 由于进入了下一点，所以为start的话，就成功。
return start;
}
int lastPos(int index,int len)
{
if (index == 0)
return len - 1;
else
return index - 1;
}
int nextPos(int index,int len)
{
return (index + 1) % len;
}
int walk2next(int oil,int index,vector<int> &gas,vector<int> &cost)
// 带有oil的油量进入index，要走的下个点缺/剩多少油
{
int total = oil + gas[index];
return total - cost[index];
}
};
后记：
当你用while很艰难时，请用do while
【leetCode百题成就】Gas Station解题报告