Leetcode 1184. distance between bus stops

【LetMeFly】1184. The distance between bus stops

Force button topic link ：https://leetcode.cn/problems/distance-between-bus-stops/

There are... On the circular bus route  n  Individual station , From  0  To  n - 1  Number . We know the distance between each pair of adjacent bus stops ,distance[i]  Indicates that the number is  i  The station and number are  (i + 1) % n  The distance between the stations .

The buses on the loop line can travel clockwise and counterclockwise .

Return passengers from the starting point  start  Destination  destination  The shortest distance between .

 

Example 1：

 Input ：distance = [1,2,3,4], start = 0, destination = 1
 Output ：1
 explain ： Bus stop  0  and  1  The distance between them is  1  or  9, The minimum is  1.

 

Example 2：

 Input ：distance = [1,2,3,4], start = 0, destination = 2
 Output ：3
 explain ： Bus stop  0  and  2  The distance between them is  3  or  7, The minimum is  3.

 

Example 3：

 Input ：distance = [1,2,3,4], start = 0, destination = 3
 Output ：4
 explain ： Bus stop  0  and  3  The distance between them is  6  or  4, The minimum is  4.

 

Tips ：

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

Method 1 ： simulation

Since the bus is two-way , Then why don't you calculate “ from $start$ and $destination$ The one with the smaller number in the middle to the one with the larger number Distance of ”$s1$

Then calculate the total distance of a lap $s$

Then the distance to take the bus in the other direction is $s-s1$

return $s1$ and $s-s1$ The smaller one is ok

• Time complexity $O(n)$, among $n$ It's the number of bus stops
• Spatial complexity $O(1)$

AC Code

C++

class Solution {
    
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    
        if (start > destination) swap(start, destination);
        int s1 = 0;
        for (int i = start; i < destination; i++) {
    
            s1 += distance[i];
        }
        int s = 0;
        for (int i = 0; i < distance.size(); i++) {
    
            s += distance[i];
        }
        return min(s1, s - s1);
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125960214