Avtobus dayanacaqları arasındakı məsafə Leetcode həll

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 29

Avtobus dayanacaqları arasındakı problem Leetcode Həlli bizə bir təmin edir array bitişik şəhərlər arasındakı məsafəni təsvir edən tam ədədi. Şəhərlər dairəvi qaydada verilir. Beləliklə, son şəhəri birinci şəhər izləyir. İndi verilən iki şəhər arasındakı minimum məsafəni tapmağımız tələb olunur. Beləliklə, həll yoluna keçmədən əvvəl. Bir neçə misala baxaq.

Avtobus dayanacaqları arasındakı məsafə Leetcode həllPin

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

İzahat: Dairəvi qaydada düzülmüş şəhərlər yuxarıdakı şəkildə göstərilmişdir. Burada, nümunədə, başlanğıc şəhəri olaraq 0 şəhəri və təyinat yeri olaraq şəhər 1 təmin olunur. Beləliklə, 0 şəhərindən başlayıb şəhərə1 çatmağın iki yolu var. Ya sadəcə şəhərdən 0-a 1-ə gedə bilərik. Və ya 0-dan 3-ə, 3-dən 2-yə, 2-dən 1-ə qədər olan yolu izləyə bilərik. İndi hər iki yoldan keçiləcək məsafəni hesablayacağıq və minimum məsafəni geri qaytaracağıq. İlk yol 0-dan 1-ə qədər, digər yol isə = 1 məsafəni qət etməyimizi tələb edir, beləliklə minimum məsafə 9 vahiddir.

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

İzahat: Yuxarıdakı nümunədə etdiyimiz kimi, məsafəni hər iki istiqamətdə hesablayırıq və minimumu qaytarırıq. İki yolun uzunluğu 3 və 7 olduğundan, ikisinin minimumunu 3-ə seçirik.

Avtobus dayanacaqları arasındakı məsafəyə yanaşma Leetcode həll

Avtobus Dayanacaqları Arasındakı Məsələ Leetcode Həlli, başlanğıc şəhər və təyinat şəhəri bizə verilsə səyahət üçün lazım olan minimum məsafəni tapmasını istədi. Problem çox sadədir, çünki hədəfə çatmağın yalnız iki yolu ola bilər. Biri irəliləməyə, digəri geriyə doğru hərəkət edib təyinat nöqtəsinə çatmaq istiqamətində başlayırıqsa. Səfərlərdən biri üçün məsafəni tapa bilərik, digəri isə bu məsafəni cəmdən çıxartmaqla asanlıqla hesablana bilər.

Fikir verin, şəhərlərin ümumi sayı 2 olduğu şəhərdən 5-yə 10-ə getməliyik. Sonra ya 2-dən 5-ə qədər gedirik. Və ya 5-dən 10-a, sonra 10-dan 1-ə, sonra da 1-dən 2-yə. hər iki yolun birləşməsinin bütün dövrüdür. Beləliklə, digər səyahət üçün məsafəni əldə etmək üçün məsafəni çıxara bilərik.

Kodu

Avtobus dayanacaqları arasındakı məsafə üçün C ++ kodu Leetcode Həlli

#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

Avtobus dayanacaqları arasındakı məsafə üçün kod kodu Leetcode Solution

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), burada N şəhərlərin sayıdır. Çünki bütün şəhərləri gəzməli olduq. Zamanın mürəkkəbliyi xətti.

Kosmik Mürəkkəblik

O (1), yalnız bir dəyişən istifadə etdiyimiz üçün. Kosmik mürəkkəblik sabitdir.

Şərh yaz

Translate »
1