פתרון ה- Leetcode של עיר היעד


רמת קושי קַל
נשאל לעתים קרובות פייפאל לילל
מחרוזת

הבעיה פתרון ה- 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 ביקש מאיתנו למצוא את היעד. הקלט סיפק לנו כמה כבישים ישירים בין הערים. ניתן כי לעיר יעד אין דרך יוצאת. ניתן לפתור את הבעיה בקלות באמצעות מפת גיבוב. בהאשמפ אנו עוקבים אחר דרכים יוצאות. אנו חוצים את וקטור השבילים ומגדילים את מספר הכבישים היוצאים של הערים. לאחר מכן אנו בודקים אם יש עיר כלשהי בין וקטור השבילים, שאין לה דרך יוצאת. אנו מחזירים את אותה עיר כתשובה.

קוד לפתרון 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

קוד ג'אווה

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, מורכבות הזמן מצטמצמת לליניארית.

מורכבות בחלל

עַל), נדרש מקום לאחסון מספר הכבישים היוצאים בהאשמפ. לפיכך מורכבות החלל היא גם לינארית.