[LeetCode] 1184. Distance Between Bus Stops

[grandyang]

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:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Constraints:

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

这道题说是有n个公交站形成了一个环，它们之间的距离用一个数组 distance 表示，其中 distance[i] 表示公交站i和 (i+1)%n 之间的距离。说是公交可以顺时针和逆时针的开，问给定的任意起点和终点之间的最短距离。对于一道 Easy 题的身价，没有太多的技巧而言，主要就是考察了一个循环数组，求任意两个点之间的距离，由于两个方向都可以到达，那么两个方向的距离加起来就正好是整个数组之和，所以只要求出一个方向的距离，另一个用总长度减去之前的距离就可以得到。所以这里先求出所有数字之和，然后要求出其中一个方向的距离，由于处理循环数组比较麻烦，所以这里希望 start 小于 destination，可以从二者之间的较小值遍历到较大值，累加距离之和，然后比较这个距离和，跟总距离减去该距离所得结果之间的较小值返回即可，参见代码如下：

解法一：

class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        int total = accumulate(distance.begin(), distance.end(), 0), cur = 0, mx = max(start, destination);
        for (int i = min(start, destination); i < mx; ++i) {
            cur += distance[i];
        }
        return min(cur, total - cur);
    }
};

我们也可以只要一次遍历就可以完成，因为最终都要是要遍历所有的站点距离，当这个站点在 [start, destination) 范围内，就累加到 sum1 中，否则就累加到 sum2 中。不过要要注意的是要确保 start 小于 destination，所以可以开始做个比较，若不满足则交换二者。最终返回 sum1 和 sum2 中较小者即可，参见代码如下：

解法二：

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

Github 同步地址:

#1184

参考资料：

https://leetcode.com/problems/distance-between-bus-stops/

https://leetcode.com/problems/distance-between-bus-stops/discuss/377568/C%2B%2B-one-pass

https://leetcode.com/problems/distance-between-bus-stops/discuss/377444/Java-O(n)-solution-Easy-to-understand

LeetCode All in One 题目讲解汇总(持续更新中...)