বাস স্টপস লেটকোড সমাধানের মধ্যে দূরত্ব


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় গুগল
বিন্যাস

বাস স্টপস লেটকোড সমাধানের মধ্যে সমস্যা আমাদের একটি সরবরাহ করে us বিন্যাস সংলগ্ন শহরগুলির মধ্যে দূরত্ব বর্ণনা করে পূর্ণসংখ্যার শহরগুলিকে একটি বিজ্ঞপ্তি অর্ডার দেওয়া হয়। সুতরাং, সর্বশেষ শহরটি অনুসরণ করে প্রথম শহর। এখন, দুটি প্রদত্ত শহরের মধ্যে ন্যূনতম দূরত্ব আমাদের খুঁজে বের করতে হবে। সুতরাং, সমাধান দিকে সরানোর আগে। আসুন কয়েকটি উদাহরণ দেখুন।

বাস স্টপস লেটকোড সমাধানের মধ্যে দূরত্ব

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

ব্যাখ্যা: সার্কুলার ক্রমে সাজানো শহরগুলি উপরের চিত্রটিতে দেখানো হয়েছে। এখানে, উদাহরণস্বরূপ, আমরা শহরটিকে শুরুর শহর হিসাবে এবং শহর 0 টি গন্তব্য হিসাবে সরবরাহ করি। সুতরাং, 1 টি শহর থেকে শুরু করে সিটি 0 এ পৌঁছানোর দুটি উপায় রয়েছে। হয় আমরা শহর থেকে সহজভাবে 1 থেকে 0 যেতে পারি অথবা আমরা 1 থেকে 0, 3 থেকে 3, 2 থেকে 2 পর্যন্ত পথ অনুসরণ করতে পারি Now এখন, আমরা উভয় উপায়ে ভ্রমণ করার দূরত্ব গণনা করব এবং সর্বনিম্ন দূরত্ব ফিরিয়ে দেব। প্রথম পাথ 1 থেকে 0 এর জন্য আমাদের দূরত্ব = 1 যাত্রা করতে হবে, অন্য পথের জন্য আমাদের দূরত্ব = 1 9. ভ্রমণ করতে হবে। সুতরাং সর্বনিম্ন দূরত্বটি 1 ইউনিট।

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

ব্যাখ্যা: আমরা উপরের উদাহরণে যেমন করেছি, আমরা উভয় দিকের দূরত্ব গণনা করি এবং সর্বনিম্ন ফিরিয়ে দিই। যেহেতু দুটি পাথ 3 এবং 7 দৈর্ঘ্যের We আমরা দুটি নূন্যতমটি 3 বাছাই করি।

বাস স্টপস লেটকোড সমাধানের মধ্যে দূরত্বের জন্য দৃষ্টিভঙ্গি

বাস স্টপস লেটকোড সলিউশন এর মধ্যকার সমস্যাটি যদি শহর এবং গন্তব্য শহর আমাদের দেওয়া হয় তবে ভ্রমণের জন্য প্রয়োজনীয় ন্যূনতম দূরত্বটি জানতে চেয়েছিলেন। সমস্যাটি সহজ কারণ গন্তব্যে পৌঁছানোর কেবল দুটি উপায় থাকতে পারে। একটি হ'ল আমরা যদি এগিয়ে চলার দিকে শুরু করি এবং অন্যটি পিছনে সরে যেতে এবং গন্তব্যে পৌঁছতে। আমরা যাতায়াতের একটির জন্য দূরত্বটি খুঁজে পেতে পারি এবং অন্যটি মোট থেকে এই দূরত্বকে বিয়োগ করে সহজেই গণনা করা যায়।

বিবেচনা করুন, আমাদের শহর থেকে ২ থেকে ৫ পর্যন্ত যেতে হবে, যেখানে মোট নগর ১০ টি। তারপরে আমরা হয় 2 থেকে 5 বা 10 থেকে 2, তারপর 5 থেকে 5 এবং তারপরে 10 থেকে 10 পর্যন্ত যেতে পারি The উভয় পথের মিলনের পুরো সার্কিট। সুতরাং, আমরা অন্য যাত্রার দূরত্ব পেতে দূরত্বকে বিয়োগ করতে পারি।

কোড

বাস স্টপস লেটকোড সমাধানের মধ্যে দূরত্বের জন্য সি ++ কোড

#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

বাস স্টপস লেটকোড সমাধানের মধ্যে দূরত্বের জন্য জাভা কোড

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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), যেখানে এন শহরগুলির সংখ্যা। যেহেতু আমাদের সমস্ত শহর ঘুরে বেড়াতে হয়েছিল। সময় জটিলতা রৈখিক।

স্পেস জটিলতা ity

ও (1), যেহেতু আমরা কেবল একটি একক ভেরিয়েবল ব্যবহার করেছি। স্থান জটিলতা ধ্রুবক।