Élaguer pour respecter la limite de temps
Éliminer les branches qui ne peuvent pas améliorer le résultat
Élaguer pour respecter la limite de temps est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Pourquoi l'élagage est important
Le retour sur trace brut peut explorer beaucoup trop de branches et atteindre la limite de temps. L'élagage coupe rapidement les branches sans espoir pour vous permettre de rester rapide. ✂️
Ce qu'est réellement l'élagage
L'élagage consiste à arrêter une branche dès que vous pouvez prouver qu'elle ne peut pas atteindre une réponse valide ou meilleure. Vous évitez entièrement de l'explorer.
Élagage selon la faisabilité
Si le choix partiel actuel enfreint déjà une règle, retournez immédiatement. Cette vérification de faisabilité évite de construire sur un état incorrect.
if violates(cur):
returnÉlagage par borne
Suivez la meilleure réponse trouvée jusqu'à présent. Si le meilleur résultat qu'une branche puisse atteindre est moins bon, coupez-la. Il s'agit d'une borne sur la branche.
Élaguer en code
Ici, une borne arrête la branche lorsque même l'estimation optimiste ne peut pas dépasser la meilleure réponse actuelle.
if cur_cost + best_possible <= best:
returnOrdonnez judicieusement les choix
Essayer d'abord l'option la plus prometteuse permet de trouver une bonne réponse plus tôt, ce qui relève la borne et permet d'élaguer davantage de branches par la suite.
Propagation des contraintes
Après un choix, réduisez les possibilités des étapes suivantes. Supprimer à l'avance les options impossibles constitue la propagation des contraintes et réduit la taille de l'arbre.
Rupture de symétrie
Si deux branches sont des images miroir l'une de l'autre, n'en explorez qu'une seule. La rupture de symétrie peut réduire le travail de moitié ou davantage, sans perdre de réponses.
Mémorisez les états qui se recouvrent
Si le même état partiel réapparaît, mettez son résultat en cache. La mémoïsation transforme les sous-arbres répétés en une seule consultation rapide.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...Élaguez tôt, pas tard
Vérifiez votre condition de coupure avant de poursuivre la récursivité, et non après. L'élagage précoce évite le travail inutile qui consiste à développer une branche condamnée.
Estimez avant d'exécuter
Vérifiez toujours que le nombre de branches dans le pire cas reste compatible avec les contraintes. S'il est trop élevé, vous avez besoin d'un élagage plus efficace ou d'une nouvelle approche.
Vérification rapide
Quel est le but de l'élagage dans le retour sur trace ?
Récapitulatif : coupez les branches condamnées
Vous avez appris à élaguer avec des vérifications de faisabilité et de borne, un ordre judicieux, la rupture de symétrie et la mémoïsation afin de respecter la limite de temps. 🎯
Apprends Coding Interview Prep avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 90
- Leçons
- 360
Questions Fréquemment Posées
La leçon « Élaguer pour respecter la limite de temps » est-elle gratuite ?
Oui — le texte complet de « Élaguer pour respecter la limite de temps » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Élaguer pour respecter la limite de temps » ?
Éliminer les branches qui ne peuvent pas améliorer le résultat Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Élaguer pour respecter la limite de temps » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Raisonner récursivement : base et récursion
- Générer tous les sous-ensembles
- Permutations et idée des N reines
- Élaguer pour respecter la limite de temps