LeetCode——Gas Station
1182 ワード
There are N gas stations along a circular route, where the amount of gas at station i is
You have a car with an unlimited gas tank and it costs
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/
テーマ:一つのリングにN個のガソリンスタンドがあり、ステーションiにはgas[i]のガソリンがある.
駅iから駅i+1までcost[i]のガソリンを消費する車があります.空きタンクでその中の1つの駅から出発します.一周したら、ガソリンスタンドのインデックスに戻ります.そうしないと-1に戻ります.
構想:まず車が各ガソリンスタンドに到着する際のガソリンスタンドの油量と自動車消費の油量の差を計算し、もし差が0未満であれば、自動車は少なくとも次の駅から出発しなければならないことを説明し、当駅から出発すると、次の駅に到着できないからだ.合計の差が0より小さいと、車は一周できません.
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/
テーマ:一つのリングにN個のガソリンスタンドがあり、ステーションiにはgas[i]のガソリンがある.
駅iから駅i+1までcost[i]のガソリンを消費する車があります.空きタンクでその中の1つの駅から出発します.一周したら、ガソリンスタンドのインデックスに戻ります.そうしないと-1に戻ります.
構想:まず車が各ガソリンスタンドに到着する際のガソリンスタンドの油量と自動車消費の油量の差を計算し、もし差が0未満であれば、自動車は少なくとも次の駅から出発しなければならないことを説明し、当駅から出発すると、次の駅に到着できないからだ.合計の差が0より小さいと、車は一周できません.
public int canCompleteCircuit(int[] gas, int[] cost) {
int minus = 0, total = 0, index = -1;
for (int i = 0; i < gas.length; i++) {
minus += gas[i] - cost[i];
total += minus;
if (minus < 0) {
index = i;
minus = 0;
}
}
return total < 0 ? -1 : index + 1;
}