Avtobus marşrutları Leetcode həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon google kvadrat Über
Geyim Genişlik İlk Axtarış HashingBaxılıb 42

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Avtobus Marşrutları LeetCode Həll - “Avtobus Marşrutları” sizə harda bir sıra marşrutlar verildiyini bildirir marşrutlar[i] elə bir avtobus marşrutudur ki, avtobus həmişə marşrutu təkrarlayır. Bizə avtobus dayanacağı veriləcək mənbə və biz avtobus dayanacağına çatmaq istəyirik hədəf. Biz yalnız avtobuslardan istifadə edərək dayanacaqlar arasında gedə bilərik.

tapmaq lazımdır ən az avtobus sayı mənbədən hədəfə səyahət etmək üçün lazım olan. Qayıdış -1 bu mümkün deyilsə.

Misal:

Input:  routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2

Explanation:

  • Avtobus7 ilə 1-yə çatanda birinci avtobusdan ikinci avtobusa keçə bilərik, sonra ikinci avtobusdan hədəf = 6-ya keçəcəyik.
  • Beləliklə, cavabımız 2-dir.
Input:  routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

Explanation:

  • Mənbə = 15-dən hədəf = 12-yə qədər hərəkət edə bilən avtobus marşrutları yoxdur, buna görə də -1 qayıdırıq.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Genişlik-İlk Axtarış.
  2. Hər bir marşrutun xəritəsini[i] avtobus nömrəsinə saxlayın və avtobuslar üçün genişlik üzrə birinci axtarışı həyata keçirin.
  3. Mənbə marşrutu mövqeyindən başlayacağıq və bu mənbədən səyahət edə biləcəyimiz bütün istiqamətləndirilənləri növbəyə itələyəcəyik. Bütün bu cür marşrutlar bitişik siyahıların köməyi ilə asanlıqla əldə edilə bilər.
  4. Hər dəfə ön elementi açın queue və bir sıra avtobusların sayı ilə cari vəziyyətdən gedə biləcəyimiz bütün növbəti marşrutları tapmaq üçün bitişik siyahılarda təkrarlayın.
  5. Nəhayət, bununla sona çatacağıq ən az avtobus sayı hədəf marşruta çatmaq üçün tələb olunur.

Kodu

Avtobus Marşrutları Leetcode C++ Həlli:

class Solution {
public:
    const int N = 1e6;
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source==target){
            return 0;
        }
        int n = routes.size();
        vector<int> buses(n),adj[N];
        for(int i=0;i<n;i++){
            for(int j=0;j<routes[i].size();j++){
                adj[routes[i][j]].push_back(i);
            }
        }
        queue<pair<int,int>> q;
        for(auto& bus:adj[source]){
            for(auto& route:routes[bus]){
                q.push({route,1});
            }
            buses[bus] = true;
        }
        while(!q.empty()){
            int route = q.front().first,amount = q.front().second;
            q.pop();   
            if(route==target){
                return amount;
            }
            for(auto& bus:adj[route]){
                if(!buses[bus]){
                    buses[bus] = true;
                    for(auto& x:routes[bus]){
                        q.push({x,amount+1});
                    }
                }
            }
        }
        return -1;
    }
};

Avtobus Marşrutları Leetcode Java Həlli:

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        int n = routes.length;
        HashMap<Integer, HashSet<Integer>> to_routes = new HashMap<>();
        for (int i = 0; i < routes.length; ++i) {
            for (int j : routes[i]) {
                if (!to_routes.containsKey(j))
                    to_routes.put(j, new HashSet<Integer>());
                to_routes.get(j).add(i);
            }
        }
        Queue<int[]> bfs = new ArrayDeque();
        bfs.offer(new int[] {S, 0});
        HashSet<Integer> seen = new HashSet<>();
        seen.add(S);
        boolean[] seen_routes = new boolean[n];
        while (!bfs.isEmpty()) {
            int stop = bfs.peek()[0], bus = bfs.peek()[1];
            bfs.poll();
            if (stop == T) return bus;
            for (int i : to_routes.get(stop)) {
                if (seen_routes[i]) continue;
                for (int j : routes[i]) {
                    if (!seen.contains(j)) {
                        seen.add(j);
                        bfs.offer(new int[] {j, bus + 1});
                    }
                }
                seen_routes[i] = true;
            }
        }
        return -1;
    }
}

Avtobus marşrutları üçün mürəkkəbliyin təhlili Leetcode Solution

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi Genişlik-ilk Axtarış kimi normal qrafikdən.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N), bitişiklik siyahılarını saxlamaq üçün, burada N = görülən maksimum marşrut.

Referans: https://en.wikipedia.org/wiki/Breadth-first_search

Crack Sistemi Dizayn Müsahibələri
Translate »