గమ్యం సిటీ లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది పేపాల్ బాధతో అరుపులు
స్ట్రింగ్

డెస్టినేషన్ సిటీ లీట్‌కోడ్ సొల్యూషన్ సమస్య మాకు నగరాల మధ్య కొన్ని సంబంధాలను అందిస్తుంది. ఇన్పుట్ లైన్ వేరు చేయబడిన నగరాల నగరంగా ఇవ్వబడింది. ఇన్‌పుట్‌లోని ప్రతి పంక్తి ప్రారంభ స్థానం నుండి ఎండ్ పాయింట్ వరకు ప్రత్యక్ష రహదారిని సూచిస్తుంది. ఇది సమస్యలో ఇవ్వబడింది, నగరాలు వృత్తాకార మార్గాన్ని ఏర్పాటు చేయవు. ఇన్పుట్ గమ్యం నగరాన్ని కలిగి ఉందని కూడా పేర్కొనబడింది. గమ్యస్థాన నగరాన్ని అవుట్గోయింగ్ రహదారి లేని నగరంగా నిర్వచించారు. కాబట్టి ద్రావణంలో లోతుగా డైవింగ్ చేయడానికి ముందు ఎప్పటిలాగే, కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

గమ్యం సిటీ లీట్‌కోడ్ పరిష్కారం

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

వివరణ: కాబట్టి మేము ఇన్పుట్ ద్వారా వెళితే, లండన్ న్యూయార్క్ కు ప్రత్యక్ష రహదారిని కలిగి ఉంది. న్యూయార్క్‌లో లిమాకు ప్రత్యక్ష రహదారి ఉంది. చివరికి, లిమాకు సావో పాలోకు ప్రత్యక్ష రహదారి ఉంది. కాబట్టి, గమ్యం నగరం సావో పాలో అయి ఉండాలి ఎందుకంటే దీనికి అవుట్గోయింగ్ రోడ్లు లేవు.

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

వివరణ: మాకు A నుండి Z వరకు ఒకే ప్రత్యక్ష రహదారి ఉంది. ఈ విధంగా Z మా గమ్యం నగరం.

గమ్యం సిటీ లీట్‌కోడ్ పరిష్కారానికి చేరుకోండి

డెస్టినేషన్ సిటీ లీట్‌కోడ్ సొల్యూషన్ సమస్య గమ్యాన్ని కనుగొనమని కోరింది. ఇన్పుట్ మాకు నగరాల మధ్య కొన్ని ప్రత్యక్ష రహదారులను అందించింది. గమ్యస్థాన నగరానికి అవుట్గోయింగ్ రహదారి లేదని ఇది ఇవ్వబడింది. A ను ఉపయోగించి సమస్యను సులభంగా పరిష్కరించవచ్చు హాష్ మ్యాప్. హ్యాష్‌మ్యాప్‌లో, మేము అవుట్గోయింగ్ రోడ్లను ట్రాక్ చేస్తాము. మేము పాత్స్ వెక్టర్లో ప్రయాణించి, నగరాల అవుట్గోయింగ్ రోడ్ల సంఖ్యను పెంచుతాము. మార్గాల వెక్టర్‌లో ఏదైనా నగరం ఉందా, అవుట్‌గోయింగ్ రహదారి లేదని మేము తనిఖీ చేస్తాము. మేము ఆ నగరాన్ని సమాధానంగా తిరిగి ఇస్తాము.

డెస్టినేషన్ సిటీ లీట్‌కోడ్ సొల్యూషన్ కోసం కోడ్

సి ++ కోడ్

#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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), మేము హాష్‌మ్యాప్‌ను ఉపయోగించినందున, సమయ సంక్లిష్టత సరళంగా తగ్గించబడుతుంది.

అంతరిక్ష సంక్లిష్టత

పై), అవుట్గోయింగ్ రోడ్ల సంఖ్యను హాష్ మ్యాప్ లో నిల్వ చేయడానికి స్థలం అవసరం. అందువలన స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.