Дестинация City Leetcode Решение


Ниво на трудност Лесно
Често задавани в PayPal Лая
Низ

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

Дестинация City Leetcode Решение

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

Обяснение: Така че, ако минем по входа, Лондон има директен път към Ню Йорк. Ню Йорк има директен път към Лима. В крайна сметка Лима има директен път към Сао Пауло. И така, градът на местоназначение трябва да е Сао Пауло, защото няма изходящи пътища.

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

Обяснение: Имаме един директен път, започващ от А до Я. По този начин Z е нашият дестинационен град.

Подход към решението на Leetcode City Destination

Проблемът Destination City Leetcode Solution ни помоли да намерим дестинацията. Входът ни предостави някои преки пътища между градовете. Дадено е, че градът на местоназначение няма изходящ път. Проблемът може лесно да бъде решен с помощта на hashmap. В хеш-картата ние следим изходящите пътища. Прекосяваме вектора на пътеките и увеличаваме броя на изходящите пътища на градовете. След това проверяваме дали сред векторите на пътеки има град, който няма изходящ път. Връщаме този град като отговор.

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

Сложност на пространството

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