幾道加油站加油相關問題

1.選一個加油站能走完一圈：leetcode134. Gas Station
2.加油最少次數(easy)
3.加油最少次數(hard)：leetcode871. Minimum Number of Refueling Stops

題目：1.leetcode134. 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 in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

題目描述：

若干車站排列在一個環形上，每個車站給出儲油量和到下一個車站的耗油量，選一個位置能走完一圈，回到出發位置。

解法：

從某個位置開始如果lack+gas>cost，則繼續往后遍歷，并記錄下剩余的汽油，如果<則油不夠，此時從下一個開始lack=0，從新遍歷如果還不行的話繼續從下一個位置重復，如果最后剩下的汽油能補上之前不夠的，則可以完成一圈從下一個開始，而不從頭到當前位置中的某個開始是因為，前面的每次都會剩下，從頭已經是最優。

class Solution { public:/*從某個位置開始如果lack+gas>cost，則繼續往后遍歷，并記錄下剩余的汽油，如果<則油不夠，此時從下一個開始lack=0從新遍歷如果還不行的話繼續從下一個位置重復，如果最后剩下的汽油能補上之前不夠的，則可以完成一圈從下一個開始，而不從頭到當前位置中的某個開始是因為，前面的每次都會剩下，從頭已經是最優。*/int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int res=0;int temp=0;int lack=0;for(int i=0;i<gas.size();++i){lack+=gas[i]-cost[i];if(lack<0){temp+=lack;lack=0;res=i+1;}}return lack+temp>=0?res:-1;} };

題目：2.加油最少次數

一輛汽車加滿油后可行駛n公里，假設汽車在起點是加滿油的。
旅途中有若干個加油站。設計一個有效算法，指出應在哪些加油站停靠加油，
使到達終點的沿途加油次數最少。
對于給定的n和k個加油站位置，編程輸出停靠加油站的位置。
例如：
n = 100
k = 5
d = [50,80,39,60,40,32] （表示加油站之間的距離）

思路

在可以到達某個加油站時候，可以每個加油站判斷不加油能不能到下一個，如果可以則不加油繼續走；不可以的的話，加滿油，繼續走，記錄下當前車站位置

bool count(vector<int>d,int n){vector<int>station;//保存加油的位置if(n-d[0]<0)return -1;elsen = n-d[0];for(int i=1;i<=k;++i){ //0 1 2 3 4 5 6if(i==k&&n-d[i]>=0){return 1;}else if(i==k&&n-d[i]<0){return -1;}if(n-d[i]>=0){n=n-d[i];}else if(n-d[i]<0){station.push_back(i);n=100;}}}

題目：3.leetcode871. Minimum Number of Refueling Stops

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.
Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can’t reach the target (or even the first gas station).
Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation:
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

題目描述：

汽車可以無限儲油，給一個目的距離，初始油量，以及路上按順序每個加油站的距離和儲油量，求最少加油次數，到不了終點返回-1；

思路

到達某個加油站不加油，而是把每個加油站的油存放在一個優先隊列，這樣一旦油不夠就可以從優先隊列找最大的存進去，不夠繼續找(只要隊列不空)；
注意需要把重點push到隊列中去

class Solution { public://用一個優先隊列保存每個位置的油，這樣每次取到的都是油最多的位置；//油箱里的油大于等于當前距離則通過，小于則從經過的位置找一個油最多的加進去，加油次數res++，如果加完油不夠則繼續找，一直到隊列空還不夠返回-1；//遍歷每個位置都需要把當前位置的油存儲量加入隊列，以備后面使用。int minRefuelStops(int target, int startFuel, vector<vector<int> >& stations) {priority_queue<int>pq;int res=0;int loc=0;vector<int>last_station;last_station.push_back(target);last_station.push_back(0);stations.push_back(last_station);for(int i=0;i<stations.size();++i){while(!pq.empty()&&startFuel<stations[i][0]){int max_gas=pq.top();startFuel+=max_gas;pq.pop();res++;cout<<"res:"<<res<<endl;}cout<<startFuel<<" "<<stations[i][0]<<endl;if(pq.empty()&&startFuel<stations[i][0]){cout<<-1;return -1;}//else{//startFuel-=stations[i][0];//loc+=stations[i][1];//}pq.push(stations[i][1]);}return res;} };

總結

以上是生活随笔為你收集整理的几道加油站加油相关问题：最小加油次数、能否回到起点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。