主題

LeetCode - 1184. Distance Between Bus Stops 解題心得

Not In My Back Yard | 2021-04-01 00:00:13 | 巴幣 0 | 人氣 36

題目連結:


題目意譯:
某一台公車有 n 個站點編號為 0 到 n - 1 ,其形成一個圓圈。我們知道所有相鄰車站之間的距離,其中 distance[i] 代表著車站 i 到車站 (i + 1) % n 的距離。

公車兩個方向都會行駛,即它會順時針繞著圓圈也會逆時針繞著走。

回傳給定的起點站 start 以及終點站 destination 之間的最短距離。

限制:
1 ≦ n ≦ 10 ^ 4
distance.length == n
0 ≦ start 、 destination < n
0 ≦ distance[i] ≦ 10 ^ 4



範例測資:
範例 1:
輸入: distance = [1,2,3,4], start = 0, destination = 1
輸出: 1
解釋: 車站 0 與車站 1 之間的距離為 1 或 9,而最小的為 1。

範例 2:
輸入: distance = [1,2,3,4], start = 0, destination = 2
輸出: 3
解釋: 車站 0 與車站 2 之間的距離為 3 或 7,而最小的為 3。

範例 3:
輸入: distance = [1,2,3,4], start = 0, destination = 3
輸出: 4
解釋: 車站 0 與車站 3 之間的距離為 6 或 4,而最小的為 4。


解題思維:
直接計算即可:
假設所有距離之總和為 S。

我們先隨機朝一個方向走(逆或順),如果 start ≦ destination,我們就從 distance[start] 一路加到 distance[destination - 1];反之,我們就從 distance[destination] 加到 distance[start - 1]。

於是我們就求出了其中一個方向所走的距離 D,而另一個方向便呼之欲出,其值即 S - D。

接著就看 D 與 S - D 哪個值較小,該值即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作