ડેસ્ટિનેશન સિટી લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે પેપાલ દરદથી ચીસ પાડવી
શબ્દમાળા

સમસ્યા ડેસ્ટિનેશન સિટી લીટકોડ સોલ્યુશન અમને શહેરો વચ્ચેના કેટલાક સંબંધો પ્રદાન કરે છે. ઇનપુટ શહેરોની લાઇન વિભાજિત જોડ તરીકે આપવામાં આવે છે. ઇનપુટની દરેક લાઇન પ્રારંભિક બિંદુથી અંતિમ બિંદુ સુધીનો સીધો રસ્તો સૂચવે છે. તે સમસ્યામાં આપવામાં આવ્યું છે, કે શહેરો પરિપત્ર માર્ગ બનાવતા નથી. એવું પણ કહેવામાં આવ્યું છે કે ઇનપુટનું ડેસ્ટિનેશન સિટી છે. ગંતવ્ય શહેરને શહેર તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જેમાં કોઈ આઉટગોઇંગ રસ્તો નથી. તેથી ઉકેલમાં dંડે ડાઇવ કરતા પહેલાં હંમેશની જેમ, ચાલો આપણે થોડા ઉદાહરણો જોઈએ.

ડેસ્ટિનેશન સિટી લીટકોડ સોલ્યુશન

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે આપણે હાશ્મpપનો ઉપયોગ કર્યો છે, સમય જટિલતા રેખીય થઈ છે.

અવકાશ જટિલતા

ઓ (એન), હેશમેપમાં બહાર જતા રસ્તાઓની સંખ્યા સ્ટોર કરવા માટે જગ્યા આવશ્યક છે. આમ જગ્યા જટિલતા પણ રેખીય છે.