راه حل کد Leetcode شهر


سطح دشواری ساده
اغلب در پی پال Yelp
رشته

مشکل Destination City Leetcode Solution برخی از روابط بین شهرها را برای ما فراهم می کند. ورودی به صورت جفت شهرهای جدا شده از خط داده می شود. هر خط در ورودی یک جاده مستقیم را از نقطه شروع تا نقطه انتهایی نشان می دهد. این مسئله نشان می دهد که شهرها یک مسیر دایره ای شکل نمی دهند. همچنین عنوان شده است که ورودی دارای یک شهر مقصد است. شهر مقصد به شهری گفته می شود که فاقد هرگونه جاده خروجی باشد. بنابراین طبق معمول قبل از غوطه ور شدن در محلول ، بیایید نگاهی به چند مثال بیندازیم.

راه حل کد Leetcode شهر

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

توضیح: بنابراین اگر از ورودی استفاده کنیم ، لندن راهی مستقیم به نیویورک دارد. نیویورک راهی مستقیم به لیما دارد. در پایان ، لیما راهی مستقیم به سائوپائولو دارد. بنابراین ، شهر مقصد باید سائوپائولو باشد زیرا هیچ جاده خروجی ندارد.

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

توضیح: ما یک جاده مستقیم داریم که از A به Z شروع می شود. بنابراین Z شهر مقصد ما است.

رویکرد به Destination City Leetcode Solution

مشکل Destination City Leetcode Solution از ما خواست که مقصد را پیدا کنیم. ورودی برخی از جاده های مستقیم را در بین شهرها برای ما فراهم کرده است. با توجه به اینکه یک شهر مقصد جاده خروجی ندارد. با استفاده از a می توان به راحتی مشکل را حل کرد هاشمپ. در hashtap ، جاده های خروجی را پیگیری می کنیم. ما بردار مسیرها را پیمایش می کنیم و تعداد جاده های خروجی شهرها را افزایش می دهیم. سپس پس از آن بررسی می کنیم که آیا در بین بردار مسیرها شهری وجود دارد که فاقد جاده خروجی باشد. ما آن شهر را به عنوان پاسخ برمی گردانیم.

کد برای راه حل کد مقصد شهر

کد 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

تحلیل پیچیدگی

پیچیدگی زمان

بر)، از آنجا که ما از Hashmap استفاده کردیم ، پیچیدگی زمان به خطی کاهش می یابد.

پیچیدگی فضا

بر)، فضا برای ذخیره تعداد جاده های خروجی در hashtap مورد نیاز است. بنابراین پیچیدگی فضا نیز خطی است.