डेस्टिनेशन सिटी लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले पोपल केकाटणे
अक्षरमाळा

डेस्टिनेशन सिटी लीटकोड सोल्यूशन आम्हाला शहरे दरम्यान काही संबंध प्रदान करते. इनपुट शहरांच्या जोडी विभक्त जोडी म्हणून दिले जाते. इनपुटमधील प्रत्येक ओळ प्रारंभ बिंदूपासून शेवटच्या बिंदूपर्यंत थेट रस्ता दर्शविते. शहरे परिपत्रक मार्ग तयार करीत नाहीत, ही समस्या आहे. असेही म्हटले आहे की इनपुटला गंतव्य शहर आहे. एक गंतव्य शहर असे शहर म्हणून परिभाषित केले गेले आहे ज्यामध्ये कोणताही बाहेर जाणारा रस्ता नसतो. सोल्यूशनमध्ये खोल जाण्यापूर्वी नेहमीप्रमाणे काही उदाहरणे पाहूया.

डेस्टिनेशन सिटी लीटकोड सोल्यूशन

paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Sao Paulo

स्पष्टीकरणः म्हणून आपण जर इनपुटवर गेलो तर लंडनचा न्यूयॉर्कपर्यंत थेट रस्ता आहे. न्यूयॉर्कमध्ये लिमाचा थेट रस्ता आहे. सरतेशेवटी, लिमाचा साओ पाउलो पर्यंत थेट रस्ता आहे. तर, गंतव्य शहर साओ पाउलो असणे आवश्यक आहे कारण त्याकडे कोणतेही रस्ता नाहीत.

paths = [["A","Z"]]
Z

स्पष्टीकरणः आमच्याकडे ए पासून झेड पर्यंत एकच थेट रस्ता आहे. झेड हे आमचे गंतव्य शहर आहे.

डेस्टिनेशन सिटी लीटकोड सोल्यूशनकडे संपर्क

डेस्टिनेशन सिटी लीटकोड सोल्यूशनने समस्येने आम्हाला गंतव्य शोधण्यास सांगितले. इनपुटने आम्हाला शहरांमध्ये काही थेट रस्ते प्रदान केले आहेत. हे दिले गेले आहे की गंतव्य शहराकडे जाणारा रस्ता नसतो. याचा उपयोग करून समस्या सहज सोडवता येऊ शकते हॅशमॅप. हॅशमॅपमध्ये आम्ही जाणार्‍या रस्त्यांचा मागोवा ठेवतो. आम्ही पथ वेक्टरला मागे टाकतो आणि शहरांमधून जाणार्‍या रस्त्यांची संख्या वाढवतो. त्यानंतर आम्ही हे तपासतो की पथांपैकी काही शहर वेक्टर आहे की नाही, त्यात बाहेर जाणारा रस्ता नाही. आम्ही उत्तर म्हणून ते शहर परत करतो.

डेस्टिनेशन सिटी लीटकोड सोल्यूशनसाठी कोड

सी ++ कोड

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

string destCity(vector<vector<string>>& paths) {
    unordered_map<string, int> outdegree;
    for(auto x: paths){
        outdegree[x[0]]++;
    }
    for(auto x: paths)
        if(outdegree[x[0]] == 0)
            return x[0];
        else if(outdegree[x[1]] == 0)
            return x[1];
    return paths[0][0];
}

int main(){
    vector<vector<string>> paths = {{"London","New York"},{"New York","Lima"},{"Lima","Sao Paulo"}};
    string output = destCity(paths);
    cout<<output;
}
Sao Paulo

जावा कोड

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

class Main
{
  public static String destCity(List<List<String>> paths) {
        HashMap<String, Integer> outdegree = new HashMap<String, Integer>();
        for(List<String> x: paths)
            if(outdegree.containsKey(x.get(0)))
                outdegree.put(x.get(0), outdegree.get(x.get(1))+1);
            else
               outdegree.put(x.get(0), 1);
        
        for(List<String> x: paths)
               if(!outdegree.containsKey(x.get(0)))
                    return x.get(0);
               else if(!outdegree.containsKey(x.get(1)))
                    return x.get(1);
            
        return paths.get(0).get(0);
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    List<List<String>> paths = new ArrayList<List<String>>();
    paths.add(new ArrayList(Arrays.asList("London","New York")));
    paths.add(new ArrayList(Arrays.asList("New York","Lima")));
    paths.add(new ArrayList(Arrays.asList("Lima","Sao Paulo")));
    System.out.print(destCity(paths));
  }
}
Sao Paulo

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), आम्ही हॅशमॅप वापरल्यामुळे, वेळेची जटिलता रेषांपर्यंत कमी होते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), हॅशमॅपमध्ये जाणा roads्या रस्त्यांची संख्या साठवण्यासाठी जागा आवश्यक आहे. अशा प्रकारे अवकाशातील अवघडपणा देखील रेषात्मक आहे.