Destination CityLeetcodeソリューション


難易度 簡単に
よく聞かれる PayPal 悲鳴
文字列

問題のDestinationCity Leetcode Solutionは、都市間のいくつかの関係を提供します。 入力は、行で区切られた都市のペアとして提供されます。 入力の各線は、始点から終点までの直接の道路を示します。 問題には、都市が循環ルートを形成していないことが示されています。 また、入力には宛先都市があるとも記載されています。 目的地の都市は、出て行く道路がない都市として定義されます。 したがって、いつものように、ソリューションを深く掘り下げる前に、いくつかの例を見てみましょう。

Destination CityLeetcodeソリューション

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

説明:つまり、入力を見ると、ロンドンにはニューヨークへの直接の道があります。 ニューヨークにはリマへの直接の道があります。 結局、リマはサンパウロへの直接の道を持っています。 したがって、目的地の都市は、出て行く道路がないため、サンパウロでなければなりません。

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

説明:AからZまでの直通道路がXNUMX本あります。したがって、Zが目的地の都市です。

目的地の都市リートコードソリューションへのアプローチ

問題のあるDestinationCity Leetcode Solutionから、目的地を見つけるように求められました。 入力により、都市間のいくつかの直接道路が提供されました。 目的地の都市には出て行く道路がないことが与えられています。 問題は、を使用して簡単に解決できます ハッシュマップ。 ハッシュマップでは、出て行く道路を追跡します。 パスベクトルをトラバースし、都市の出て行く道路の数を増やします。 次に、パスベクトルの中に、出て行く道路がない都市があるかどうかを確認します。 その都市を答えとして返します。

Destination CityLeetcodeソリューションのコード

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

Javaコード

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

複雑さの分析

時間の複雑さ

オン)、ハッシュマップを使用したため、時間計算量は線形に減少します。

スペースの複雑さ

オン)、ハッシュマップに出て行く道路の数を格納するためのスペースが必要です。 したがって、スペースの複雑さも線形です。