Дестинатион Цити Леетцоде решење


Ниво тешкоће Лако
Често питани у ПаиПал Заштектати
низ

Проблем Дестинатион Цити Леетцоде Солутион пружа нам неке односе између градова. Улаз је дат као пар градова раздвојених линијама. Свака улазна линија означава директан пут од почетне до крајње тачке. У проблему је дато да градови не чине кружну руту. Такође се наводи да улаз има град одредишта. Одредишни град је дефинисан као град који нема излазни пут. Као и обично пре него што заронимо дубоко у решење, погледајмо неколико примера.

Дестинатион Цити Леетцоде решење

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

Објашњење: Ако прођемо поред улаза, Лондон има директан пут до Њујорка. Њујорк има директан пут до Лиме. На крају, Лима има директан пут до Сао Паула. Дакле, град одредишта мора бити Сао Пауло јер нема одлазних путева.

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

Објашњење: Имамо један директан пут који почиње од А до Ж. Дакле, З је наш одредишни град.

Приступ рјешењу града с одредишним градовима

Проблем Дестинатион Цити Леетцоде Солутион затражио је да пронађемо одредиште. Улаз нам је пружио неке директне путеве међу градовима. Даје се да одредишни град нема одлазни пут. Проблем се лако може решити помоћу а хасхмап. У хасхмапу пратимо одлазеће путеве. Прелазимо вектор путања и повећавамо број излазних путева градова. Затим после тога проверавамо има ли града међу векторима стаза који нема излазни пут. Враћамо тај град као одговор.

Шифра за решење града са одредишним градовима

Ц ++ код

#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

Анализа сложености

Сложеност времена

НА), пошто смо користили Хасхмап, временска сложеност је сведена на линеарну.

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

НА), потребан је простор за складиштење броја одлазних путева у хешмапу. Стога је сложеност простора такође линеарна.