Разстояние между автобусните спирки Leetcode Solution


Ниво на трудност Лесно
Често задавани в Google
Array

Проблемът Разстояние между автобусните спирки Leetcode Solution ни предоставя масив на цели числа, описващи разстоянието между съседните градове. Градовете са дадени в кръгов ред. И така, последният град е последван от първия град. Сега от нас се изисква да открием минималното разстояние между двата дадени града. Така че, преди да преминете към решението. Нека да видим няколко примера.

Разстояние между автобусните спирки Leetcode Solution

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

Обяснение: Градовете, подредени в кръгов ред, са показани на изображението по-горе. Тук, в примера, ни е предоставен град 0 като начален град и град 1 като дестинация. И така, има два начина да започнете от град 0 и да стигнете до city1. Или можем просто да преминем от град 0 до 1. Или можем да следваме пътя от 0 до 3, 3 до 2, 2 до 1. Сега ще изчислим разстоянието, което трябва да бъде изминато от двете посоки, и ще върнем минималното разстояние. Първият път 0 до 1 изисква да изминем разстояние = 1, докато другият път изисква да изминем разстояние = 9. По този начин минималното разстояние е 1 единица.

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

Обяснение: Точно както направихме в горния пример, изчисляваме разстоянието в двете посоки и връщаме минимума. Тъй като двата пътя са с дължина 3 и 7. Избираме минимума от двата, който е 3.

Подход за разстоянието между автобусните спирки Leetcode Solution

Проблемът Разстояние между автобусните спирки Leetcode Solution поиска да се намери минималното разстояние, необходимо за пътуване, ако ни се даде начален град и град на местоназначение. Проблемът е прост, защото може да има само два начина да стигнете до дестинацията. Единият е, ако започнем по посока на движение напред, а другият се движим назад и стигаме до дестинацията. Можем да намерим разстоянието за едно от пътуванията, а другото можем лесно да изчислим, като извадим това разстояние от общото.

Помислете, трябва да преминем от град 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), тъй като използвахме само една променлива. Сложността на пространството е постоянна.