題目描述
你正在開發一個公車追蹤網站，使用者可以查詢公車目前在哪一個站，以及「離指定站最近的公車還有幾站」。公車只會沿著站點單向行駛（由左到右），且公車永遠只停在站點上（不會在站與站之間）。
請實作：
class BusTracker {
// stationList 為用 '-' 連接的站點列表
// 例如 "1-2-3-4-5" 對應 1 -> 2 -> 3 -> 4 -> 5
// 公車只會由左往右移動
// busLocations：busId -> stationId
constructor(stationList, busLocations) {}
// 回傳距離 stationId 最近的公車還有幾站
// 若所有公車都在 stationId 左側，回傳 -1
nearestBusToStation(stationId: string): number { return -1; }
// 回傳指定公車目前所在站點
getBusLocation(busId: number): string { return ""; }
}
範例
站點：A-B-C-D-E-F-G-H-I
公車：{1: "B", 2: "E"}
nearestBusToStation("A") -> -1
nearestBusToStation("B") -> 0
nearestBusToStation("C") -> 1
nearestBusToStation("D") -> 2
nearestBusToStation("E") -> 0
nearestBusToStation("F") -> 1
getBusLocation(1) -> "B"
getBusLocation(2) -> "E"
解題思路
- 先把站點轉成陣列，建立
station -> index對映。 - 把每台公車的位置也轉成 index。
- 從右往左掃描，預先算出每個站點「右側最近公車距離」。
- 查詢時即可 O(1) 回傳。
Python 參考實作
class BusTracker:
def __init__(self, station_list: str, bus_locations: dict):
self.stations = station_list.split('-')
self.station_to_idx = {s: i for i, s in enumerate(self.stations)}
self.bus_locations = bus_locations
n = len(self.stations)
self.nearest = [-1] * n
bus_indices = set(self.station_to_idx[s] for s in bus_locations.values() if s in self.station_to_idx)
next_bus = None
for i in range(n - 1, -1, -1):
if i in bus_indices:
next_bus = i
if next_bus is not None:
self.nearest[i] = next_bus - i
def nearestBusToStation(self, station_id: str) -> int:
idx = self.station_to_idx.get(station_id)
if idx is None:
return -1
return self.nearest[idx]
def getBusLocation(self, bus_id: int) -> str:
return self.bus_locations.get(bus_id, "")
複雜度
- 預處理：
O(n + m) - 查詢：
O(1) - 空間：
O(n)
需要面試輔助服務？聯絡 OA VO Service
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。