இலக்கு நகர லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது பேபால் நாயின் குரைப்பு
சரம்

இலக்கு சிட்டி லீட்கோட் தீர்வு நகரங்களுக்கு இடையிலான சில உறவுகளை எங்களுக்கு வழங்குகிறது. உள்ளீடு வரி பிரிக்கப்பட்ட ஜோடி நகரங்களாக வழங்கப்படுகிறது. உள்ளீட்டில் உள்ள ஒவ்வொரு வரியும் தொடக்க புள்ளியிலிருந்து இறுதிப் புள்ளி வரை ஒரு நேரடி சாலையைக் குறிக்கிறது. நகரங்கள் வட்டவடிவத்தை உருவாக்குவதில்லை என்பது பிரச்சினையில் கொடுக்கப்பட்டுள்ளது. உள்ளீட்டில் ஒரு இலக்கு நகரம் இருப்பதாகவும் கூறப்பட்டுள்ளது. ஒரு இலக்கு நகரம் எந்த வெளிச்செல்லும் சாலையும் இல்லாத நகரமாக வரையறுக்கப்படுகிறது. எனவே தீர்வில் ஆழமாக டைவ் செய்வதற்கு முன்பு வழக்கம் போல், சில எடுத்துக்காட்டுகளைப் பார்ப்போம்.

இலக்கு நகர லீட்கோட் தீர்வு

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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), நாங்கள் ஹாஷ்மாப்பைப் பயன்படுத்தியதால், நேர சிக்கலானது நேரியல் ஆக குறைக்கப்படுகிறது.

விண்வெளி சிக்கலானது

ஓ (என்), வெளிச்செல்லும் சாலைகளின் எண்ணிக்கையை ஹாஷ்மாப்பில் சேமிக்க இடம் தேவை. இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.