Самти ҳалли Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад PayPal Yelp
сатр

Мушкилоти Solution Destination City Leetcode моро бо баъзе муносибатҳо байни шаҳрҳо таъмин менамояд. Вуруд ҳамчун ҷуфти шаҳрҳои ҷудошуда дода мешавад. Ҳар як сатр дар вуруд роҳи мустақимро аз нуқтаи оғоз то нуқтаи ниҳоӣ ишора мекунад. Дар масъала оварда шудааст, ки шаҳрҳо роҳи давраро ташкил намекунанд. Инчунин қайд карда мешавад, ки вуруд як шаҳри таъинотӣ дорад. Шаҳри таъинот ҳамчун шаҳре муайян карда мешавад, ки ягон роҳи баромад надорад. Аз ин рӯ, маъмулӣ пеш аз он ки ба ҳалли амиқ биравем, биёед ба якчанд мисол назар кунем.

Самти ҳалли Leetcode

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

Шарҳ: Ҳамин тавр, агар мо аз рӯи даромад гузарем, Лондон роҳи мустақим ба Ню-Йоркро дорад. Ню Йорк роҳи мустақим ба Лима дорад. Дар ниҳоят, Лима роҳи мустақим ба Сан-Пауло дорад. Ҳамин тавр, шаҳри таъинот бояд Сан-Паулу бошад, зеро он роҳҳои содиротӣ надорад.

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

Шарҳ: Мо як роҳи мустақими мустақимро аз A то Z дорем. Ҳамин тавр Z шаҳри таъиноти мост.

Равиш ба ҳалли таъиноти Сити Leetcode

Мушкилоти 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 -ро истифода кардем, мураккабии вақт ба хаттӣ коҳиш ёфтааст.

Мураккабии фазо

О (Н), барои захира кардани шумораи роҳҳои содиротӣ дар hashmap ҷой лозим аст. Ҳамин тариқ, мураккабии фазо низ хаттӣ аст.