Solutions LeetCode dans le bon style

Ce document fournit un aperçu complet de LeetCode-Solutions-in-Good-Style, une ressource proposant des didacticiels conviviaux et des solutions vidéo pour les problèmes d'algorithme et de structure de données. Il présente une approche structurée avec un code clair, des explications détaillées et se concentre sur la construction. une solide compréhension des concepts fondamentaux plutôt que du codage compétitif.

LeetCode-Solutions-dans-le-bon-style

Explication : Comme la plupart de mes camarades de classe, j'étudie et résume en même temps. Je vais essayer de partager davantage et de vous apporter des connaissances utiles. Merci pour votre soutien continu.

Bonjour à tous, il s'agit d'un tutoriel d'entrée de gamme sur "Algorithmes et structures de données". Il convient aux étudiants n'ayant aucune base en algorithmique et aux étudiants ayant changé de carrière. Il ne convient pas à la préparation aux concours d'algorithmes. Le point que je veux transmettre est le suivant : écrire du code avec une logique claire, donc le code que j'écris doit avoir fait l'objet d'une réflexion stricte. Le format est très standard, sans style personnel, et je n'écrirai pas de ligne blanche ou de commentaire afin de réduire. le nombre de lignes de code. C'est ici:

Vous pouvez m'appeler weiwei. Je ferai de mon mieux pour répondre aux questions que je connais dans la mesure de mes capacités et du temps qui me le permet. Si vous avez des questions auxquelles il n'est pas possible de répondre à temps, c'est peut-être parce que je n'ai pas vu la notification sur le site. Vous pouvez m'envoyer un e-mail à [email protected].

Solution vidéo que j'ai enregistrée

J'ai commencé à enregistrer des solutions vidéo en septembre 2019. Au début, j’enregistrais plusieurs fois le matériel dont je voulais parler. Maintenant, rédigez des brouillons textuels pour expliquer les points de connaissance. De nombreuses vidéos ont été accumulées, ce qui constitue en fait un petit cours systématique. Maintenant, elles sont répertoriées ici, j'espère que cela pourra être utile à tout le monde.

0. Comment un utilisateur novice d'algorithme peut-il utiliser LeetCode ? 【Partage d'informations utiles】

1. Complexité temporelle et complexité spatiale

Cette vidéo mentionne que la complexité temporelle est un concept asymptotique et doit être comprise dans une perspective dynamique. Et la définition stricte (forme limite) de la complexité temporelle est expliquée afin que chacun puisse comprendre les règles de calcul de la complexité temporelle. Il a également souligné : la complexité temporelle n'est pas le temps d'exécution du programme ; il faut utiliser « l'espace-temps » et accorder davantage d'attention à l'optimisation de la « complexité temporelle ».

2. Recherche binaire

Cette vidéo présente comment écrire un algorithme de recherche binaire. Bien qu'il existe de nombreux détails sur la recherche binaire, tant que nous maîtrisons les bonnes idées de résolution de problèmes, pratiquons davantage, réfléchissons avec diligence et faisons plus de résumés, le problème de la recherche binaire ne sera pas résolu. ne sera plus difficile.

La vidéo suivante explique plusieurs exemples de questions de recherche binaire. Nous nous concentrons sur l'analyse de la signification de la question et sur la manière d'utiliser les conditions données dans la question pour réduire progressivement la plage de recherche.

A travers l'analyse de la question 4 de "Likou" (trouver la médiane de deux tableaux d'ordre positif), nous vous avons présenté cette technique : Si les propriétés de l'élément cible que vous recherchez sont plus complexes, vous pouvez inverser cette propriété. , puis écrivez des instructions logiques qui peuvent facilement réduire la portée du problème.

3. Enjeux liés au tri

Le « tri par fusion » et le « tri rapide » sont des algorithmes de tri très importants. Une compréhension approfondie de ceux-ci est très utile pour comprendre le mécanisme de fonctionnement des fonctions « récursives ». En même temps, ce sont également des applications typiques de la pensée « diviser pour mieux régner ». ". "Paire d'ordre inversé" et "Problème du drapeau néerlandais (classification des couleurs)" sont également des problèmes d'algorithme très classiques.

Le calcul des « paires d'ordre inverse » repose entièrement sur l'idée du « tri par fusion ».

Dans l'explication du problème de la « classification des couleurs », nous avons présenté à tout le monde les « invariants de boucle ». Dans le processus d'écriture du code, nous devons toujours respecter la sémantique des variables utilisées, « avant l'exécution du programme » et « pendant l'exécution ». reste inchangé après la "fin de l'exécution". Adhérer à notre propre définition des « invariants de boucle » est un moyen important pour nous d’écrire du code correct.

Le « premier nombre positif manquant » est un problème d'algorithme classique. L'idée utilisée est le « hachage sur place », qui peut être compris comme une application spéciale de l'algorithme de « tri par compartiment » : une carotte, un noyau et un seau. Stocker un élément. Je tiens à souligner que le fait que vous puissiez faire cela est étroitement lié à la valeur des éléments du tableau d'entrée.

4. Fenêtre coulissante

Le problème de la « fenêtre coulissante » est un problème typique résolu en appliquant des « invariants de boucle », qui testent nos capacités de codage et de débogage.

5. Problèmes liés à la pile

Les problèmes résolus à l'aide de « piles » nous obligent à utiliser des exemples spécifiques pour constater que leur résolution coïncide avec la règle du « dernier entré, premier sorti » :

La maîtrise des deux questions suivantes est indissociable de l’étude d’exemples précis puis de la synthèse de règles générales.

L'une des applications les plus largement utilisées de la « pile » est la prise en charge de la structure de données pour la « récursivité », la « traversée en profondeur d'abord » et l'« algorithme diviser pour régner ».

6. Recherche combinée

La structure de données « Union Search Set » est actuellement rarement utilisée dans les entretiens. Si vous vous préparez à un entretien algorithmique, vous pouvez l'ignorer.

7. arbre

De nombreux problèmes d'arborescence peuvent être résolus en utilisant le « parcours en profondeur d'abord » ou le « parcours en largeur d'abord ».

8. Algorithme de retour en arrière

L'« algorithme de retour en arrière » est en fait une traversée en profondeur de la « structure arborescente » contenue dans la question. Lorsque vous résolvez ce type de problème, il est important de dessiner un diagramme de structure arborescente sur du papier brouillon.

9. Programmation dynamique

10. Traversée en largeur et tri topologique

11. Table de hachage

12. Opérations sur les bits liées

Mon site Web personnel et mes notes d'étude sur les algorithmes

Groupe WeChat et groupe QQ

Si vous avez besoin d'amis pour travailler ensemble sur les questions, vous pouvez rejoindre le groupe WeChat et le groupe QQ.

MonLeetBook

Voici une promotion pour moi. J'ai récemment lancé mon propre LeetBook sur "LeetBook" : Learning Algorithms from Zero (anciennement connu sous le nom de " Learning Algorithms and Data Structures with " LeetCoin "), qui s'adresse principalement aux amis qui ont changé de carrière et qui ont base zéro. Expliquer les connaissances de base des algorithmes et des structures de données.

illustrer:

Les deux premiers chapitres de LeetBook (Time Complexity, Binary Search) sont lisibles gratuitement. Les chapitres suivants nécessitent un paiement pour être lu. Le prix pour les non-membres est de 99 yuans et le prix pour les membres est de 69 yuans. le même que LeetBook Seulement la partie supplémentaire, pas moins ;

Les titres des cours, les exemples, les exercices et le référentiel de code de support (le référentiel que vous voyez actuellement) sont entièrement publics. Si vous maîtrisez déjà le contenu (y compris les exercices) conçu dans LeetBook, il n'est pas recommandé de l'acheter ;

L'énergie investie est la même que pour écrire la solution normalement, sauf que LeetBook sera plus détaillé dans la réalisation des graphiques. Le contenu payant est le suivant : le temps et l'énergie consacrés à la création de tutoriels, et la participation du personnel et des experts de « Likou » à la production et à la révision, l'expérience de lecture sera meilleure. Il n'est pas exclu que j'écrive généralement plus de points de connaissances sur la résolution de problèmes que LeetBook ;

Utilisateurs intermédiaires et avancés, veuillez acheter avec prudence ;

Vous pouvez me consulter sur le contenu des cours sur le site "Likou" ou mes autres comptes sociaux, ou vous pouvez soumettre une problématique à cet entrepôt. Que j'achète le cours ou non, je ferai de mon mieux pour répondre aux questions que je connais (si le temps le permet et dans la limite de mes capacités). Merci à tous pour votre soutien continu à mon égard. Tout le monde est invité à communiquer avec moi si vous avez des suggestions et des opinions ;

Les connaissances que j'explique se trouvent dans les livres que j'ai recommandés à tout le monde, les blogs, les solutions aux problèmes et les notes que j'ai écrites. Les solutions aux problèmes, les blogs et les notes publiés seront toujours partagés, et tant que j'aurai du temps et de l'énergie, Je continuerai à le faire. Faites du partage et des questions-réponses ;

Je suis très reconnaissant à "Likou" de m'avoir donné l'opportunité de suivre des cours et de m'aider à réaliser un petit souhait.

Classification "Lekou" et répertoire de solutions aux problèmes (organisés selon les chapitres du LeetBook, le chapitre 16 et les suivants sont des chapitres actuellement non inclus dans le LeetBook)

Remarque : Les catégories de questions correspondent aux chapitres de mon LeetBook.

Chapitre 1 Complexité temporelle

Cette partie présente le concept de complexité temporelle. Vous pouvez regarder [Explication vidéo], qui est entièrement gratuite. Il n'y a pas d'exercices pour ce chapitre.

Chapitre 2 Recherche binaire

Type de question 1 : Trouver des indices en deux points

illustrer:

pratique:

Type de question 2 : Déterminer un entier avec une plage de deux points (réponse à deux points)

Pensée algorithmique : réduire et vaincre. Si la question nous oblige à trouver un nombre entier et que cet entier a une certaine plage, nous pouvons progressivement réduire la plage par recherche binaire, et finalement l'approcher à un nombre.

Type de question 3 : Fonction discriminante complexe (problème de maximisation)

Remarque : Ce type de question est essentiellement une « question de type 2 » (réponse en deux points), mais elle peut sembler un peu déroutante lorsque vous l'apprenez pour la première fois. Les questions de ce type sont posées de la même manière. Les mots-clés sont « continu » et « entier positif ». Veuillez faire attention à capturer ces informations clés dans la question.

Chapitre 3 Algorithmes de tri de base

Cette partie contient quatre algorithmes de tri de base : le tri par sélection, le tri par insertion, le tri Hill et le tri à bulles.

Question « Likou » 912 : Solution au tableau trié : Ceci résume quelques points clés et du matériel d'apprentissage pour les problèmes de tri. Vous pouvez commencer à apprendre des algorithmes à partir de problèmes de tri.

Les problèmes de tableaux peuvent être utilisés comme un « domaine de débutant » en algorithmique, car ces problèmes ne peuvent être résolus qu'en maîtrisant les connaissances de base des langages de programmation. Il est facile de trouver des solutions aux problèmes suivants, même si vous n’avez pas acquis de connaissances pertinentes sur la structure des données et les algorithmes.

Point de connaissance : invariants de boucle

Chapitre 4 Algorithmes de tri avancés (important)

Cette partie doit se concentrer sur la maîtrise de trois algorithmes de tri avancés : le tri par fusion, le tri rapide et le tri par tas.

illustrer:

Chapitre 5 Tri non comparatif (facultatif)

Cette partie contient trois types de tri sans comparaison : le tri par comptage, le tri par base et le tri par compartiment. La résolution de ces problèmes nécessite de comprendre le concept de hachage sur place.

Chapitre 6 Fenêtre coulissante et doubles pointeurs

1. Fenêtre coulissante

Méthode d'écriture de référence de fenêtre coulissante (pas un modèle, veuillez ne pas la copier telle quelle, c'est à titre de référence uniquement, il est plus important de comprendre l'idée de conception de l'algorithme) :

Rappel amical : Les questions 3 et 76 sont des questions de base que vous devez être capable de poser. Une fois que vous aurez bien compris les questions ci-dessus, vous pourrez répondre plus facilement aux questions suivantes.

Questions clés :

illustrer:

pratique:

illustrer:

Question 209 : L'information clé donnée dans la question : Tous les éléments du tableau sont des entiers positifs. Il existe au total 3 méthodes comme suit.

Méthode 1 : solution violente

Méthode 2 : Fenêtre coulissante (analyser les raisons pour lesquelles des fenêtres coulissantes peuvent être utilisées)

Méthode 3 : Construisez le préfixe et le tableau, puis utilisez la recherche binaire

Question 438 : Identique à la question 76 ;

Question 567 : Identique à la question 76, sauf que le recueil des phrases qualifiées est différent.

2. Doubles pointeurs

Le problème du « double pointeur » est en fait une optimisation de l'algorithme naïf. De nombreuses solutions qui ne correspondent pas au sens du problème sont résolues en même temps. Il en va de même pour la technique de la « fenêtre coulissante ». Il est encore plus important d’analyser pourquoi les doubles pointeurs peuvent être utilisés.

L'algorithme de recherche binaire utilisé pour trouver des indices peut également être considéré comme une solution à double pointeur.

Chapitre 7 Liste chaînée

Une technique très pratique pour résoudre les problèmes de listes chaînées est le « dessin ». Il en va de même pour l’analyse et l’explication d’autres problèmes algorithmiques (explication à l’intervieweur).

Vous pouvez écrire des fonctions de test pour les listes chaînées afin de faciliter le débogage. Les méthodes d'implémentation recommandées sont les suivantes : ① Créer une liste à chaînage unique via un tableau ; ② Imprimer le nœud actuel et les nœuds suivants en fonction du nœud actuel. Ces deux méthodes peuvent très facilement nous aider à déboguer les programmes liés aux listes chaînées.

Type de question 1 : Problème de pointage de pointeur de liste chaînée de base

Remarque : Certains problèmes nécessitent l'utilisation de « nœuds principaux virtuels » pour éviter une logique de discussion de classification complexe pour le premier nœud de la liste chaînée. Nous avons vu cette idée dans les tableaux, appelés « sentinelles ».

Utilisez des fonctions récursives pour éviter les opérations complexes de modification des variables de pointeur, ce qui simplifie la résolution des problèmes.

illustrer:

Type de question 2 : Compétences de pointeur rapide et lent

Pour être précis, il serait peut-être préférable de l'appeler « pointeur synchronisé ».

En utilisant deux variables de pointeur, elles sont toutes deux situées au premier nœud de la liste chaînée au début. L'une ne fait toujours qu'un pas à la fois, et l'autre ne fait toujours que deux pas à la fois, un devant et un devant. de retour, en même temps. De cette façon, lorsque le pointeur rapide aura fini de marcher, le pointeur lent atteindra la position médiane de la liste chaînée.

La fonctionnalité commune pour résoudre ces problèmes est d’utiliser deux variables de pointeur pour se déplacer de manière synchrone. Les pointeurs rapides et lents se déplacent dans la même direction et la « différence » entre leurs pas est constante. Sur la base de cette certitude, certains problèmes de la liste chaînée peuvent être résolus. L'utilisation de cette idée peut également résoudre les problèmes suivants des listes chaînées :

illustrer:

Type de question trois : Concevoir la structure des données

Chapitre 8 Pile et file d'attente

1. Pile

Type de question 1 : Problèmes de base résolus à l'aide de la pile

Les questions suivantes sont très basiques et doivent être maîtrisées :

pratique:

Type de question 2 : pile monotone

Une pile monotone est une pile ordinaire, qui se conforme au principe du « dernier entré, premier sorti » lors de son utilisation, et les éléments de la pile sont monotones. Les problèmes de "pile monotone" et de "file d'attente monotone" sont généralement très particuliers. Il suffit de maîtriser les exemples et quelques exercices.

Expérience : les indices sont généralement stockés dans des piles monotones.

illustrer:

pratique:

2. File d'attente

Type de question 1 : Problèmes de base résolus à l'aide de files d'attente

Tous les problèmes résolus à l’aide de files d’attente de traversée en largeur d’abord.

Type de question 2 : file d'attente monotone

Une file d'attente monotone n'est qu'une file d'attente ordinaire. Ce problème se retrouve actuellement dans la file d'attente monotone sur "Likou". La clé est d'analyser clairement pourquoi l'algorithme conçu rend la file d'attente monotone. De plus, il existe des exemples d'utilisation de files d'attente monotones pour l'optimisation dans le "Problème du sac à dos". Les amis intéressés peuvent en apprendre davantage, ce qui constitue une connaissance de la compétition.

Expérience : les indices sont généralement stockés dans des files d'attente monotones.

Chapitre 9 File d'attente prioritaire

Remarque : Il est nécessaire de comprendre l'implémentation de "heap" comme une "file d'attente prioritaire". Cela vous aidera à comprendre les détails de codage de remove() et replace(), afin que vous soyez plus efficace lors de l'utilisation du tas.

Application : sélectionnez dynamiquement l'élément de priorité la plus élevée dans la file d'attente actuelle, en vous concentrant sur la compréhension de la signification de « dynamique ».

Chapitre 10 : Recherche combinée

Et vérifiez l'[explication vidéo] des points de connaissance dans la solution vidéo à la question 990. Les questions de base et courantes comprennent :

Questions facultatives :

Chapitre 11 Arbres (arbres binaires et arbres de recherche binaire)

Chapitre 12 Algorithme de retour en arrière

Type de question 1 : Problème de base de retour en arrière

Grâce à ces questions, vous pouvez comprendre l'idée de l'algorithme de backtracking. Les points de connaissance de l'algorithme de backtracking sont expliqués dans la solution vidéo et la solution textuelle de la question 46 de « Likou ».

Le retour en arrière consiste à utiliser un parcours en profondeur d'abord pour rechercher toutes les solutions de l'arbre (graphique). Le parcours en profondeur d'abord a une structure récursive évidente.

Conseils pour résoudre les problèmes suivants : ① Dessinez, dessinez, dessinez ; ② Comprendre le parcours et la récursivité en profondeur ; ③ Déboguer davantage, déboguer davantage.

Type de question 2 : problème de retour en arrière sur les chaînes

Points clés à comprendre : Puisque la chaîne génère de nouveaux caractères à chaque fois, il n'est pas nécessaire de réinitialiser l'état.

Type de question trois : Remplissage d'inondation

Type de question 4 : Quelques questions de jeu

illustrer:

Chapitre 13 Programmation dynamique (Partie 1)

Deux idées importantes de programmation dynamique :

Deux directions de réflexion en programmation dynamique :

Trois conditions doivent être remplies pour résoudre le problème en utilisant la programmation dynamique :

Deux concepts importants de la programmation dynamique :

Référence de classification des questions :

Remarque : Les questions typiques données ci-dessous seront ajoutées (2 décembre 2020).

1. Pour commencer

Comprendre les deux méthodes de programmation dynamique : la récursion mémoire « descendante » et la récursion « ascendante ».

2. Sous-problèmes répétés

Cette partie nécessite l'utilisation du « principe de multiplication par comptage par étapes » et du « principe d'addition par comptage catégoriel ».

Question 70 : C'est la même question que les nombres de Fibonacci. Les problèmes de comptage utiliseront le principe de comptage de classification et le principe de comptage de pas.

3. Sous-structure optimale

illustrer:

Question 377 : Notez que le contrôle n'est pas un problème de sac à dos.

4. Aucune séquelle

pratique:

Voici quelques problèmes classiques de « programmation dynamique ». Parce que ces questions sont si importantes, elles sont incluses dans une catégorie distincte.

5. Somme maximale des sous-segments

pratique:

6. Sous-séquence ascendante la plus longue

Remarque : La question 300 est un problème de programmation dynamique très classique. La solution de $O(N log N)$ définit l'état en fonction des caractéristiques du problème lui-même et prouve que le tableau d'états est un tableau ordonné, ce qui réduit la complexité temporelle.

pratique:

7. La sous-chaîne commune la plus longue

8. Intervalle DP et DP partitionné

Intervalle DP :

DP partitionné :

9. Arbre DP

Chapitre 14 Programmation dynamique (Partie 2)

1. Problème de sac à dos

Neuf conférences sur les sacs à dos : https://github.com/tianyicui/pack

("Game Type DP", "State Compression DP", "Digital DP", etc. seront ajoutés.)

Autres questions

Chapitre 15 Algorithme gourmand

Chapitre 17 Tables de hachage

Chapitre 18 Sommes de préfixes et tables de hachage

Chapitre 19 Traversée en largeur d'abord

Quelques problèmes avec la traversée des arbres en largeur et quelques problèmes dans LeetBook.

Chapitre 20 Algorithme de théorie des graphes (arbre couvrant minimum)

Chapitre 21 : Algorithme de théorie des graphes (plus court chemin à source unique)

Chapitre 22 : Algorithme diviser pour régner

L'idée de diviser pour régner (diviser pour régner) divise un problème plus vaste en plusieurs sous-problèmes plus petits du même type, puis résout ces sous-problèmes de manière récursive. Une fois chaque sous-problème terminé, la solution à. le problème d'origine est obtenu.

L'algorithme diviser pour régner peut être exécuté en parallèle, mais dans le domaine des algorithmes de base, l'algorithme diviser pour régner est exécuté selon une méthode de parcours en profondeur d'abord.

Algorithmes typiques qui appliquent l'idée de diviser pour régner : tri par fusion, tri rapide.

Problèmes typiques de la pensée diviser pour régner : « Question 51 de l'épée pointe vers l'offre » : « Question 51 de l'épée pointe vers l'offre » 51. Paires d'ordre inversé dans un tableau (explication vidéo).

Autres questions typiques (à ajouter)

Il continuera à être mis à jour et les amis sont invités à faire part de leurs précieux commentaires !