公交站间的距离 : 简单模拟题

我会带着你远行 2023-10-01 22:53 8阅读 0赞

### 题目描述 ###

这是 LeetCode 上的 **[1184. 公交站间的距离][1184.]** ，难度为 **简单**。

Tag : 「模拟」

环形公交路线上有 nnn 个站，按次序从 000 到 n−1n - 1n−1 进行编号。我们已知每一对相邻公交站之间的距离，distance\[i\]distance\[i\]distance\[i\] 表示编号为 iii 的车站和编号为 `(i + 1) % n` 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 `start` 到目的地 `destination` 之间的最短距离。

示例 1：

![format_png][]

输入：distance = [1,2,3,4], start = 0, destination = 1
    
    输出：1
    
    解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
    复制代码

示例 2：

![format_png 1][]

输入：distance = [1,2,3,4], start = 0, destination = 2
    
    输出：3
    
    解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
    复制代码

示例 3：

![format_png 2][]

输入：distance = [1,2,3,4], start = 0, destination = 3
    
    输出：4
    
    解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
    复制代码

提示：

*  1<=n <=1041 <= n <= 10^41<=n <=104
 *  distance.length==ndistance.length == ndistance.length==n
 *  0<=start,destination<n0 <= start, destination < n0<=start,destination<n
 *  0<=distance\[i\]<=1040 <= distance\[i\] <= 10^40<=distance\[i\]<=104

### 模拟 ###

根据题意进行模拟即可。

用 `i` 和 `j` 分别代表往前和往后走的指针，`a` 和 `b` 分别统计两种走法的总成本。

Java 代码：

class Solution {
        public int distanceBetweenBusStops(int[] dist, int s, int t) {
            int n = dist.length, i = s, j = s, a = 0, b = 0;
            while (i != t) {
                a += dist[i];
                if (++i == n) i = 0;
            }
            while (j != t) {
                if (--j < 0) j = n - 1; 
                b += dist[j];
            }
            return Math.min(a, b);
        }
    }
    复制代码

TypeScript 代码：

function distanceBetweenBusStops(dist: number[], s: number, t: number): number {
        let n = dist.length, i = s, j = s, a = 0, b = 0
        while (i != t) {
            a += dist[i]
            if (++i == n) i = 0
        }
        while (j != t) {
            if (--j < 0) j = n - 1
            b += dist[j]
        }
        return Math.min(a, b)
    };
    复制代码

*  时间复杂度：O(n)O(n)O(n)
 *  空间复杂度：O(1)O(1)O(1)

![6dd5ca10c6f4430f8013f6521646e25d.jpeg][]

[1184.]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fdistance-between-bus-stops%2Fsolution%2Fby-ac_oier-fow3%2F
[format_png]: https://img-blog.csdnimg.cn/img_convert/3e3bad6f521ab548843ea681e353c568.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/9d44976d26bfa2644200f37c6d1d0e29.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/defdac32bbdfc5f0d7fd97097b8e79d7.webp?x-oss-process=image/format,png
[6dd5ca10c6f4430f8013f6521646e25d.jpeg]: https://img-blog.csdnimg.cn/6dd5ca10c6f4430f8013f6521646e25d.jpeg