Matrix- und Gitterprobleme
2D-Arrays als Gitter
Eine Matrix ist nur ein 2D-Array, aber in Interviews stellt sie oft ein Gitter dar – eine Karte, eine Tafel oder ein Labyrinth. Jede Zelle grid[r][c] ist ein Knoten und ihre Nachbarn sind benachbarte Zellen.
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
Zeile r, Spalte c, Abmessungen m × n. Einfach – aber die darauf aufbauenden Muster sind mächtig.
Richtungsarrays
Anstatt vier separate if-Anweisungen zu schreiben, verwenden Sie ein Richtungsarray:
# 4-directional (up, down, left, right)
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
# 8-directional (includes diagonals)
dirs = [(-1,0),(1,0),(0,-1),(0,1),
(-1,-1),(-1,1),(1,-1),(1,1)]
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
# process neighbour
Dies ist der am meisten wiederverwendbare Snippet bei Grid-Problemen.
BFS auf einem Gitter – Kürzester Weg in einem Labyrinth
BFS findet den kürzesten Pfad in einem ungewichteten Raster. Beginnen Sie an der Quelle, erkunden Sie alle Nachbarn in Entfernung 1, dann in Entfernung 2 und so weiter.
from collections import deque
def shortest_path(grid, start, end):
m, n = len(grid), len(grid[0])
q = deque([(start[0], start[1], 0)])
visited = {(start[0], start[1])}
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
while q:
r, c, dist = q.popleft()
if (r, c) == end:
return dist
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and (nr,nc) not in visited and grid[nr][nc]==0:
visited.add((nr, nc))
q.append((nr, nc, dist+1))
return -1
DFS auf einem Raster – Flutfüllung und Anzahl der Inseln
(wie das Farbeimer-Werkzeug): Ändern Sie von einer Startzelle aus alle verbundenen Zellen derselben Farbe. DFS oder BFS funktionieren beide.
Diskussion
Anmelden an der Diskussion teilnehmen