[LeetCode] 815. Bus Routes

cyixlq 發(fā)布于2019-08-16 13:54 / 1582人閱讀

Problem

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:

Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

Solution

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S == T) return 0;
        
        //pre-processing: save > for BFS
        Map> map = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop: routes[i]) {
                if (!map.containsKey(stop)) map.put(stop, new ArrayList<>());
                map.get(stop).add(i);
            }
        }
        
        if (!map.containsKey(S) || !map.containsKey(T)) return -1;
        
        Set visited = new HashSet<>(); //to store visited routes
        Deque queue = new ArrayDeque<>();
        queue.offer(S);
        
        int transitions = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            transitions++;
            for (int i = 0; i < size; i++) {
                int curStop = queue.poll();
                List buses = map.get(curStop);
                for (int bus: buses) {
                    if (visited.contains(bus)) continue;
                    visited.add(bus);
                    for (int stop: routes[bus]) {
                        if (stop == T) return transitions;
                        else queue.offer(stop);
                    }
                }
            }
        }
        
        return -1;
    }
}

GPU云服務(wù)器云服務(wù)器 Routes LeetCode Bus d bus

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/72547.html

相關(guān)文章

SpringCloud微服務(wù)實(shí)戰(zhàn)筆記

摘要：服務(wù)提供者的運(yùn)行機(jī)制用了雙層結(jié)構(gòu)來維護(hù)注冊的服務(wù)信息，第一層為服務(wù)的名稱，第二層為服務(wù)的實(shí)例名稱。服務(wù)注冊中心的運(yùn)行機(jī)制為了防止服務(wù)的異常下線，會周期性的清理列表中未續(xù)約的服務(wù)。負(fù)載均衡器的基本功能維護(hù)該服務(wù)下的所有節(jié)點(diǎn)列表。 Spring Boot Spring Boot有什么作用 Spring Boot通過自動化的配置簡化Spring原有的樣板化的配置。 Spring Boo...

chunquedong 2019-08-16 10:55 評論0 收藏0
Vue組件——子組件向父組件傳遞數(shù)據(jù)以及路由

摘要：自定義事件我們知道，父組件使用傳遞數(shù)據(jù)給子組件。另外，父組件可以在使用子組件的地方直接用來監(jiān)聽子組件觸發(fā)的事件。為了讓組件可以組合，我們需要一種方式來混合父組件的內(nèi)容與子組件自己的模板。自定義事件我們知道，父組件使用 prop 傳遞數(shù)據(jù)給子組件。但子組件怎么跟父組件通信呢？這個時候 Vue 的自定義事件系統(tǒng)就派得上用場了。使用綁定自定義事件v-on 每個 Vue 實(shí)例都實(shí)現(xiàn)了事...

CoorChice 2019-08-01 17:58 評論0 收藏0
Vue 后臺模板 [Vue admin] SanJi Boot Admin Iview

摘要：導(dǎo)讀很久沒有寫文章了最近一直在忙之前一直想著可以把項(xiàng)目中的頁面使用進(jìn)行重寫前幾天算是階段性的完成了這個計(jì)劃后期會隨著的模塊不斷增多對其進(jìn)行對應(yīng)的升級與擴(kuò)展簡介項(xiàng)目源碼已托管到碼云上使用技術(shù)實(shí)現(xiàn)了什么功能基于進(jìn)行登陸時的認(rèn)證支持跨域需要后臺配導(dǎo)讀：很久沒有寫文章了,最近一直在忙,之前一直想著可以把SanJi Boot Security項(xiàng)目中的頁面使用 Vue+webpack 進(jìn)行重寫...

546669204 2019-08-22 13:45 評論0 收藏0
Vue2.0 學(xué)習(xí)筆記

摘要：父子組件通信父組件通過向下傳遞數(shù)據(jù)給子組件，子組件通過給父組件發(fā)送消息。是一個對象而不是字符串?dāng)?shù)組時，它包含驗(yàn)證要求。狀態(tài)管理由于多個狀態(tài)分散的跨越在許多組件和交互間，大型應(yīng)用的復(fù)雜度也隨之增長。提供了，可以通過文檔學(xué)習(xí)。什么是vue vue是一個前端框架，主要兩個特點(diǎn)：數(shù)據(jù)綁定、組件化。安裝環(huán)境根據(jù)教程安裝環(huán)境：node.js、npm、webpack、vue-cli主要的命...

cgh1999520 2019-08-21 11:25 評論0 收藏0
前端知識點(diǎn)總結(jié)——VUE（持續(xù)更新中）

摘要：前端知識點(diǎn)總結(jié)持續(xù)更新中框架和庫的區(qū)別框架有著自己的語法特點(diǎn)都有對應(yīng)的各個模塊庫專注于一點(diǎn)框架的好處提到代碼的質(zhì)量，開發(fā)速度提高代碼的復(fù)用率降低模塊之間的耦合度高內(nèi)聚低耦合思維模式的轉(zhuǎn)換從操作的思維模式切換到以數(shù)據(jù)為主概述是一個漸進(jìn)式的構(gòu)建前端知識點(diǎn)總結(jié)——VUE（持續(xù)更新中） 1.框架和庫的區(qū)別：框架：framework 有著自己的語法特點(diǎn)、都有對應(yīng)的各個模塊庫 library ...

big_cat 2019-08-22 14:50 評論0 收藏0