未分類

Gas Station

Go, Greedy, 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.

提示 解題應用
Greedy 規律觀查

Default:

1
2
3
func canCompleteCircuit(gas []int, cost []int) int {
}

解答思路:

既然要找出哪裡開始加油起跑能順利繞完整個圓環，一開始當然就以一迴圈遍歷整個加油點來做為起始點，有了起始點後就再以內層迴圈作為巢狀迴圈嘗試繞整個圓環，而因為油箱沒有油量限制，所以每次經過加油點一定都要加到底並同時將總油量減去耗油量，如果總油量有剩表示能撐到下一個加油點，而如果油量不夠就放棄再重新以下一個新的加油點來做為起始點直到找出目標起始點，最後記得因為是以陣列來表示圓環，所以每次index都要記得與陣列長度相除取餘數，才能在index超出陣列範圍時能回到陣列開頭以繼續遍歷圓環。

程式碼解說:

因為如果不存在能順利繞完整個圓環的起始點要回傳-1，所以先將結果值初始化為-1，接著以一迴圈遍歷整個加油點來做為起始點，每次開始一趟旅程當然也要先將油箱清空歸0才開始，並將結果值暫存目前的起始點，再以內層迴圈作為巢狀迴圈嘗試繞整個圓環(起始點位置+前進的距離作為index)，每次index都要記得與陣列長度相除取餘數以避免超出陣列範圍，經過加油點一定都要加到底並同時將總油量減去耗油量，如果總油量有剩(大於等於0)表示能撐到下一個加油點繼續往下開，否則將結果值改回-1，再以下一個新的加油點來做為起始點重新開始，最後如果發現結果值不為-1表示順利繞整個圓環，此時就不需要再找新的起始點便結束迴圈回傳該index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var index int
var gasSum int
result := -1
for start, _ := range gas {
	gasSum = 0
	result = start
	for i := 0; i < len(gas); i++ {
		index = (start + i) % len(gas)
		gasSum += gas[index] - cost[index]
		if gasSum < 0 {
			result = -1
			break
		}
	}
	if result != -1 {
		break
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func canCompleteCircuit(gas []int, cost []int) int {
	var index int
	var gasSum int
	result := -1
	for start, _ := range gas {
		gasSum = 0
		result = start
		for i := 0; i < len(gas); i++ {
			index = (start + i) % len(gas)
			gasSum += gas[index] - cost[index]
			if gasSum < 0 {
				result = -1
				break
			}
		}
		if result != -1 {
			break
		}
	}
	return result
}

總結:

有兩串陣列分別記錄圓環路徑上能加油的量與耗油量，要回傳從哪裡開始加油起跑能順利繞完整個圓環，先以一迴圈遍歷整個加油點來做為起始點，再以內層迴圈作為巢狀迴圈嘗試繞整個圓環，每次經過加油點一定都要加到底並同時將總油量減去耗油量，如果總油量有剩表示能撐到下一個加油點，而如果油量不夠就放棄再重新以下一個新的加油點來做為起始點直到找出目標起始點為止。

分享到