バス停間の距離Leetcodeソリューション


難易度 簡単に
よく聞かれる Google
配列

バス停間の距離の問題LeetcodeSolutionは私たちに 配列 隣接する都市間の距離を表す整数の。 都市は循環順に与えられます。 したがって、最後の都市の後に最初の都市が続きます。 ここで、指定されたXNUMXつの都市間の最小距離を見つける必要があります。 したがって、ソリューションに移る前に。 いくつかの例を見てみましょう。

バス停間の距離Leetcodeソリューション

distance = [1,2,3,4], start = 0, destination = 1
1

説明:循環順に配置された都市は上の画像に示されています。 ここで、この例では、開始都市として都市0が提供され、目的地として都市1が提供されています。 したがって、都市0から開始して都市1に到達する方法は0つあります。 都市1から0に移動するか、3から3、2から2、1から0のパスをたどることができます。次に、両方向から移動する距離を計算し、最小距離を返します。 最初のパス1から1では、移動距離= 9である必要があり、他のパスでは、移動距離= 1である必要があります。したがって、最小距離はXNUMX単位です。

distance = [1,2,3,4], start = 0, destination = 2
3

説明:上記の例で行ったように、両方向の距離を計算し、最小値を返します。 3つのパスの長さは7と3であるため、XNUMXつの最小値であるXNUMXを選択します。

バス停間の距離のアプローチLeetcodeソリューション

バス停間の距離LeetcodeSolutionは、出発都市と目的都市が指定されている場合に移動に必要な最小距離を見つけるように求められました。 目的地に到達する方法はXNUMXつしかないため、問題は単純です。 XNUMXつは前進する方向から始め、もうXNUMXつは後退して目的地に到達する方向です。 一方の旅の距離を見つけることができ、もう一方の旅は、合計からこの距離を引くことで簡単に計算できます。

都市の総数が2である都市5から10に移動する必要があるとします。次に、2から5に移動するか、5から10に移動し、次に10から1に移動し、次に1から2に移動します。両方のパスの和集合は回路全体です。 したがって、距離を差し引いて、他の旅の距離を取得できます。

コード

バス停間の距離のC ++コードLeetcodeソリューション

#include<bits/stdc++.h>
using namespace std;

int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    if(start>destination)swap(start, destination);
    int total = 0, first_path = 0;
    for(int i=0;i<distance.size();i++){
        if(i>=start && i<destination)
        first_path += distance[i];
        total += distance[i];
    }
    return min(total - first_path, first_path);
}

int main(){
    vector<int> distance = {1, 2, 3, 4};
    cout<<distanceBetweenBusStops(distance, 0, 1);
}
1

バス停間の距離のJavaコードLeetcodeソリューション

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int distanceBetweenBusStops(int[] distance, int start, int destination) {
        if(start>destination){
            int t = start;
            start = destination;
            destination = t;
        }
        int total = 0, first_path = 0;
        for(int i=0;i<distance.length;i++){
            if(i>=start && i<destination)
            first_path += distance[i];
            total += distance[i];
        }
        return Math.min(total - first_path, first_path);
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] distance = {1, 2, 3, 4};
    System.out.println(distanceBetweenBusStops(distance, 0, 1));
  }
}
1

複雑さの分析

時間の複雑さ

オン)、 ここで、Nは都市の数です。 私たちはすべての都市を旅しなければならなかったので。 時間計算量は線形です。

スペースの複雑さ

O(1)、 変数をXNUMXつだけ使用したためです。 スペースの複雑さは一定です。