Решение Leetcode города назначения


Сложный уровень Легко
Часто спрашивают в PayPal Тявкать
строка

Проблема Destination City Leetcode Solution предоставляет нам некоторые отношения между городами. Входные данные представлены в виде пары городов, разделенных строками. Каждая строка во входных данных обозначает прямую дорогу от начальной до конечной точки. В задаче указывается, что города не образуют кругового маршрута. Также указано, что на входе указан город назначения. Город назначения определяется как город, в котором нет исходящей дороги. Итак, как обычно, прежде чем углубляться в решение, давайте рассмотрим несколько примеров.

Решение Leetcode города назначения

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

Пояснение: Итак, если мы пойдем по входу, из Лондона будет прямая дорога в Нью-Йорк. Из Нью-Йорка есть прямая дорога в Лиму. В конце концов, из Лимы есть прямая дорога в Сан-Паулу. Итак, город назначения должен быть Сан-Паулу, потому что у него нет выездных дорог.

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

Пояснение: У нас есть единственная прямая дорога, начинающаяся от A до Z. Таким образом, Z - это наш город назначения.

Подход к решению Leetcode города назначения

Проблема Город назначения Leetcode Solution попросила нас найти пункт назначения. Ввод предоставил нам несколько прямых дорог между городами. При этом в городе назначения нет выездной дороги. Проблему легко решить с помощью хэш-карта. В хэш-карте мы отслеживаем исходящие дороги. Мы проходим вектор путей и увеличиваем количество исходящих дорог городов. Затем проверяем, есть ли среди вектора путей город, не имеющий выездной дороги. Мы возвращаем этот город в качестве ответа.

Код для решения 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, временная сложность снижается до линейной.

Космическая сложность

НА), требуется место для хранения количества исходящих дорог в хэш-карте. Таким образом, сложность пространства также линейна.