A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.
The bus goes along both directions i.e. clockwise and counterclockwise.
Return the shortest distance between the given start and destination stops.
Example 1:
Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.
Example 2:
Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.
Example 3:
Constraints:
- 1 <= n <= 10^4
- distance.length == n
- 0 <= start, destination < n
- 0 <= distance[i] <= 10^4
Solution:
class Solution:
def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
if destination < start:
start, destination = destination, start
clockwise = sum(distance[start : destination])
cnt_clockwise = sum(distance) - clockwise
return min(clockwise, cnt_clockwise)
Explanation:
For this question, we just need to find the sum of distances of stops between start and destination, both clockwisely or counterclockwisely. Then we pick the minimum of these to as our answer. Just keep in mind that start could be greater than destination, so the clockwise and counterclockwise distance will be swapped in this case. Since we just need to find the minimum and don't care about directions(i.e. we don't care whether the minimal is from clockwise or counterclockwise), we can swap the start and destination at the beginning to make sure start is always less than destination, thus making our life easier.
本題我們只需要找到順時(shí)針或逆時(shí)針之間起點(diǎn)和終點(diǎn)之間的驮髅睿靠點(diǎn)距離之和即可旋炒。然后霎桅，我們選擇其中的最小值作為答案旅择。需要注意的是 start 可能大于destination，因此在這種情況下预麸，順時(shí)針和逆時(shí)針距離將完全相反瞪浸。由于我們只需要找到兩者最小值，而不關(guān)心具體方向（我們不關(guān)心這個(gè)最小值是來自順時(shí)針或者逆時(shí)針）吏祸，因此我們完全可以在一開始時(shí)交換起點(diǎn)和終點(diǎn)对蒲，使解題更輕松。
