Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

815. Bus Routes

給你一個路線陣列

裡面有許多路線

每條路線都是一個停靠站陣列

公車會照著路線不斷從頭跑到尾

你從起點站開始等公車

在只能搭公車換站的情況下到終點站

請你回全起點站搭到終點站需要經過的路線數量

如果無法到達則返回-1


Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
從1站搭0號路線到7站，然後再從7號站搭1號路線到6站

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]],
source = 15, target = 12
Output: -1


Intuition:
尋找起點站能到的所有站點

然後再不斷尋找下去

直到找到終點站

或是沒有辦法再到達任何新的站點

Approach:
我們用一個Map stop去紀錄已經經過的站點

(用Set應該也可以)

然後另一個Set connectedRoutes去紀錄已經走過的路線

這樣就可以避免重複計算已經計算過的路線

然後用一個陣列newConnect去紀錄要新增的路線

我們會先把當前站點能經過的所有路線記錄起來

最後再一次新增到站點裡面


第一次做的時候我沒用newConnect所以一直超時

重寫一遍之後終於能過了。


然後這一題我對時間複雜度沒什麼把握

別人的解答也都講的不太一樣

之後應該會再研究一次這一題

TS Code:

function numBusesToDestination (routes: number[][], source: number, target:
number): number {
  const stop = new Map<number, number>([[source, 0]])
  const connectedRoutes = new Set<number>()
  let routeCount = 0
  let newConnect: number[] = [-1]
  while (newConnect.length > 0 && !stop.has(target)) {
    newConnect = []
    routeCount++
    for (let i = 0; i < routes.length; i++) {
      if (connectedRoutes.has(i)) continue
      for (const item of routes[i]) {
        if (stop.has(item)) {
          newConnect.push(i)
          break
        }
      }
    }
    for (let i = 0; i < newConnect.length; i++) {
      connectedRoutes.add(newConnect[i])
      for (const item of routes[newConnect[i]]) {
        if (stop.has(item)) continue
        stop.set(item, routeCount)
      }
    }
    // console.log(stop)
  }
  return stop.get(target) ?? -1
}

圖的問題都好難

我對圖的演算法都超不熟的

這一題應該是BFS吧(?)

--
                                                                    Zoosewu
                              Yoututbe顯示PTT推文
                       可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699783177.A.F26.html
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/12/2023 17:59:50
推 y3226999: 大師==