ഉദ്ദിഷ്ടസ്ഥാന സിറ്റി ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു പേപാൽ Yelp
സ്ട്രിംഗ്

ഡെസ്റ്റിനേഷൻ സിറ്റി ലീറ്റ്കോഡ് പരിഹാരം ഞങ്ങൾക്ക് നഗരങ്ങൾ തമ്മിലുള്ള ചില ബന്ധങ്ങൾ നൽകുന്നു. ഇൻപുട്ട് ലൈൻ വേർതിരിച്ച ജോഡി നഗരങ്ങളായി നൽകിയിരിക്കുന്നു. ഇൻ‌പുട്ടിലെ ഓരോ വരിയും ആരംഭ പോയിന്റിൽ‌ നിന്നും എൻ‌ഡ്‌പോയിന്റിലേക്കുള്ള നേരിട്ടുള്ള റോഡിനെ സൂചിപ്പിക്കുന്നു. നഗരങ്ങൾ വൃത്താകൃതിയിലുള്ള ഒരു റൂട്ട് ഉണ്ടാക്കുന്നില്ലെന്നതാണ് പ്രശ്‌നത്തിൽ നൽകിയിരിക്കുന്നത്. ഇൻപുട്ടിന് ഒരു ലക്ഷ്യസ്ഥാന നഗരമുണ്ടെന്നും പ്രസ്താവിക്കുന്നു. Going ട്ട്‌ഗോയിംഗ് റോഡില്ലാത്ത നഗരമാണ് ലക്ഷ്യസ്ഥാന നഗരത്തെ നിർവചിച്ചിരിക്കുന്നത്. അതിനാൽ പരിഹാരത്തിലേക്ക് ആഴത്തിൽ പ്രവേശിക്കുന്നതിനുമുമ്പ് പതിവുപോലെ, നമുക്ക് കുറച്ച് ഉദാഹരണങ്ങൾ നോക്കാം.

ഉദ്ദിഷ്ടസ്ഥാന സിറ്റി ലീറ്റ്കോഡ് പരിഹാരം

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

വിശദീകരണം: അതിനാൽ ഞങ്ങൾ ഇൻപുട്ടിലൂടെ പോയാൽ ലണ്ടനിലേക്ക് ന്യൂയോർക്കിലേക്ക് നേരിട്ട് ഒരു റോഡുണ്ട്. ന്യൂയോർക്കിൽ ലിമയിലേക്ക് നേരിട്ട് റോഡ് ഉണ്ട്. അവസാനം, ലിമയ്ക്ക് സാവോ പോളോയിലേക്ക് നേരിട്ട് ഒരു റോഡ് ഉണ്ട്. അതിനാൽ, ലക്ഷ്യസ്ഥാന നഗരം സാവോ പോളോ ആയിരിക്കണം, കാരണം അതിന് going ട്ട്‌ഗോയിംഗ് റോഡുകളില്ല.

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

വിശദീകരണം: എ മുതൽ ഇസെഡ് വരെ ആരംഭിക്കുന്ന ഒരു നേരിട്ടുള്ള റോഡ് ഞങ്ങൾക്ക് ഉണ്ട്. അങ്ങനെ ഇസഡ് ഞങ്ങളുടെ ലക്ഷ്യസ്ഥാന നഗരമാണ്.

ഡെസ്റ്റിനേഷൻ സിറ്റി ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്കുള്ള സമീപനം

ലക്ഷ്യസ്ഥാനം കണ്ടെത്താൻ ഡെസ്റ്റിനേഷൻ സിറ്റി ലീറ്റ്കോഡ് പരിഹാരം ഞങ്ങളോട് ആവശ്യപ്പെട്ടു. ഇൻപുട്ട് ഞങ്ങൾക്ക് നഗരങ്ങൾക്കിടയിൽ ചില നേരിട്ടുള്ള റോഡുകൾ നൽകി. ഒരു ലക്ഷ്യസ്ഥാന നഗരത്തിന് going ട്ട്‌ഗോയിംഗ് റോഡ് ഇല്ലെന്നാണ് നൽകിയിരിക്കുന്നത്. A ഉപയോഗിച്ച് പ്രശ്നം എളുപ്പത്തിൽ പരിഹരിക്കാൻ കഴിയും ഹാഷ്‌മാപ്പ്. ഹാഷ്‌മാപ്പിൽ, going ട്ട്‌ഗോയിംഗ് റോഡുകളുടെ ട്രാക്ക് ഞങ്ങൾ സൂക്ഷിക്കുന്നു. ഞങ്ങൾ പാത്ത് വെക്റ്റർ സഞ്ചരിച്ച് നഗരങ്ങളുടെ going ട്ട്‌ഗോയിംഗ് റോഡുകളുടെ എണ്ണം വർദ്ധിപ്പിക്കുന്നു. അതിനുശേഷം, പാത്ത് വെക്റ്ററുകളിൽ ഏതെങ്കിലും നഗരമുണ്ടോയെന്ന് പരിശോധിക്കുന്നു, അതിന് going ട്ട്‌ഗോയിംഗ് റോഡ് ഇല്ല. അതിനുള്ള ഉത്തരമായി ഞങ്ങൾ ആ നഗരം തിരികെ നൽകുന്നു.

ലക്ഷ്യസ്ഥാന സിറ്റി ലീട്ട്‌കോഡ് പരിഹാരത്തിനുള്ള കോഡ്

സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), ഞങ്ങൾ ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ചതിനാൽ, സമയ സങ്കീർണ്ണത രേഖീയമായി ചുരുക്കി.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), out ട്ട്‌ഗോയിംഗ് റോഡുകളുടെ എണ്ണം ഹാഷ്‌മാപ്പിൽ സംഭരിക്കാൻ സ്ഥലം ആവശ്യമാണ്. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.