[LeetCode] 134. Gas Station

轉自LeetCode

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.

<Solution>
這題有個線性的解法，時間複雜度是O(N)

想法如下

• 用兩個指標分別代表起始點和終點，雙方向彼此靠近，當 start = end 的時候，代表所有點都已經走過

• 檢查 gas 的總量，如果大於等於零，代表可以全程走完；如果小於零，代表無法走完

這邊有個特別的地方要注意

在初始的時候，start = size() - 1，end = 0

這是要避免雙方向彼此靠近的時候，會有沒有檢查的點

行進方向都是從 start 走向 end

如果 start = 0，end = size() - 1

X         X         X         X         X         X
start->                                       <- end   (指標移動方向)

可以看到，當兩個指標互相靠近的時候，其實雙方的距離是變短的

因此會有少掉的點沒有檢查到，並且要去處理一些 corner cases

而如果 start = size() - 1，end = 0

X         X         X         X         X         X
end->                                       <- start   (指標移動方向)

當兩個指標互相靠近的時候，雙方的距離是拉長的，因此這樣會檢查到所有的點

code 如下(參考資料)
c++

	class Solution {
	public:
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
	int start = cost.size() - 1;
	int end = 0;
	int totalGas = gas[start] - cost[start];;
	while(start > end) {
	if(totalGas >= 0) {
	//>> gas is enough, go further
	totalGas += gas[end] - cost[end];
	++end;
	}
	else {
	//>> gas is not enough, find new start point
	--start;
	totalGas += gas[start] - cost[start];
	}
	}
	return (totalGas >= 0) ? start : -1;
	}
	};

view raw gasStationTraversal.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
	var start = gas.lastIndex
	var end = 0
	var totalGas = gas[start] - cost[start]
	while(start > end) {
	if(totalGas >= 0) {
	//>> we can go further
	totalGas += gas[end] - cost[end]
	++end
	} else {
	//>> gas is not enough, find another start point
	//>> and see can we get more gas
	--start
	totalGas += gas[start] - cost[start]
	}
	}
	return if(totalGas >= 0) start else -1
	}
	}

view raw gas_station.kt hosted with ❤ by GitHub