Temps de retard du réseau
Guide détaillé et implémentation de Python pour le problème 'Network Delay Time'.
1. Apprendre
Le problème « Network Delay Time » est un défi clé dans la section Advanced Graphs.
Cette implémentation se concentre sur la logique de niveau simple dans Python.
Nous accordons la priorité à la précision technique et à la lisibilité du code dans les solutions que nous proposons.
2. Real-World Applications
3. Visual Intuition
Visualisation du flux logique pour le temps de retard du réseau.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Lisez attentivement l'énoncé du problème concernant le temps de retard du réseau.
2. Formulate brute force
Rédigez une solution itérative simple.
3. Identify inefficiency
Recherchez les calculs redondants.
4. Optimize search path
Utilisez le hachage ou le tri pour accélérer le processus.
5. Final Implementation
Nettoyer le code pour les normes de production.
Énoncé du problème
Vous recevez un réseau de n nœuds, étiquetés de 1 à n. Vous recevez également des temps, une liste de temps de trajet sous forme de bords dirigés times[i] = [ui, vi, wi], où ui est le nœud source, vi est le nœud cible et wi est le temps qu'il faut pour qu'un signal se déplace de la source à la cible.
Nous enverrons un signal depuis un nœud k donné. Renvoie le temps minimum nécessaire à tous les n nœuds pour recevoir le signal. S'il est impossible pour tous les n nœuds de recevoir le signal, renvoyez -1.
Écrivez une fonction 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
Exemples
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
- Structures d'entrée vides
- Entrées à élément unique
- Grandes limites numériques
Prêt à résoudre ?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Aperçus et variations des entretiens
Répartition de l'analyse de complexité
Pourquoi le temps: Directly evaluates all possibilities.
Pourquoi l'espace: Uses standard local memory.
Pourquoi le temps: Optimized paths reduce total operations.
Pourquoi l'espace: May trade memory for speed.
Code Python de solution optimisée
Code Python de solution optimisée
def network_delay_time_opt(times, n, k):
return network_delay_time_brute(times, n, k)Code de force brute (spoiler gardé)
Code de force brute (spoiler gardé)
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
Les propriétés standard du problème des graphiques avancés s’appliquent.
Questions connexes
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Ressources Python recommandées
Développez vos connaissances avec des didacticiels interactifs, des aide-mémoire et des comparaisons de codes associés.
Python Datetime
Apprenez à gérer les dates, les heures, les fuseaux horaires et les calculs en Python. Maîtrisez le formatage, l'analyse et l'arithmétique à l'aide de datetime et timedelta.
Comment analyser une chaîne en une date/heure en Python
Découvrez comment convertir des chaînes en objets datetime en Python. Maîtrisez la méthode strptime, analysez les chaînes de date, gérez les fuseaux horaires et évitez les erreurs de format.
Aide-mémoire sur le formatage Python DateTime
Apprenez à analyser et formater les dates et les heures en Python à l'aide de datetime, strftime et strptime.
Python vs JavaScript : quel langage de programmation est le meilleur ?
Une comparaison complète entre Python et JavaScript. Explorez les différences de syntaxe, les performances, les cas d'utilisation (backend et frontend) et des exemples de codage.