ಗಮ್ಯಸ್ಥಾನ ನಗರ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಪೇಪಾಲ್ ಕೂಗು
ಸ್ಟ್ರಿಂಗ್

ಡೆಸ್ಟಿನೇಶನ್ ಸಿಟಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಗರಗಳ ನಡುವಿನ ಕೆಲವು ಸಂಬಂಧಗಳನ್ನು ನಮಗೆ ಒದಗಿಸುತ್ತದೆ. ಇನ್ಪುಟ್ ಅನ್ನು ಲೈನ್ ಬೇರ್ಪಡಿಸಿದ ಜೋಡಿ ನಗರಗಳಾಗಿ ನೀಡಲಾಗಿದೆ. ಇನ್ಪುಟ್ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಾಲು ಪ್ರಾರಂಭದ ಸ್ಥಳದಿಂದ ಅಂತಿಮ ಬಿಂದುವಿಗೆ ನೇರ ರಸ್ತೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ನಗರಗಳು ವೃತ್ತಾಕಾರದ ಮಾರ್ಗವನ್ನು ರೂಪಿಸುವುದಿಲ್ಲ ಎಂದು ಸಮಸ್ಯೆಯಲ್ಲಿ ನೀಡಲಾಗಿದೆ. ಇನ್ಪುಟ್ ಗಮ್ಯಸ್ಥಾನ ನಗರವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಸಹ ಹೇಳಲಾಗಿದೆ. ಗಮ್ಯಸ್ಥಾನ ನಗರವನ್ನು ಯಾವುದೇ ಹೊರಹೋಗುವ ರಸ್ತೆಯನ್ನು ಹೊಂದಿರದ ನಗರ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಆದ್ದರಿಂದ ದ್ರಾವಣದಲ್ಲಿ ಆಳವಾಗಿ ಧುಮುಕುವ ಮೊದಲು ಎಂದಿನಂತೆ, ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

ಗಮ್ಯಸ್ಥಾನ ನಗರ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

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

ವಿವರಣೆ: ಆದ್ದರಿಂದ ನಾವು ಇನ್ಪುಟ್ ಮೂಲಕ ಹೋದರೆ, ಲಂಡನ್ ನ್ಯೂಯಾರ್ಕ್ಗೆ ನೇರ ರಸ್ತೆಯನ್ನು ಹೊಂದಿದೆ. ನ್ಯೂಯಾರ್ಕ್ ಲಿಮಾಕ್ಕೆ ನೇರ ರಸ್ತೆಯನ್ನು ಹೊಂದಿದೆ. ಕೊನೆಯಲ್ಲಿ, ಲಿಮಾ ಸಾವೊ ಪಾಲೊಗೆ ನೇರ ರಸ್ತೆಯನ್ನು ಹೊಂದಿದೆ. ಆದ್ದರಿಂದ, ಗಮ್ಯಸ್ಥಾನ ನಗರವು ಸಾವೊ ಪಾಲೊ ಆಗಿರಬೇಕು ಏಕೆಂದರೆ ಅದು ಹೊರಹೋಗುವ ರಸ್ತೆಗಳಿಲ್ಲ.

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

ವಿವರಣೆ: ನಮ್ಮಲ್ಲಿ 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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ನಾವು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಅನ್ನು ಬಳಸಿದ್ದರಿಂದ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ರೇಖೀಯಕ್ಕೆ ಇಳಿಸಲಾಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಹೊರಹೋಗುವ ರಸ್ತೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಲು ಸ್ಥಳಾವಕಾಶದ ಅಗತ್ಯವಿದೆ. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆಯೂ ರೇಖೀಯವಾಗಿರುತ್ತದೆ.