資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 程式：查詢到達最終目標所需的最小公交車數量
假設我們有一個 n x 3 矩陣，其中每一行包含三個欄位 [src, dest, id]，這意味著公交車從 src 到 dest 有路線。乘坐新公交車需要花費一個單位的錢，但如果我們留在同一輛公交車上，我們只需要支付一個單位的錢。我們必須找到從位置 0 到終點站（最大位置）乘坐公交車所需的最低成本。如果沒有解決方案，則返回 -1。
因此，如果輸入類似於
| 0 | 1 | 0 |
| 1 | 2 | 0 |
| 2 | 3 | 0 |
| 3 | 5 | 1 |
| 5 | 0 | 2 |
那麼輸出將為 2，因為我們可以在位置 0 乘坐公交車 0 併到達位置 3。然後我們乘坐公交車 1 到達位置 5。
為了解決這個問題，我們將遵循以下步驟：
- start := 0
- target := 給定矩陣的最大位置
- adj := 一個空對映
- 對於 connections 中的每個 src、dest 和 id，執行以下操作：
- 將 (dest, id) 插入 adj[src] 的末尾
- hp := 一個包含專案 (0, start, -1) 的堆
- seen := 一個空對映
- 當 hp 不為空時，執行以下操作：
- (cost, cur_pos, cur_bus) := 堆 hp 的頂部元素，並從 hp 中刪除頂部元素
- 如果 cur_pos 與 target 相同，則
- 返回 cost
- 如果 seen[cur_pos] 中包含 cur_bus，則
- 進入下一次迭代
- 將 cur_bus 插入 seen[cur_pos]
- 對於 adj[cur_pos] 中的每個 (nex_pos, nex_bus)，執行以下操作：
- next_cost := cost
- 如果 nex_bus 與 cur_bus 不相同，則
- next_cost := next_cost + 1
- 將 (next_cost, nex_pos, nex_bus) 插入堆 hp
- 返回 -1
讓我們看看以下實現，以便更好地理解：
示例
from collections import defaultdict from heapq import heapify, heappop, heappush class Solution: def solve(self, connections): start = 0 target = max(max(y, x) for y, x, _ in connections) adj = defaultdict(list) for f, t, id in connections: adj[f].append((t, id)) hp = [(0, start, -1)] seen = defaultdict(set) while hp: cost, cur_pos, cur_bus = heappop(hp) if cur_pos == target: return cost if cur_bus in seen[cur_pos]: continue seen[cur_pos].add(cur_bus) for nex_pos, nex_bus in adj[cur_pos]: next_cost = cost if nex_bus != cur_bus: next_cost += 1 heappush(hp, (next_cost, nex_pos, nex_bus)) return -1 ob = Solution() matrix = [ [0, 1, 0], [1, 2, 0], [2, 3, 0], [3, 5, 1], [5, 0, 2] ] print(ob.solve(matrix))
輸入
matrix = [[0, 1, 0], [1, 2, 0], [2, 3, 0], [3, 5, 1], [5, 0, 2]]
輸出
2
更新於： 2020-12-03
254 次檢視
廣告