網路延遲時間
「網路延遲時間」問題的詳細指南和 Python 實作。
1. 學習
「網路延遲時間」問題是進階圖形部分的關鍵挑戰。
此實作著重於 Python 中的簡單層級邏輯。
在我們提供的解決方案中，我們優先考慮技術準確性和程式碼可讀性。
2. Real-World Applications
3. Visual Intuition
可視化網路延遲時間的邏輯流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔細閱讀網路延遲時間的問題陳述。
2. Formulate brute force
起草一個簡單的迭代解決方案。
3. Identify inefficiency
尋找冗餘計算。
4. Optimize search path
使用散列或排序來加速該過程。
5. Final Implementation
清理生產標準代碼。
問題陳述
給定一個由 n 個節點組成的網絡，標記為 1 到 n。您還會獲得時間，即有向邊 times[i] = [ui, vi, wi] 形式的行進時間列表，其中 ui 是來源節點，vi 是目標節點，wi 是訊號從來源行進到目標所需的時間。
我們將從給定節點 k 發送訊號。返回所有n個節點接收到訊號所需的最短時間。如果不可能所有n個節點都收到訊號，則回傳-1。
寫一個函數 networkDelayTime(times: List[List[int]], n: int, k: int) -> int。
- •1 <= k <= n <= 100
- •1 <= len(times) <= 6000
- •times[i].length == 3
- •1 <= ui, vi <= n
- •ui != vi
- •0 <= wi <= 100
- •All the pairs (ui, vi) are unique
範例
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
2
The signal starts at node 2. It reaches 1 and 3 in 1 unit of time, and 4 in 2 units of time.
times = [[1,2,1]], n = 2, k = 1
1
Signal reaches node 2 from node 1 in 1 unit of time.
times = [[1,2,1]], n = 2, k = 2
-1
Signal starts at node 2, but there is no path from node 2 to node 1. So node 1 never receives it.
Need a Hint?
Edge Cases to Watch
- 空輸入結構
- 單元素輸入
- 大數值範圍
準備好解決了嗎？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面試見解和變化
複雜度分析分解
為什麼時間: Directly evaluates all possibilities.
為什麼選擇太空: Uses standard local memory.
為什麼時間: Optimized paths reduce total operations.
為什麼選擇太空: May trade memory for speed.
最佳化解決方案Python程式碼
最佳化解決方案Python程式碼
def network_delay_time_opt(times, n, k):
return network_delay_time_brute(times, n, k)暴力破解代碼（劇透保護）
暴力破解代碼（劇透保護）
import heapq, collections
def network_delay_time_brute(times, n, k):
edges = collections.defaultdict(list)
for u, v, w in times: edges[u].append((v, w))
min_heap = [(0, k)]
visit = {}
while min_heap:
w1, n1 = heapq.heappop(min_heap)
if n1 in visit: continue
visit[n1] = w1
for n2, w2 in edges[n1]:
if n2 not in visit: heapq.heappush(min_heap, (w1 + w2, n2))
return max(visit.values()) if len(visit) == n else -1Algorithm Pattern Checklist
When dealing with Advanced Graphs data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推薦的 Python 資源
透過相關的互動式教學、備忘單和程式碼比較來擴展您的知識。
Python 日期時間：使用日期和時間
了解如何在 Python 中處理日期、時間、時區和計算。使用日期時間和時間增量來掌握格式化、解析和算術。
如何在 Python 中將字串解析為日期時間
了解如何在 Python 中將字串轉換為日期時間物件。掌握strptime方法，解析日期字串，處理時區，防止格式錯誤。
Python 日期時間格式備忘單
了解如何在 Python 中使用 datetime、strftime 和 strptime 解析和格式化日期和時間。
Python 與 JavaScript：哪種程式語言最好？
Python 和 JavaScript 的全面比較。探索語法差異、效能、用例（後端與前端）和編碼範例。