Destination City Leetcode Solution


Кыйынчылык деңгээли жеңил
Көп суралган PayPal Yelp
аркан

Көйгөй Destination City Leetcode Solution бизге шаарлардын ортосундагы айрым мамилелерди камсыз кылат. Киргизүү шаарлардын сызыктар менен бөлүнгөн жуптары катары берилет. Киргизилген ар бир сызык баштапкы чекиттен акыркы чекитке чейинки түз жолду билдирет. Маселеде шаарлардын тегерек каттам түзбөгөндүгү айтылган. Ошондой эле, кире турган шаар бар экени айтылган. Көздөгөн шаар эч кандай чыгуучу жолу жок шаар катары аныкталат. Ошентип, чечимге терең сүңгөөрдөн мурун, бир нече мисалдарды карап көрөлү.

Destination City Leetcode Solution

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

Түшүндүрмө: Демек, эгер биз киришүү менен барсак, Лондондо Нью-Йоркко түз жол бар. Нью-Йорктун Лимага түз жолу бар. Акыр-аягы, Лима Сан-Паулуга түз жол бар. Ошентип, көздөгөн шаар Сан-Паулу болушу керек, анткени анда чыгуучу жолдор жок.

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

Түшүндүрмө: Бизде А дан Zгө чейинки бирден-бир түз жол бар. Ошентип Z биздин бара турган шаарыбыз.

Destination City Leetcode чечими боюнча мамиле

Destination City Leetcode Solution көйгөйү бизден көздөгөн жерди табууну суранды. Кириш бизге шаарлардын арасында түз жолдорду камсыз кылды. Көздөгөн шаарга чыгуучу жол жок деп берилген. Көйгөйүн оңой чечүүгө болот хэшмап. Хэшмапта биз чыгып жаткан жолдорду көзөмөлдөп турабыз. Биз жолдордун векторун кесип өтүп, шаарлардын чыгыш жолдорунун санын көбөйтөбүз. Андан кийин, векторлордун арасында чыгуучу жолу жок шаар бар же жок экендигин текшеребиз. Жооп катары ошол шаарды кайтарып беребиз.

Destination City Leetcode Solution коду

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

Комплекстик анализ

Убакыт татаалдыгы

O (N), Hashmap колдонулгандыктан, убакыттын татаалдыгы сызыктуу болуп калды.

Космостун татаалдыгы

O (N), хэшмаптагы чыккан жолдордун санын сактоо үчүн орун талап кылынат. Ошентип космостогу татаалдык дагы сызыктуу.