牆和門
“牆壁和門”問題的詳細指南和 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
清理生產標準代碼。
問題陳述
給你一個 m x n 格房間，用這三個可能的值初始化：
- -1：牆壁或障礙物。
- 0：門。
- INF（由2147483647代表）：一個空房間。
用到最近大門的距離填滿每個空房間。如果無法到達某個門，則應填充 INF。
寫一個函數 wallsAndGates(rooms: List[List[int]]) -> List[List[int]] 傳回修改後的房間網格。
- •m == len(rooms)
- •n == len(rooms[i])
- •1 <= m, n <= 250
- •rooms[i][j] is -1, 0, or 2147483647
範例
rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
The empty rooms are filled with the shortest distance to their nearest gate.
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程式碼
from collections import deque
def walls_and_gates_opt(rooms):
ROWS, COLS = len(rooms), len(rooms[0])
q = deque()
for r in range(ROWS):
for c in range(COLS):
if rooms[r][c] == 0: q.append((r, c))
while q:
r, c = q.popleft()
for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
nr, nc = r + dr, c + dc
if 0 <= nr < ROWS and 0 <= nc < COLS and rooms[nr][nc] == 2147483647:
rooms[nr][nc] = rooms[r][c] + 1
q.append((nr, nc))暴力破解代碼（劇透保護）
暴力破解代碼（劇透保護）
def walls_and_gates_brute(rooms):
ROWS, COLS = len(rooms), len(rooms[0])
def dfs(r, c, dist):
if r < 0 or r == ROWS or c < 0 or c == COLS or rooms[r][c] < dist:
return
rooms[r][c] = dist
dfs(r + 1, c, dist + 1)
dfs(r - 1, c, dist + 1)
dfs(r, c + 1, dist + 1)
dfs(r, c - 1, dist + 1)
for r in range(ROWS):
for c in range(COLS):
if rooms[r][c] == 0:
dfs(r, c, 0)Algorithm Pattern Checklist
When dealing with 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 腳本崩潰。了解 try、 except、finally 區塊以及如何正確引發自訂異常。
如何在Python中產生隨機數（random模組）
了解如何在 Python 中產生隨機數。將 randrange、randint 和均勻浮點產生與播種控制進行比較。
Python pip 套件管理器備忘單
pip 命令列參考指南。学习安装、升级、卸载和管理 Python 包和依赖项。
Python 與 JavaScript：哪種程式語言最好？
Python 和 JavaScript 的全面比較。探索語法差異、效能、用例（後端與前端）和編碼範例。