1184. Distance Between Bus Stops

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation