Waktu Tunda Jaringan
Panduan terperinci dan implementasi Python untuk masalah 'Waktu Tunda Jaringan'.
1. Belajar
Masalah 'Waktu Tunda Jaringan' merupakan tantangan utama di bagian Grafik Tingkat Lanjut.
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 Waktu Tunda Jaringan.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Bacalah pernyataan masalah untuk Waktu Tunda Jaringan 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 diberi jaringan n node, diberi label dari 1 hingga n. Anda juga diberikan waktu, daftar waktu perjalanan sebagai tepi terarah times[i] = [ui, vi, wi], dengan ui adalah node sumber, vi adalah node target, dan wi adalah waktu yang dibutuhkan sinyal untuk melakukan perjalanan dari sumber ke target.
Kami akan mengirimkan sinyal dari node k tertentu. Mengembalikan waktu minimum yang dibutuhkan semua n node untuk menerima sinyal. Jika tidak mungkin semua n node menerima sinyal, kembalikan -1.
Tulis fungsi 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
Contoh
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
- 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
def network_delay_time_opt(times, n, k):
return network_delay_time_brute(times, n, k)Kode Brute Force (Spoiler Dilindungi)
Kode Brute Force (Spoiler Dilindungi)
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?
Key Revision Notes
Properti masalah Grafik Lanjutan 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.
Python Datetime
Pelajari cara menangani tanggal, waktu, zona waktu, dan penghitungan dengan Python. Kuasai pemformatan, penguraian, dan aritmatika menggunakan datetime dan timedelta.
Cara Mengurai String ke Datetime dengan Python
Pelajari cara mengonversi string menjadi objek datetime dengan Python. Kuasai metode strptime, parsing string tanggal, tangani zona waktu, dan cegah kesalahan format.
Lembar
Pelajari cara mengurai dan memformat tanggal dan waktu dengan Python menggunakan datetime, strftime, dan strptime.
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.