Destination City Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် PayPal က Yelp
ကြိုး

ပြestနာ Destination City Leetcode Solution သည်မြို့များအကြားဆက်ဆံရေးအချို့ကိုကျွန်ုပ်တို့အားထောက်ပံ့ပေးသည်။ အဆိုပါ input ကိုလိုင်းခွဲထားမြို့ကြီးများ၏ pair တစုံအဖြစ်ပေးထားသည်။ ထည့်သွင်းမှုရှိလိုင်းတစ်ခုစီသည်စမှတ်မှအဆုံးမှတ်သို့တိုက်ရိုက်လမ်းကိုညွှန်ပြသည်။ ပြtheနာတွင်မြို့များသည်မြို့ပတ်ရထားလမ်းကြောင်းမဖွဲ့စည်းကြောင်းဖော်ပြထားသည်။ ဒါဟာ input ကိုတစ် ဦး ဦး တည်ရာမြို့ရှိကြောင်းဖော်ပြထားသည်။ သွားလိုသည့်မြို့ကိုအထွက်လမ်းမရှိသောမြို့အဖြစ်သတ်မှတ်သည်။ ဒီတော့ဖြေရှင်းချက်ထဲကိုနက်နက်ရှိုင်းရှိုင်းမဝင်ခင်ခါတိုင်းလိုနည်းနည်းလောက်ကြည့်ကြရအောင်။

Destination City Leetcode ဖြေရှင်းချက်

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

ရှင်းလင်းချက် - အကယ်လို့ input ကိုသွားမယ်ဆိုရင်လန်ဒန်မှာနယူးယောက်ကိုသွားမယ်။ နယူးယောက်တွင်လီမာသို့တိုက်ရိုက်လမ်းရှိသည်။ နောက်ဆုံးတွင် Lima သည် Sao Paulo သို့တိုက်ရိုက်လမ်းပေါ်တွင်ရှိသည်။ ဒါကြောင့်လမ်းပန်းဆက်သွယ်ရေးအဆင်မပြေသောကြောင့်ဆလိုပိုလိုမြို့သည်မြို့တော်ဖြစ်သင့်သည်။

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

ရှင်းလင်းချက်။ ။ A မှ Z သို့တိုက်ရိုက်လမ်းကြောင်းတစ်ခုရှိသည်။ ထို့ကြောင့် Z သည်ကျွန်ုပ်တို့၏ ဦး တည်ရာမြို့ဖြစ်သည်။

Destination City Leetcode ဖြေရှင်းနည်းကိုချဉ်းကပ်ပါ

ပြproblemနာ Destination City Leetcode Solution သည် ဦး တည်ရာကိုရှာရန်ကျွန်ုပ်တို့အားတောင်းဆိုခဲ့သည်။ မြို့တော်အကြားတိုက်ရိုက်လမ်းများဖြင့်ဤထည့် ၀ င်မှုကကျွန်ုပ်တို့အားကူညီပေးသည်။ သတ်မှတ်ထားသောမြို့တွင်အထွက်လမ်းမရှိသောကြောင့်ဖြစ်သည်။ ပြနာကိုအလွယ်တကူဖြေရှင်းနိုင်သည် hashmap။ hashmap တွင်ကျွန်ုပ်တို့သည်ထွက်ပေါက်လမ်းများကိုခြေရာခံသည်။ ကျနော်တို့လမ်းကြောင်းအားနည်းချက်ကိုဖြတ်သန်းနှင့်မြို့များ၏အထွက်လမ်းများ၏အရေအတွက်ကိုတိုး။ ပြီးတဲ့နောက်လမ်းကနေထွက်မယ့်လမ်းမရှိတဲ့လမ်းကြောင်းတွေထဲမှာမြို့တစ်မြို့ရှိလားဆိုတာစစ်ဆေးကြည့်ရအောင်။ အဖြေအဖြစ်ထိုမြို့ကိုကျွန်ုပ်တို့ပြန်လာကြသည်။

Destination City Leetcode ဖြေရှင်းချက်အတွက်ကုဒ်

C ++ ကုဒ်

#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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)ကျနော်တို့ Hashmap ကိုသုံးပြီးကတည်းကအချိန်ရှုပ်ထွေးမှုကို linear အဖြစ်လျှော့ချသည်။

အာကာသရှုပ်ထွေးမှု

အို (N), hashmap အတွက်ထွက်ပေါက်လမ်းများ၏နံပါတ်သိုလှောင်ရန်နေရာလိုအပ်ပါသည်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးမှုသည်လည်း linear ဖြစ်သည်။