Gas Station
程序员文章站
2022-06-07 11:38:33
...
解析:
比较容易想到的一种解法
1.从所有加油站里面选择一个可以到达下一个地点的加油站作为起点
2.从起点出发,依次计算到达每个加油站所剩余的油量,若中间出现剩余油量小于0,则无法到达,重新选择下一个加油站;反之,输出起点
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int max_index = cost.size();
for (int start = 0; start < max_index; ++start){
if (gas[start] < cost[start]) continue;
int tank = 0;
int movPos = start; //起点
while (tank >= 0){
tank += gas[movPos] - cost[movPos]; //开往下一站后还剩余的汽油
if (tank < 0) break;
movPos = (movPos + 1) % max_index; //开往下一站
if (movPos == start) return start;
}
}
return -1;
}
};
第二种解法
主要涉及到一个知识点:当总油量大于消耗的油量时,一定可以从某个起点出发,到达终点,即回到起点。
基于上面的分析,total表示总油量,start表示起点的位置,sum代表从起点出发,到达某个位置所剩余的油量
1.从start开始,前往下一站,如果当前sum的值大于或等于0,可以继续前往下一站;反之,无法到达下一站。则从start位置之前的所有位置,同样也无法回到起点,可以选择从start的下一个位置开始
2.,total大于或等于0,则说明可以到达,输出start;反之,无法到达,输出-1.
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int sum = 0;
int index = 0, total = 0;
for(int start = 0; start < gas.size(); ++start){
sum += gas[start] - cost[start];
total += gas[start] - cost[start]; //总的汽油
if (sum < 0){ //当前起点无法到达终点
index = start + 1; //从下一个位置开始
sum = 0;
}
}
return total < 0 ? -1 : index;
}
};
[1]https://www.cnblogs.com/grandyang/p/4266812.html
推荐阅读
-
vmware station-ubuntu18.04 共享剪贴板
-
【代码超详解】POJ 2031 Building a Space Station(Kruskal 算法求最小生成树)
-
PAT-A-1072 Gas Station 【Dijkstra】
-
POJ 2031 Building a Space Station G++ 最小生成树 Kruskal实现 prim未实现
-
Unreal Engine 4 —— GAS系统学习 (八) 为敌人增加血条并关联伤害数据
-
2019 ICPC Asia Nanjing Regional I. Space Station题解
-
PTA甲级 1072 Gas Station (30分)
-
【PAT A1072】Gas Station
-
[PAT-A 1072]Gas Station
-
1072 Gas Station [dj]