Tembok dan Gerbang
Panduan lengkap dan implementasi Python untuk masalah 'Dinding dan Gerbang'.
1. Belajar
Masalah 'Dinding dan Gerbang' merupakan tantangan utama di bagian Grafik.
Implementasi ini berfokus pada logika tingkat mudah di Python.
Kami memprioritaskan akurasi teknis dan keterbacaan kode dalam solusi yang kami berikan.
2. Real-World Applications
3. Visual Intuition
Memvisualisasikan aliran logika untuk Walls And Gates.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Bacalah rumusan masalah Walls And Gates dengan cermat.
2. Formulate brute force
Draf solusi berulang sederhana.
3. Identify inefficiency
Cari perhitungan yang berlebihan.
4. Optimize search path
Gunakan hashing atau pengurutan untuk mempercepat proses.
5. Final Implementation
Bersihkan kode untuk standar produksi.
Pernyataan Masalah
Anda diberikan ruang kotak berukuran mxn yang diinisialisasi dengan tiga kemungkinan nilai berikut:
- -1: Tembok atau penghalang.
- 0: Sebuah gerbang.
- INF (diwakili oleh 2147483647): Ruangan kosong.
Isi setiap ruangan kosong dengan jarak ke gerbang terdekat. Jika tidak mungkin mencapai gerbang, maka harus diisi dengan INF.
Tulis fungsi wallsAndGates(rooms: List[List[int]]) -> List[List[int]] yang mengembalikan kisi ruangan yang dimodifikasi.
- •m == len(rooms)
- •n == len(rooms[i])
- •1 <= m, n <= 250
- •rooms[i][j] is -1, 0, or 2147483647
Contoh
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
- Struktur masukan kosong
- Masukan elemen tunggal
- Batasan angka yang besar
Siap Memecahkannya?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Wawasan & Variasi Wawancara
Perincian Analisis Kompleksitas
Mengapa Waktu: Directly evaluates all possibilities.
Mengapa Luar Angkasa: Uses standard local memory.
Mengapa Waktu: Optimized paths reduce total operations.
Mengapa Luar Angkasa: May trade memory for speed.
Solusi yang Dioptimalkan Kode Python
Solusi yang Dioptimalkan Kode 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))Kode Brute Force (Spoiler Dilindungi)
Kode Brute Force (Spoiler Dilindungi)
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?
Key Revision Notes
Properti masalah Grafik Standar berlaku.
Pertanyaan Terkait
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Sumber Daya Python yang Direkomendasikan
Perluas pengetahuan Anda dengan tutorial interaktif terkait, lembar contekan, dan perbandingan kode.
Penanganan Coba/Kecuali & Kesalahan Python
Cegah skrip Python Anda agar tidak mogok. Pelajari blok coba, kecuali, akhirnya, dan cara memunculkan pengecualian khusus dengan benar.
Cara Menghasilkan Angka Acak dengan Python
Pelajari cara menghasilkan angka acak dengan Python. Bandingkan generasi randrange, randint, dan pelampung seragam dengan kontrol penyemaian.
Lembar
Panduan referensi baris perintah untuk pip. Pelajari cara menginstal, meningkatkan, menghapus instalasi, dan mengelola paket dan dependensi Python.
Python vs JavaScript: Bahasa Pemrograman Mana yang Terbaik?
Perbandingan komprehensif antara Python dan JavaScript. Jelajahi perbedaan sintaksis, kinerja, kasus penggunaan (backend vs frontend), dan contoh pengkodean.