Відстань між автобусними зупинками


Рівень складності Легко
Часто запитують у Google
масив

Проблема "Відстань між автобусними зупинками", рішення 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 одиницю.

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

Пояснення: Так само, як це було зроблено у наведеному вище прикладі, ми обчислюємо відстань в обох напрямках і повертаємо мінімум. Оскільки два шляхи мають довжину 3 і 7. Ми обираємо мінімум з двох, тобто 3.

Підхід до відстані між автобусними зупинками

Проблема Відстань між зупинками автобусів Leetcode Solution попросила знайти мінімальну відстань, необхідну для подорожі, якщо нам дано вихідне місто та місто призначення. Проблема проста, оскільки до пункту призначення можна дістатися лише двома способами. Один - якщо ми починаємо в напрямку руху вперед, а інший рухається назад і досягаємо пункту призначення. Ми можемо знайти відстань для однієї з подорожей, а іншу можна легко розрахувати, віднявши цю відстань від загальної.

Поміркуйте, нам потрібно перейти від міста 2 до 5, де загальна кількість міст дорівнює 10. Тоді ми або переходимо від 2 до 5. Або переходимо від 5 до 10, потім 10 до 1, а потім 1 до 2. Результат об'єднання обох шляхів - це вся схема. Таким чином, ми можемо відняти відстань, щоб отримати відстань для іншої подорожі.

код

Код C ++ для рішення відстані між шинами, що зупиняється

#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-код для відстані між автобусними зупинками

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

Аналіз складності

Складність часу

O (N), де N - кількість міст. Оскільки нам довелося подорожувати по всіх містах. Складність часу лінійна.

Складність простору

O (1), оскільки ми використовували лише одну змінну. Складність простору постійна.