目的地城市Leetcode解决方案


难度级别 易得奖学金
经常问 贝宝 狗吠声

目标城市Leetcode解决方案问题为我们提供了城市之间的某些关系。 输入以行分隔的城市对形式给出。 输入中的每条线表示从起点到终点的直接道路。 问题是,城市没有形成一条循环路线。 还声明输入具有目的地城市。 目的地城市定义为没有任何输出道路的城市。 因此,像往常一样,在深入研究解决方案之前,让我们看一些示例。

目的地城市Leetcode解决方案

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

说明:因此,如果我们按输入进行分析,则伦敦可以直达纽约。 纽约有直达利马的路。 最终,利马直达圣保罗。 因此,目的地城市必须是圣保罗,因为它没有出路。

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

说明:我们有一条从A到Z的直接道路。因此Z是我们的目的地城市。

目的地城市Leetcode解决方案的方法

问题“目的地城市Leetcode解决方案”要求我们找到目的地。 这些意见为我们提供了一些城市之间的直达道路。 假定目的地城市没有出行道路。 使用以下命令可以轻松解决该问题 哈希图。 在哈希图中,我们跟踪出行道路。 我们遍历路径矢量并增加城市的出行道路数量。 然后,我们检查路径向量中是否有没有出路的城市。 我们返回那个城市作为答案。

目的地城市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

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

复杂度分析

时间复杂度

上),因为我们使用了Hashmap,所以时间复杂度降低为线性。

空间复杂度

上),则需要空间以在哈希图中存储输出道路的数量。 因此,空间复杂度也是线性的。