न्यूनतम समय सबै पोइन्टहरूको लेइटकोड समाधान भ्रमण गर्दै


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन ब्लूमबर्ग फेसबुक Media.net
एरे ज्यामिति

समस्या न्यूनतम समय सबै बिन्दुहरूको भ्रमण लिट्टकोड समाधानले हामीलाई प्रदान गर्दछ array वा निर्देशांक अक्षमा पोइन्टको भेक्टर। हामीलाई इनपुट प्रदान गरे पछि समस्या इनपुटमा दिइएका सबै पोइन्टहरू हेर्न न्यूनतम समय खोज्नको लागि सोध्छ। जब तपाईं या त x या y दिशा को दुबैमा एकाई सार्नुहुन्छ, तपाईं समयको 1 एकाई लिनुहुन्छ। जब तपाईं विकर्ण सार्नुहुन्छ जुन १ युनिट एकै साथ दुबै दिशामा सारिन्छ। तपाईंले १ इकाई समय भेट्नुभयो। अब, सबै दिइएको पोइन्ट भ्रमण गर्न आवश्यक न्यूनतम समय पत्ता लगाउनुहोस्। अर्को शर्त पनि छ। सर्तले भन्छ कि हामीलाई सबै पोइन्टहरू समान क्रममा यात्रा गर्न आवाश्यक हुन्छ। त्यसोभए, सिधा समाधानमा नलिनकन हामी केही उदाहरणहरू हेरौं।

न्यूनतम समय सबै पोइन्टहरूको लेइटकोड समाधान भ्रमण गर्दै

[[1,1],[3,4],[-1,0]]
7

स्पष्टीकरण: छविमा पनि देखाइए अनुसार हामीलाई पहिलो पोइन्टबाट दोस्रोमा जानका लागि unit इकाई समय चाहिन्छ। त्यसपछि unit एकाई समय दोस्रोबाट अन्तिम बिन्दुमा जानका लागि। यस प्रकार, कुल units इकाई समय आवश्यक छ।

सबै पोइन्ट्स लेइटकोड समाधानको न्यूनतम समयको लागि दृष्टिकोण

समस्या न्यूनतम समय सबै विन्दुहरूको भ्रमण लिट्टकोड समाधानले हामीलाई इनपुटमा दिइएका सबै पोइन्टहरू हेर्न न्यूनतम समय भनेको के हो सोधे। समस्याले हामीलाई बिन्दुहरू पनि समान क्रममा यात्रा गर्न बाध्य गर्दछ किनकि ती इनपुटमा प्रदान गरिन्छ। हामीलाई प्रत्येक चालको लागतको बारेमा पनि बताइएको छ। हामी या त दुबै दिशाहरू मध्ये कुनै एकमा १ एकाई सार्न सक्छौं वा हामी दुबै दिशामा सँगै १ एकाई सार्न सक्छौं। यी सबै चालहरूको लागी हामी समयको १ एकाई खर्च गर्छौं। त्यसोभए, सामान्यतया एक x वा y मान अर्को बिन्दुको x वा y मान बराबर नभएसम्म विकर्ण सार्न प्रयास गर्दछ। अब हामी निश्चित छौं कि x वा y मध्ये एक वर्तमान बिन्दुको x वा y बराबर छ। र अब हामी केवल ठाडो वा तेर्सो रूपमा सार्नु पर्छ।

सोच अलि कठिन देखिन्छ तर समस्याको कार्यान्वयन धेरै सरल देखि बाहिर जान्छ। यहाँ प्रक्रियालाई अलग गर्नुको सट्टा जहाँ पहिले हामी विकर्ण र त्यसपछि एकल दिशामा सार्दछौं। हामी केवल हालको र अर्को पोइन्टको x र y मानहरूको अधिकतम भिन्नता फेला पार्दछौं। यसले हामीलाई प्रत्येक चालको लागि सरल सूत्र दिन्छ।

कोड

C ++ कोड न्यूनतम समयको लागि सबै पोइन्टहरूको लेटकोड समाधानको लागि

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

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int ans = 0;
    int n = points.size();
    for(int i=1;i<n;i++){
        vector<int> cur = points[i], prev = points[i-1];
        int curVal = max(abs(cur[0] - prev[0]), abs(cur[1] - prev[1]));
        ans += curVal;
    }
    return ans;
}

int main(){
    vector<vector<int>> points({{1,1},{3,4},{-1,0}});
    cout<<minTimeToVisitAllPoints(points);
}
7

न्यूनतम समयको लागि जाभा कोड सबै पोइन्टहरूको लेटकोड समाधानको लागि

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

class Main
{
  public static int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        int n = points.length;
        for(int i=1;i<n;i++){
            int[] cur = points[i];
            int[] prev = points[i-1];
            int curVal = Math.max(Math.abs(cur[0] - prev[0]), Math.abs(cur[1] - prev[1]));
            ans += curVal;
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] points = {{1,1},{3,4},{-1,0}};
    System.out.println(minTimeToVisitAllPoints(points));
  }
}
7

जटिलता विश्लेषण

समय जटिलता

O (N), किनभने हामीले सम्पूर्ण सूचीलाई पार गर्नुपर्नेछ र यसरी समय जटिलता रैखिक हुन्छ।

ठाउँ जटिलता

O (१), किनभने हामीले उत्तर एकचोटि एकल चरलाई प्रयोग गर्यौं, यसैले अन्तरिक्ष जटिलता स्थिर छ।