Démarrer les boutons dans les entrevues de codage : structures de données dans Python

1. Prêt ? Définissez. Allez.: [MUSIQUE] Les interviews de codage sont vraiment intimidantes. Il y a des questions difficiles, des énigmes délicates et même des problèmes insolubles. Il existe des plans d'attaque pour chaque scénario, mais nous nous concentrerons sur le plus évident lorsque la question sera claire. Où il n'y a pas de balles courbes, pas de trucs. Je veux m'assurer que tu réussisses l'entretien. Bonjour. Je suis Alvin, chercheur dans l'industrie. Au printemps dernier, j'ai reçu des offres de Meta, Apple, Amazon, Tesla et bien d'autres. Ces dernières années, j'ai également reçu des offres d'ingénierie de la part de Google, NVIDIA, Facebook et Lyft. L'expérience que j'ai acquise au cours de ces entretiens a été inestimable. Je me suis vraiment assise pour comprendre quels sont les éléments qui ont fait le succès de mes entretiens ? Quels sont les principes de base et les astuces ? Ce cours est un pas vers des directions importantes, un pas en avant dans la préparation d'un entretien et un pas en avant dans la maîtrise du codage. Pour atteindre ces deux objectifs, nous allons en apprendre davantage sur les structures de données. Les structures de données permettent d' organiser les données. Dans ce cours, vous verrez des exemples expliquant comment elles fonctionnent et comment les utiliser. À la fin du cours, vous aurez acquis deux compétences, une pour chaque objectif. Vous serez en mesure de choisir des structures de données à utiliser pour coder les entretiens. C'est un gros problème. Au lieu d'inventer des algorithmes efficaces, il suffit de créer un algorithme efficace prêt à l'emploi pour les appels. Vous serez également en mesure d'implémenter ces structures de données, combinant et en mélangeant les implémentations selon les besoins. C'en est une aussi. Connaître efficacement les implémentations vous donne un code de départ lors de l'entretien, une longueur d'avance. J'espère que tu es enthousiaste. Je sais que je le suis. Allons-y. 2. Pourquoi vous avez besoin de structures de données: Permettez-moi de vous expliquer pourquoi vous avez besoin de structures de données, en particulier pourquoi ce cours sur les structures de données est si essentiel à votre développement en tant que codeur, et comment vous pouvez tirer parti de ce cours de manière efficace. Nous aborderons trois points de discussion principaux : tout d'abord, nous discuterons des avantages de la maîtrise de ce sujet, deuxièmement, nous aborderons des objectifs d'apprentissage spécifiques du cours pour accélérer votre maîtrise, et troisièmement, nous vous proposerons un exercice qui vous aidera à acquérir de la maîtrise une fois le cours terminé. Voici notre premier point de discussion, pourquoi vous devriez vous y intéresser, pourquoi je donne ce cours, les avantages que vous en retirerez. Le plus grand avantage de suivre ce cours est d'être mieux préparé aux entretiens. Il existe deux types d'entretiens techniques : Tout d'abord, il y a des questions de codage, sont des problèmes spécifiques tels que comment inverser une chaîne de caractères ? Comment supprimer tous les numéros dupliqués ? Ensuite, il y a des questions de conception des systèmes. Ce sont des questions plus générales, telles comment créeriez-vous un clone d'Airbnb ? En gros, comment concevoir infrastructure et des logiciels pour l'ensemble d'un produit. Les deux entretiens peuvent être difficiles, mais les structures de données vous aident énormément de ces deux entretiens techniques, et voici comment procéder. Voici deux avantages spécifiques liés à la connaissance des structures de données. avantage numéro 1 concerne votre premier entretien technique, les entretiens de codage. Une part importante, probablement plus d'un tiers des questions de codage, concerne les structures de données. Si vous connaissez vos structures de données, vous pouvez souvent appliquer des algorithmes à vos entretiens au lieu de les concevoir. C'est énorme. Il n'est pas nécessaire de trouver des idées à partir de zéro. Si vous savez que la structure de données A répond exactement à ces besoins, vous dites simplement  : « Je sais que les HashMaps sont idéales pour ce cas d'utilisation ; voici pourquoi et comment je l'utiliserais ». C'est une réponse géniale à l' entretien. avantage numéro 2 concerne votre entretien de conception de systèmes, possibilité d'optimiser les systèmes pour votre application spécifique, fois lors de vos entretiens et dans la pratique. Je ne parle pas d'un système 10 ou 25 % plus rapide, je parle d'un système qui gère des ordres de grandeur plus efficacement en choisissant la bonne base de données, le bon serveur ou infrastructure sans serveur, et bien plus encore. Vous diriez : « Nous avons besoin de graphes acycliques dirigés. Les bases de données de graphes sont optimisées spécifiquement pour ce type de relation, et voici pourquoi. » Il s'agit maintenant d'une décision de conception bien informée et convaincante. L'avantage numéro 3 dépasse le processus d'entretien. comprenant les structures de données, vous serez en mesure d'aborder sujets plus avancés au-delà de vos entretiens. En informatique en général, ces sujets vous donnent de nouvelles capacités, comme la création d'un jeu. L'un des outils de création de jeux les plus populaires, Unity, utilise ce que l'on appelle un paradigme de programmation orienté données. Comme son nom l'indique, il est très important de comprendre vos structures de données. En résumé, voici trois avantages pour comprendre les structures de données. Être capable de postuler à partir de zéro au lieu de concevoir des entretiens de codage, d'optimiser l'application dans les entretiens de conception de systèmes et d'aborder sujets plus avancés pour ouvrir de nouvelles portes au-delà des simples entretiens. Dans ce cours, nous allons nous concentrer sur l'avantage numéro 1. Dans une leçon sur deux, vous vous entraînerez à appliquer des structures de données pour coder des questions d' vous vous entraînerez à appliquer des structures de données entretien. Pour profiter de ces avantages, vous devrez vous concentrer sur deux objectifs d'apprentissage dans ce cours. L'objectif numéro 1 est de connaître le fonctionnement de chaque structure de données et de s'entraîner à implémenter chaque structure de données. Cela est essentiel car, ultérieurement, vous devrez peut-être implémenter certaines parties de ces structures de données ou combiner des structures données à des fins différentes. Comme dans mes autres cours, je vous recommande vivement de coder à mes côtés, placer cette vidéo d'un côté de votre écran et votre éditeur de code préféré de l'autre côté. Copiez mon code exactement, et pas besoin de vous précipiter, mettez la vidéo en pause chaque fois que vous en avez besoin. Le plus important, c' est de développer la mémoire musculaire. L'objectif numéro 2 est de savoir comment et quand utiliser chaque structure de données. En particulier, n'oubliez pas les avantages et les inconvénients de chaque structure de données. Dans la leçon suivante, nous allons partager des éléments de rubrique spécifiques sur la base desquels vous jugerez chaque structure de données. Les avantages et les inconvénients ne sont pas simples, ils sont très précis et bien définis. En résumé, vos deux principaux objectifs d'apprentissage sont de savoir comment fonctionnent les structures de données en pratiquant les implémentations et le codage à mes côtés, ensuite, de savoir comment et quand utiliser les données structures en se souvenant des avantages et des inconvénients que nous passons en revue. Notre dernier point de discussion est de savoir comment renforcer votre compréhension de la structure des données au-delà de ce cours. Bien sûr, c'est pour s'entraîner, mais ce n'est pas vraiment ce à quoi vous vous attendez. Nous devons inverser la tendance, prétendre que vous êtes l'intervieweur, disons que vous êtes en train de rédiger les questions sur la structure des données. Votre tâche consiste à vous entraîner à concevoir des questions de structure de données et le faire quotidiennement pendant trois jours. L'objectif est de vous faire réfléchir aux structures de données quelques fois après une bonne nuit de sommeil. Faites-le pendant vos temps libres, pendant vos trajets domicile-travail, pendant que vous vous brossez les dents ou pendant que vous faites la queue. Ajoutez ceci à votre liste de choses à faire quand je m'ennuie. Plus vous faites cela, plus vous poserez de questions, mieux vous maîtriserez les structures de données. Pour résumer, nous avons discuté des avantages de la connaissance des structures de données, meilleure préparation aux entretiens et d'un tremplin vers des sujets avancés Nous avons discuté de vos objectifs d'apprentissage, pour savoir comment implémenter des structures de données et comment utiliser les structures de données, nous avons enfin discuté d'un moyen renforcer vos connaissances Trois jours après le cours, concevez une question sur la structure des données chaque jour. Je vous encourage également à poster votre question dans la section discussion, ma faute. Je suis vraiment très sérieux. C'est incroyablement gratifiant pour moi de voir les questions que vous postez, qu'il s'agisse d'une question que vous avez posée ou d'une question concernant le cours Veuillez donc les télécharger. J'ai hâte de le voir. C'est tout pour la vue d'ensemble. Pour obtenir une copie de ces diapositives et d'autres ressources, n'oubliez pas de consulter le site Web du cours. Nous avons terminé l' aperçu et nous verrons ensuite comment comparer les structures de données. 3. Qu'est-ce qu'une structure de données "bonne ?: Qu'est-ce qu'une bonne structure de données ? Il est essentiel que nous comprenions cela car l'un de nos objectifs d'apprentissage est de savoir comment et quand utiliser chaque structure de données. Mais avant même de poser cette question, nous devons d'abord nous demander ce qu' est une structure de données. Nous pouvons commencer par une définition simple. Une structure de données est simplement un ensemble de données. Cela semble simple, alors nous allons maintenant développer un peu ce point. Élargissons cette définition en ajoutant certaines attentes relatives à une structure de données. En particulier, nous devrions être en mesure de modifier les données contenues et d'y accéder. Une structure de données est un ensemble de données qui peuvent être modifiées et accessibles. Pour modifier la structure des données, nous devrions être en mesure d'insérer des données et de les supprimer. Pour accéder aux données, nous devrions être en mesure de rechercher et de récupérer des données. Ce sont les quatre actions que chaque structure de données doit prendre en charge. Chacune de ces actions peut être très lente ou très rapide en fonction de la structure des données. Cela nous amène à la section suivante, qui est de savoir comment quantifier très rapidement ou très lentement ? quelle mesure chacune de ces actions est-elle efficace ou inefficace ? En d'autres termes, comment évaluons-nous l'efficacité ? Pour évaluer l'efficacité d'un algorithme, nous compterons le nombre d' opérations qu'un algorithme doit exécuter. Par exemple, supposons que nous ayons cette liste de fruits et que nous recherchions de l'avocat. Pour effectuer une recherche dans la liste, nous devons parcourir la liste une par une jusqu'à ce que nous trouvions l'article que nous recherchons. Dans ce cas, nous avons effectué trois « opérations » pour rechercher un avocat. Toutefois, si l'avocat se trouve à la fin ou s'il ne figure pas du tout dans la liste, votre algorithme de recherche devra parcourir tous les éléments de la liste. Pour une liste contenant n éléments, recherche d'une valeur dans une liste nécessite jusqu'à n opérations. Or, la définition de l' opération est vague. Peut-être qu'un accès à la mémoire est une opération, peut-être que la vérification de l'égalité des chaînes est une autre opération. Supposons que le nombre d'opérations nécessaires pour un seul élément est c. La recherche prend alors des opérations cn. Cependant, cette constante c ne nous intéresse pas lorsque nous comparons des algorithmes. Nous disons simplement que l' algorithme prend O sur n opérations où la notation O masque toutes les constantes. C'est ce que nous appelons la statistique O of n, le temps d'exécution ou la complexité informatique. Voici une autre façon de comprendre ce que signifie O of n Complexity. Ce que nous savons, c'est qu'à mesure que la liste s'allonge, le nombre d'opérations, la façon dont vous le comptez, augmente de façon linéaire. Cela signifie que la complexité informatique de nos algorithmes peut être limitée au-dessus et en dessous par des fonctions linéaires. Tout algorithme dont la complexité se situe dans ces limites est O sur n. Par conséquent, la recherche dans votre liste a O de n complexité informatique. Nous savons maintenant que pour une liste, également appelée tableau, il faut O de n fois la recherche. Plus précisément, nous recherchons une valeur lorsque nous ne savons pas où se trouve une certaine valeur dans la liste. Cependant, supposons que nous voulons récupérer exactement le premier article. Nous savons que nous voulons le premier élément et n'avons pas besoin de rechercher une valeur. Cette extraction prend un temps constant ou un O de l'un, car nous accédons simplement à l'élément ith de la liste sans regarder d'autres valeurs. Plus précisément, à mesure que la longueur de la liste augmente, l'effort nécessaire pour récupérer un élément ne change pas. C'est génial. Aller chercher un article ne coûte pas cher. Pour optimiser l'efficacité, cela signifie que nous devons utiliser un tableau lorsque nous devons récupérer plus de données que nous n'en recherchons. Ceci est un exemple de plat pratique à emporter, et nous en verrons beaucoup au cours. Chacune de ces décisions vise à optimiser l'efficacité. Nous devrions modifier notre définition d'une structure de données. Une structure de données est un ensemble de données qui peuvent être modifiées et accessibles de manière efficace. fonction de chaque application, nous devrons sélectionner des structures de données pour garantir cette efficacité. nous analyserons la complexité de cours, nous analyserons la complexité de quelques structures de données. Au fur et à mesure que nous effectuerons ces analyses, nous trouverons plusieurs ordres de croissance courants. Les ordres de croissance sont le O de ce que nous avons vu plus tôt. Nous avons déjà vu deux exemples d' ordres de croissance. Croissance en temps constant O de 1 et croissance linéaire O de n. Ce sont les six ordres de croissance courants présentés ici sur cette diapositive. Mais pour les structures de données et les algorithmes que nous abordons , nous ne verrons que quatre ordres de croissance : O constant de un, O logarithmique de log n, O linéaire de n et O de n au carré. Nous verrons à quoi ressemble O of log n plus tard, mais pour l'instant, gardez à l'esprit que vous disposez d'un nouvel outil pour analyser la complexité algorithmique et que ces quatre ordres de croissance sont les plus courants que vous trouverez. Pour obtenir une copie de ces diapositives et d'autres ressources, n'oubliez pas de consulter le site Web du cours. Vous avez maintenant un nouvel outil à votre disposition et des ordres d'analyse de croissance, qui vous permettent d'évaluer la complexité informatique de n'importe quel algorithme. Plus important encore, il vous permet de sélectionner des structures de données pour différentes applications fonction de la lenteur ou de la rapidité d'insertion, de suppression, de récupération et de recherche d'une structure de données . Dans la section suivante, nous nous entraînerons analyser les ordres de croissance. 4. Les ordres de pratique de croissance: Bienvenue dans la pratique de certaines structures de données. Dans cette leçon, nous allons évaluer les structures de données. En d'autres termes, nous évaluerons les algorithmes et structures de données à l'aide d'un système appelé ordres de croissance. C'est ce dont nous avons parlé dans la leçon précédente. La notation Big O nous indiquera la rapidité ou lenteur d' exécution d'un algorithme en fonction de sa taille d'entrée. Nous allons mettre de côté les tactiques d'entretien pour l'instant, au moins les tactiques spécifiques aux entretiens. Nous aurons certainement des conseils relatifs aux entretiens, mais nous devons d'abord nous concentrer sur les fondamentaux. Commencez par accéder à cette URL, alvinwan.com/data structures101/oog. Une fois cette page affichée, formez le projet pour obtenir votre propre copie modifiable. Pour ce faire, cliquez sur le nom du projet en haut à gauche pour obtenir une liste déroulante. Cliquez ensuite sur les points de suspension en haut à droite pour obtenir une autre liste déroulante. Enfin, cliquez sur le bouton « Fourchette ». Ensuite, je suggère de placer vos fenêtres Skillshare et Repl.it côte à côte, comme indiqué ici. Vous devriez alors voir une fenêtre comme la mienne sur le côté droit. Avant de nous plonger réellement dans les problèmes, passons en revue les ordres de croissance dont nous avons parlé précédemment. Il existe quatre niveaux de croissance pertinents. Pour rappel, ce que j'écris ici est une fonction de n, où n est la taille de l'entrée. Ces ordres de croissance nous indiqueront à quel point la fonction s' exécutera plus lentement si nous augmentons la taille de l' entrée n. Par conséquent, nous voulons que les temps d'exécution croissent plus lentement à mesure que la taille de l'entrée augmente. est bon de remonter dans cette liste de runtimes. Plus l'ordre de croissance est lent, plus l'algorithme ou la structure de données sont efficaces et plus l'algorithme ou la structure de données sont efficaces et privilégiés. Un conseil que j'ai pour vous est connaître ces durées par cœur, sont les quatre durées de base que vous devez connaître pour chaque entretien. La première valeur O (1) ou temps constant signifie que, quelle que soit la taille de l'entrée, notre fonction prend toujours le même temps. Ensuite, O (log n) en parlera plus tard. Il s'agit d'un environnement d' exécution un peu plus compliqué à expliquer. Le troisième O (n), ou temps d'exécution linéaire, signifie que si la taille de notre entrée double, notre temps d'exécution double également. Si la taille de notre entrée triple, notre temps d'exécution triple également. En d'autres termes, le temps d'exécution de notre fonction croît en fait linéairement par rapport à n. O (n) carré signifie ici quadratique. Si nous doublons la taille d'entrée, d'exécution de notre fonction quadruple ou le temps d'exécution de l'algorithme quadruple. Si la taille de notre entrée triple, notre temps d'exécution sera en fait multiplié par neuf, et ainsi de suite. Passons maintenant directement aux exercices. Sur le côté droit, j'ai notre premier exercice. Quelle est la complexité d'exécution des éléments suivants ? Ici, nous avons juste une boucle for pour i dans la plage n. N'oubliez pas que la plage de n vous donne une entrée de n éléments différents. Quelle est la complexité d'exécution de cette fonction ? Mettez la vidéo en pause ici et essayez-la et voici la réponse. Cette fonction itère à nouveau une fois sur chaque élément de cet itérable de n éléments. En d'autres termes, il itère une fois pour n éléments, il itère n fois. Le temps d'exécution de cette fonction ou de cet algorithme est O (n). [RIRES] J'ai oublié de te le montrer. Voici la liste des quatre options d'exécution différentes dont vous disposez. Je les garderai ici au fur et à mesure de ces exercices. Passons maintenant au deuxième exercice. Quelle est la complexité d'exécution de cette fonction, encore une fois, en fonction de n. Nous en avons deux, pour les boucles. Chacun d'entre eux itère jusqu'à n. Une autre façon de voir cela serait de demander combien de fois la fonction d'impression a-t-elle été appelée ? Mettez la vidéo en pause ici et essayez et voici la réponse. Ici, nous le répétons en un rien de temps. Ensuite, pour chaque i, nous itérons également sur j n fois. Cela fait un total de n fois n courses. Cet algorithme est O (n) au carré. Passons à l'exercice suivant. Quelle est la complexité d'exécution de cette fonction en fonction de n ? Ici, nous commençons par n. Ensuite, dans cette boucle while, pour chaque étape, nous aurons cette valeur. Quelle est la complexité d'exécution de cette fonction ? Vous pouvez utiliser un processus d'élimination pour déterminer quel est le temps d'exécution. Mettez la vidéo en pause ici et essayez-la et voici la réponse. La réponse à cette fonction, que nous pouvons déduire par élimination , est O (logn). Voici comment ce processus d' élimination pourrait fonctionner. Nous voyons ici que la fonction n' est certainement pas constante. Cela prend certainement un peu plus de temps chaque fois que n augmente. Ce n'est certainement pas O (1). Cependant, il n'est pas aussi lent que O (n), car O (n) itérerait une seule fois. Il effectuerait une itération sur tous les éléments un par un, jusqu'à n. Cependant, nous ne le faisons pas. Nous réduisons de moitié la valeur à chaque fois. On ne fait que sauter un petit moment. Il n'est pas aussi lent que O (n), et il n'est pas aussi rapide que O (1). Le seul environnement d'exécution intermédiaire est O (log n). Nous le ferons plus précisément plus tard pour expliquer comment se produit O (logn). Mais pour l'instant, parlons d'une explication visuelle. quoi ressemble la croissance logarithmique et que signifie une croissance logarithmique ? La croissance logarithmique est vraiment très lente. Pour vous donner une idée de la lenteur, considérez la fonction de journalisation. N'oubliez pas que n est la taille d'entrée, la valeur de log n est le temps d'exécution. Supposons que notre entrée ait une taille deux, alors que le moteur d'exécution possède une unité d'exécution. Supposons que notre entrée double la taille quatre, le temps d'exécution augmente d'un. Si notre entrée double à nouveau pour atteindre la taille huit, le temps d'exécution augmente d'un. Enfin, si votre entrée double à nouveau pour atteindre la taille 16, le temps d'exécution n' augmente toujours que d'une unité. Notez que notre taille d'entrée doit continuer à doubler pour augmenter le temps d'exécution d'une unité. Cela signifie que notre algorithme est assez efficace. Visuellement, voici à quoi cela ressemble. Nous tracons la taille des entrées le long de l'axe X, nous tracons le temps d'exécution le long de l'axe Y, puis nous tracons tous les points précédemment. Remarquez que notre fonction se développe assez lentement. En fait, voici un diagramme plus grand avec plus de valeurs de x. Vous pouvez voir que notre graphique devient plat très rapidement. En d'autres termes, les fonctions logarithmiques se développent très lentement. Gardez cela à l'esprit. Revenons à notre fonction. Nous pouvons maintenant voir que i ici ceci, ou i ou n, disons que n doit doubler pour augmenter le nombre d'itérations de la boucle while d'une unité. Si n est égal à deux, la boucle while itère une fois. Si n est égal à quatre, cela se répète deux fois. Si n est égal à huit, cela se répète trois fois, et ainsi de suite. Cette valeur n doit être doublée à chaque fois pour augmenter le temps d'exécution d'un seul. Il s'agit d'une croissance logarithmique. L'autre façon de voir cela est que notre fonction logarithmique réduit de moitié la taille d'entrée à chaque étape. Comme vous pouvez le voir ici, nous réduisons de moitié notre charge de travail à chaque étape, donc nous réduisons de moitié notre charge chaque étape. C'est le conseil. Les fonctions logarithmiques réduisent de moitié la taille des entrées à chaque étape. Voici un résumé des trois exemples que nous venons de passer en revue et de leurs durées d'exécution. C'est tout pour les « exemples de base ». Je ne veux pas dire basique, car c'est facile. Ces exemples sont assez confus, surtout lorsque vous les voyez pour la première fois. Je dis « basique » pour signifier que tous les autres exemples constitueront une modification de cette structure de base. Pour déterminer les durées d'exécution futures, il y a deux étapes. Commencez par mémoriser à quoi ressemblent ces «  exemples de base ». Ensuite, une fois que vous connaissez ces exemples, vous pouvez mémoriser les différentes modifications possibles. C'est notre conseil. Passons maintenant à ces modifications, ces exemples délicats. Encore une fois, il s'agit de modifications des exemples ci-dessus qui peuvent sembler confuses ou pour modifier le temps d'exécution. Voici les quatre runtimes précédents. Passons maintenant aux exemples, aux exemples délicats. Combien de fois la fonction print est-elle appelée dans la fonction suivante ? Ici, nous avons une boucle imbriquée. Ensuite, nous avons cette condition if, si i est égal à j. Remarquez cette déclaration if et comment affecte-t-elle la complexité, le cas échéant ? Mettez la vidéo en pause ici et reprenez-la, combien de fois est appelée print ? Voici la réponse. Print n' est appelé que n fois. C'est parce que notre boucle interne n'est exécutée qu'une seule fois. Si i est égal à zéro, alors cette condition ne passe que si j est également égal à zéro. Si i est égal à un, encore une fois, cette condition ne passe que si j est également égal à un. Cela signifie que pour chaque boucle externe, la boucle interne ne s'exécute qu'une seule fois, soit n fois une itération, soit un total de O (n). Passons maintenant à notre prochain exemple délicat. Combien de fois est appelé print en fonction de n ? Ici, nous avons une boucle for imbriquée, mais remarquez que la boucle for interne ne compte que jusqu'à i. Encore une fois, comment cela affecte-t-il le temps d'exécution, le cas échéant ? Mettez la vidéo en pause ici et essayez-la. Voici maintenant la réponse. Il s'avère que même si nous ne faisons qu'itérer jusqu'à i, il semble que nous puissions avoir une complexité d'exécution plus rapide. Il s'avère que ce n'est pas le cas. C'est toujours O (n) au carré. En voici la raison. Je vais devoir t'expliquer en te montrant une photo. Ici, disons que nous avons une boucle pour normale sur le côté gauche. Ensuite, pour chaque valeur de i, nous parcourons j n fois. Nous allons le faire car i est égal à un, nous itérons sur toutes les valeurs de j, i est égal à deux toutes les valeurs de j et ainsi de suite. Continuez à faire ça. Cela signifie qu'il y a un total de n fois différentes au carré que nous imprimons. Supposons que nous imprimions i j. Supposons que nous ayons cette nouvelle boucle for où nous n'itérons que jusqu'à i. Ensuite, cela signifie qu' ici, dans cette première ligne, lorsque i est égal à un, nous N'exécutez j qu'une seule fois. Lorsque i est égal à deux dans la deuxième ligne, on n'exécute j que deux fois. Quand i est égal à trois, on ne lance j que trois fois, et ainsi de suite. Ici, au lieu de n temps total au carré que nous appelons impression, nous avons 1/2 fois n fois carrés que nous appelons impression. Cependant, la moitié de n carré est toujours de l' ordre de n au carré, c'est pourquoi cette fonction est toujours O sur n au carré en termes de complexité algorithmique. Cela met fin à cet exemple délicat. Si vous avez des questions ou si vous êtes toujours confus, n'hésitez pas à poser une question dans la section de discussion. Ce sont les quatre sujets différents que nous avons abordés. Ordres de croissance, nous avons récupéré quelques exemples fondamentaux, croissance logarithmique et quelques exemples délicats, ainsi que la façon dont ils ont modifié ces exemples de base pour des exemples plus délicats. Pour obtenir une copie de ces diapositives et le code final de cette leçon, n' oubliez pas de consulter le site Web du cours. Ceci conclut cette leçon sur l'évaluation des structures de données. 5. Séquences : pile vs file d'attente: Un format courant pour les données est la séquence, et en particulier, il existe deux types de séquences courants. Il y a des piles, comme une pile de vêtements ou une pile de pierres. Il y a aussi des files d'attente, comme une file de personnes ou un tunnel de voitures. Une fois que nous aurons analysé les piles et les files d'attente, nous discuterons de leurs avantages et de leurs inconvénients. Tout d'abord, il y a une pile. Tout comme pour une pile de pierres, vous ajoutez des objets en haut de la pile. Ensuite, pour retirer une pierre ou un objet, vous le retirez également du haut de la pile. Nous résumons cela comme suit : dernier entré, premier sorti ; le dernier élément que vous ajoutez est le premier que vous supprimez. L' opération d'insertion selon cette logique est alors simple. Nous prenons la valeur que nous voulons ajouter, nous la plaçons dans la pile et c'est tout. Il faut une constante ou un O unique pour insérer une nouvelle valeur dans la pile car quelle que soit la longueur de la pile, l'effort pour simplement insérer un élément est le même. Notez que par définition, nous ne pouvons insérer des valeurs qu'en haut de la pile. L'opération de suppression est également simple. Nous prenons la dernière valeur affichée ici en gris et la faisons apparaître. Cela prend également une constante ou O d'une fois. Étant donné que la longueur de la liste ne modifie pas le nombre d'opérations, la suppression pétrit. Ensemble, nous savons maintenant que les piles permettent insertion et une suppression à temps constant, sorte que la modification est peu coûteuse. Mais qu'en est-il de l'accès ? Combien coûte la recherche d'une valeur dans la pile ? Malheureusement, assez lent. Supposons que nous recherchions la valeur 8. On sort un article, on vérifie sa valeur. Est-ce que 7 est égal à huit ? Ce n'est pas le cas, donc nous ajoutons une autre valeur, puis nous vérifions sa valeur. Est-ce que 2 est égal à 8 ? Ce n'est pas le cas, on saute une fois de plus puis on vérifie sa valeur. Est-ce que 8 est égal à ? C'est absolument le cas, donc notre recherche est terminée. Cependant, s'il y a n éléments dans la pile, nous devons effectuer jusqu'à n contrôles. Cela signifie que la recherche prend un temps linéaire ou égal à N. récupération d'un élément spécifique est similaire. Supposons que nous souhaitions récupérer le deuxième élément avec la valeur 8. Nous ajoutons un article, c'est un article, nous en ajoutons un autre, c'est deux articles, puis nous ajoutons un autre article, c'est trois articles. Nous avons enfin trouvé la valeur que nous recherchions. Comme avant, s'il y a n objets sur la pile, se peut que nous ayons besoin de n pops. Cela permet de désactiver la fonction Fetch à temps. En résumé, nous pouvons insérer et supprimer dans une pile en temps constant. La modification est efficace. Cependant, la recherche et la récupération prennent un temps linéaire. L'accès est inefficace. Et si au lieu d'une pile de pierres, nous avions une file de personnes ? La première personne à rejoindre la ligne doit être la première à la quitter. Cela s'appelle une file d'attente. Cette fois, nous insérons une valeur à la fin de la file d'attente et supprimons une valeur au début de la file. C'est ce que nous appelons une séquence du premier entré, premier sorti ou une file d'attente. Comme nous l'avons déjà mentionné, l'insertion est simple. Nous prenons en compte une valeur à ajouter, puis nous mettons cet élément en file d'attente. Quelle que soit la longueur de la liste, la simplicité d' insertion n'est pas affectée. Il s'agit d'une opération O d'une seule opération. La suppression est similaire. Nous prenons en compte une valeur à supprimer illustrée en gris, puis à retirer cette valeur de la file d'attente. Il s'agit également d'une opération O d'une seule opération. En résumé, l'insertion et la suppression d' une file d'attente se font donc à la fois. Encore une fois, la recherche est cependant assez lente. Supposons que nous recherchions la valeur 8 dans la file d'attente , encore une fois, nous retirons la file d'attente, puis vérifiions si 7 est égal à 8 Ce n'est pas le cas, on retire à nouveau la file d'attente, puis on vérifie Est-ce que 2 est égal à 8 ? Ça ne l'est pas. Nous retirons la file et vérifions. Est-ce que 8 est égal à 8 ? Ça l'est. Notre recherche est terminée. Toutefois, s'il y a n articles dans la file d'attente, nous pouvons avoir besoin de n contrôles au maximum. Cela fait de la recherche et des files d'attente un algorithme O of n. Fetch est à nouveau similaire. Supposons que nous cherchions à récupérer le troisième objet avec la valeur 8. Nous retirons un objet, c'est 1, nous retirons un autre objet, c'est 2, et nous retirons un autre objet pour finalement récupérer la valeur du troisième élément, qui est huit. Pour une file d'attente contenant n éléments, nous avons besoin de n files d'attente, donc récupérer est O sur n. Pour résumer, une file d'attente est efficace à modifier, mais inefficace à accéder, comme pour les piles. Analysons maintenant les avantages et les inconvénients des piles et des files d'attente. À l'extrême gauche, nous avons les quatre opérations qui nous intéressent : insertion, suppression, recherche et extraction. Dans la deuxième colonne, nous avons les temps d'exécution d'une pile, et dans la troisième colonne, nous avons les temps d'exécution d'une file d'attente. Malheureusement, les environnements d' exécution eux-mêmes ne sont pas très intéressants. Nous devons donc savoir lequel utiliser en fonction de l'application et de la manière dont chaque structure de données a été définie. Par exemple, une pile est idéale pour suivre les modifications, comme annuler une opération, puis la refaire. Il s'agit d'une pile, car la dernière modification ajoutée est la première que vous annulez. Une file d'attente est idéale pour le traitement séquentiel, comme le traitement des voitures sur une ligne à un pont à péage ou des demandes de téléchargement sur un serveur. Gardez cette diapositive à l'esprit car elle résume l'ensemble de la leçon. Pour obtenir une copie de ces diapositives et d'autres ressources, n'oubliez pas de consulter le site Web du cours. Voyons maintenant ces structures de données en action. Dans la leçon suivante, nous nous entraînerons à utiliser et à implémenter ces structures de données, en abordant les deux objectifs d'apprentissage de ce cours. 6. La pratique des séquences: Bienvenue dans une autre leçon d' entraînement. Dans cette leçon, nous aborderons des séquences, c'est-à-dire des piles et des files d'attente. Tout comme avant, nous allons mettre côté les tactiques d' entretien rudimentaires, nous devons d'abord maîtriser ces fondamentaux. Notez que ces questions sont assez difficiles. Ce n'est pas une application cool. Ce sont des éléments fondamentaux dont vous aurez besoin pour les entretiens et c'est un matériel techniquement difficile. Comme auparavant, accédez à cette URL, alvinwan.com/datastructures101/sequences. Une fois cette page affichée, formez le projet pour obtenir votre propre copie modifiable. Pour ce faire, cliquez sur le nom du projet en haut à gauche pour obtenir une liste déroulante, cliquez sur les points de suspension pour obtenir une autre liste déroulante, puis cliquez sur le bouton Fourchette. Ensuite, je suggère de placer vos fenêtres d' édition Skillshare et Replit côte à côte , comme indiqué ici. Nous allons parler des palmiers dans trois catégories différentes. Nous allons d'abord parler des problèmes de mise en œuvre. Il s'agit de problèmes qui mettent en œuvre les fonctionnalités de base d'une structure de données. Ensuite, l'utilisation, nous allons implémenter certaines fonctionnalités et choisir la bonne structure de données à utiliser, c'est l'élément clé. Nous allons apprendre à sélectionner structures de données en fonction de leurs avantages et de leurs inconvénients. Pour la troisième étape, nous allons combiner des structures de données en une nouvelle structure de données ou une nouvelle application qui nous obligera à jongler entre plusieurs structures de données pour chacun de leurs points forts. Quelle que soit la catégorie de problèmes, voici un conseil de pro que vous devez toujours garder à l'esprit. En fait, nous allons suivre ce conseil de pro pour ensemble de cette leçon et toutes les leçons pratiques qui suivront. Nous allons répondre à toutes nos questions de résolution d'énigmes de cette manière. Vous devez également mener tous vos entretiens de résolution d'énigmes de cette manière. Tout d'abord, nous allons concevoir l' algorithme sans coder. Concevez l'algorithme verbalement ou visuellement avec votre intervieweur. Cela permet à votre intervieweur de vous guider vous et votre réflexion, vers la bonne réponse. Ensuite, signalez la complexité de l'exécution et de la mémoire. C'est important. Tout d'abord pour faire preuve de compréhension, mais aussi pour voir si votre intervieweur souhaite une solution plus efficace. Troisièmement, et enfin, vous codez. Nous allons structurer votre pratique de cette façon. Concevez l'algorithme, puis je passerai en revue la solution, signalerai la complexité, puis je passerai en revue la solution, et enfin je coderai l'algorithme, puis encore une fois nous passerons en revue la solution. L'idée est que même si vous gâchez une partie de ce processus en trois étapes, vous serez toujours en mesure de pratiquer les autres étapes. Voici notre toute première question. Nous allons implémenter des files d'attente mais en utilisant des piles. Mais avant de commencer, laissez-moi vous parler d'un conseil. N'oubliez pas qu'une pile est le dernier entré, premier sorti. Cela signifie que c'est comme une pile de pierres ou une pile de boîtes. Le dernier objet que vous mettez sur cette pile sera le premier que vous retirerez, c'est la pile. Maintenant, la file d'attente est comme une file, une file de voitures, disons. Cela signifie « premier entré, premier sorti ». La première voiture qui s'est alignée est donc la première voiture qui quittera cette file d'attente. Gardez cela à l'esprit. ce que j'ai écrit ici, une file d'attente est premier entré, premier sorti, une pile, dernier sorti, premier entré. Bien sûr, je ne me souviens jamais de ce premier entré, premier sorti, dernier sorti, premier entré. Ce dont je me souviens plutôt, c'est que je travaille avec la pile, comme une pile de pierres, pile de vêtements, une pile de boîtes, et puis je considère une file d'attente comme une simple file d'attente. Si vous gardez cela à l'esprit, cela vous indiquera dans quelle direction vous vous dirigez. Encore une fois, l' exercice consiste à implémenter une file d'attente à l'aide de piles. Si vous faites défiler l'écran vers le bas dans votre ripl.it, vous verrez ceci ici. C'est ce que vous devez mettre en œuvre. Alors mettez la vidéo en pause ici et pensez d'abord à l'algorithme. Comment allez-vous procéder d'un point vue conceptuel ? Alors essayez-le. Voici la réponse. Nous allons donc procéder comme suit. Disons que nous avons cette liste en noir. Nous avons 9, 8, 2, 7. Le neuf est notre premier article. Notre dernier article est sept. Pour émuler une file d'attente, nous devons supprimer le premier élément , neuf, avec cette flèche rouge juste là. Notre objectif, affiché ici en rouge, est de supprimer la valeur 9 et de redonner ou de conserver la pile restante, 8, 2, 7. Sachant que c'est notre objectif, la seule chose que nous pouvons faire avec une pile est de la supprimer du dernier objet. On ne peut en avoir que sept. Eh bien, ça va. Nous pouvons continuer à le faire. On va en faire sept, on va en faire deux, on va en faire huit et enfin, on en aura neuf. On y va. Nous pouvons maintenant en renvoyer neuf. Nous pouvons maintenant retirer la file d'attente d'une pile. Cependant, nous avons perdu tous les objets qui avaient été retirés plus tôt, les 8, 2 et 7. Nous avons donc besoin d'une autre pile pour tous les contenir. Donc, ici, nous allons en extraire sept, mais les placer sur l'autre pile. Ensuite, nous allons en retirer deux, huit, et enfin nous en retournerons neuf. C'est génial. Nous y sommes presque. Cependant, nous avons besoin de 8, 2, 7 dans notre pile. heure actuelle, nous avons l'inverse 7, 2, 8. Donc, ce que nous allons faire, c'est sortir de la deuxième pile et la remettre dans la pile d'origine. Nous allons donc repousser cela, et c'est parti. Nous avons les deux objectifs. Nous sommes en mesure d'en renvoyer neuf comme s'il s'agissait d' une file d'attente et nous sommes en mesure de conserver une pile restante de 8, 2, 7 comme nous le voulions. Maintenant, cela semble être une solution intelligente. Je me dirais probablement qu'il n'y a aucun moyen que je trouve cette solution. Si vous pensez la même chose, je suis totalement d'accord avec vous et je suis là pour vous dire que ce n'est pas un problème. Il n'est en fait pas nécessaire de trouver cette solution. Au lieu de cela, comprenez-le bien. Lors de vos entretiens ou au travail, rappelez-vous simplement les tactiques qui s' offrent à vous. Concentrez donc vraiment votre énergie mentale sur la compréhension de la solution. Si quelque chose n'a pas de sens, il suffit de le demander dans la section de discussion. Sachant qu' il s'agit de l'algorithme, passons à la deuxième étape. Quelle est la complexité algorithmique ? Quelle est la complexité de l'exécution et quelle est la complexité de la mémoire ? Mettez la vidéo en pause ici et essayez de la comprendre . Voici la réponse. La complexité algorithmique ou d'exécution est ici O (n). Nous devons essentiellement effectuer deux n opérations, ce qui correspond à O (n) time. Nous devons placer chaque objet dans la deuxième pile, puis nous devons replacer chaque objet de la deuxième chaque objet de la deuxième pile dans la première. Donc, c'est O (n) pour la complexité d'exécution, pour la complexité de la mémoire, c'est aussi O (n) simplement parce que nous avons dû conserver cette autre pile, et cette autre pile nécessitait jusqu'à n éléments différents. Nous avons donc O (n) complexité d'exécution, O (n) complexité de mémoire. Essayons maintenant de l' implémenter dans le code. Encore une fois, mettez la vidéo en pause ici et essayez-la vous-même d'abord. Nous allons maintenant implémenter cette solution. Nous allons commencer par écrire un constructeur. Ce constructeur va prendre en compte un itérable. Nous pouvons donc voir ici que ce constructeur prend un itérable, qui est une liste d'un seul élément. À partir de l'itérable, nous allons créer une pile. [BRUIT] Maintenant, pour faire la queue, [NOISE], nous allons simplement pousser jusqu'à la pile. [BRUIT] Cependant, je veux retirer la file d'attente ou la supprimer de la pile, c'est là que la logique spéciale entre en jeu. C'est l' algorithme complet dont nous avons parlé ici sur le côté gauche. Nous allons commencer par vider la pile d'origine dans une nouvelle pile. Ici, nous aurons la nouvelle pile. Ensuite, pendant que nous avons des objets dans l'ancienne pile, les placerons dans la nouvelle pile et nous les déplacerons de l'ancienne. Maintenant que nous avons sorti tous ces articles, nous allons enfin sortir le dernier article. Cela nous donnera la valeur que nous devons réellement restituer. Maintenant, remettons la nouvelle pile dans la pile d'origine. N'oubliez pas que c'était la dernière étape où tout était en sens inverse. Nous devons tous les remettre dans la pile d'origine. Maintenant, pendant que la pile contient des objets, nous allons pendant que la pile contient des objets, la remettre dans la pile d'origine. Enfin, nous allons renvoyer la valeur. On y va. Nous avons déjà implémenté notre algorithme en trois étapes. Voyons maintenant si cette fonction passe ou non nos doctests. Pour ce faire, cliquez sur Exécuter, le bouton vert tout en haut de votre fichier. Ici, nous pouvons voir que nous avons eu des défaillances dans toutes les autres fonctions, mais pas celle-ci. N'oubliez pas que notre fonction ici est la file d'attente par pile, qui est absente de cette liste. Nous sommes prêts à y aller. Nous avons réussi nos doctests pour cette fonction. Passons maintenant à la question suivante. Dans notre prochaine question, nous allons faire l'inverse. Nous allons implémenter une pile à l'aide de files d'attente. Ici encore, nous avons implémenté une file d'attente utilisant des piles. Maintenant, dans notre prochain problème, nous allons faire l'inverse. Allez-y, prenez une seconde pour mettre la vidéo en pause et réfléchissez l'algorithme que vous souhaitez créer pour ce faire. Voici une solution. C'est très similaire au dernier problème. Comme avant, nous allons instancier une deuxième file d'attente. Nous allons ensuite prendre chaque article notre première file d'attente et le placer dans la deuxième file. Une fois que nous aurons atteint le dernier élément, renverrons cet élément de la liste comme le ferait une pile. C'est à peu près ça. Maintenant que nous avons l'algorithme, passons à la complexité de la mémoire et de l'exécution de l'algorithme. nouveau la vidéo en pause. Voici maintenant une solution conceptuelle. Ici, nous voulons implémenter une pile, mais nous n'avons qu'une file d'attente. Souvenez-vous qu'une file d'attente ne peut être supprimée que depuis le début alors que pour émuler une pile, il faut pouvoir la supprimer depuis la fin. Nous sommes confrontés à ce dilemme, mais nous allons le résoudre de la même manière ou de la même manière que nous l'avons fait auparavant. Nous allons créer une deuxième file d'attente. Ensuite, nous allons retirer la neuf de la file d' attente et la placer dans la deuxième file. Ensuite, nous retirerons huit files d'attente et ajouterons une deuxième file d'attente, puis nous en retirerons deux, et nous les ajouterons à la deuxième file. Enfin, nous allons retirer sept de la file d'attente et les renvoyer. Ici, nous avons réussi à « en faire sept ». Voici quelque chose de nouveau, contrairement à ce qui se passait avant que notre deuxième file d'attente soit déjà dans le bon ordre. Souvenez-vous qu' avant, notre file d'attente était de 9, 8, 2, 7 et maintenant elle est 9, 8, 2. Il s'agit de l'ordre exact et correct. Nous n'avons pas besoin de le remettre la file d'attente d'origine comme nous le faisions auparavant. Sachant que nous pouvons maintenant savoir exactement comment nous allons implémenter cet algorithme. Toutefois, avant de procéder, signalons la complexité de la fonction en termes d'exécution et de mémoire. Mettez la vidéo en pause ici et essayez de la comprendre. Voici maintenant la solution. La complexité de l'exécution et de la mémoire est telle qu'auparavant. Pour des raisons de complexité d'exécution, nous devons retirer chaque élément de la liste et le placer dans la deuxième file d'attente, de sorte que le résultat soit activé. Maintenant, pour des raisons de complexité de mémoire, nous devons maintenir la deuxième file d'attente. La deuxième file d'attente s'effectue essentiellement ou s'éteint en mémoire jusqu'à n éléments. Voilà, vous l'avez. La complexité de l'exécution et de la mémoire sont toutes deux variables. Passons maintenant à la troisième étape. Essayons de coder cet algorithme. Mettez la vidéo en pause ici et essayez de la coder. Maintenant, allons-y et parlons de la solution. Implémentons la pile à l'aide de files d'attente. Tout comme avant, nous allons créer un constructeur. Ce constructeur va prendre un itérable. Cet itérable sera la valeur initiale de nos files d'attente. Implémentons ensuite la commande push pour cette pile. Il s'agira simplement d'une file et d'un appel de file d'attente. Toute la magie se produira désormais dans la méthode pop. Dans cette méthode pop, nous allons d'abord vider n moins un élément de la file d'attente d'origine dans la nouvelle file. Pour cela, créons une file d'attente. C'est notre nouvelle file d'attente. Alors que notre ancienne file d'attente contient au moins un article, nous allons continuer à en retirer. Ici, il sera en fait retiré de l'ancienne file d'attente et l' ajoutera à la nouvelle file d'attente. Maintenant que nous les avons presque tous retirés de la file d'attente, retirons le dernier article de l'ancienne file d'attente. Oups, donc c'est une file d'attente, une sortie de file. Ce dernier élément serait sept, par exemple. Ensuite, nous retournerions cette valeur. Comme nous l'avons déjà dit, notre nouvelle file d'attente contient tous les éléments dont nous avons besoin dans le bon ordre. Nous allons simplement remplacer notre ancienne file d'attente par la nouvelle. Nous pouvons maintenant renvoyer une valeur. Allons-y, essayons d'exécuter tous nos tests et voyons ce qui se passe. On y va. Nous pouvons constater que notre stack via la file d'attente ne figure plus dans la liste des échecs. Tada, nous avons réussi ces tests. Passons maintenant au problème suivant. Le problème suivant, c'est que nous allons utiliser une structure de données. Je ne vais pas vous dire lequel utiliser, et c'est à vous de décider lequel. Nous allons utiliser des piles ou des files d'attente. En particulier pour imprimer toutes les combinaisons des lettres a et b. Nous allons imprimer toutes les combinaisons de longueur k. Voici un exemple, print_baba de 2 nous donnera aa, ab, bb. Maintenant, si nous appelons print baba of 3, cela nous donnera tous les « mots » de trois lettres qui ont les lettres a et b. Encore une fois, toutes les combinaisons sont possibles. Notez qu'il n' y a pas de répétitions. Notez que chaque valeur ici a une longueur trois. Sachant cela, reprenons le processus en trois étapes dont nous avons parlé plus tôt. Dans un premier temps, concevons l'algorithme. Mettez la vidéo en pause ici et essayez de concevoir l'algorithme. Encore une fois, vous devez utiliser une pile ou une file d'attente. Parlons maintenant de la solution d'un point de vue conceptuel. Ici, dans cette solution particulière, nous allons utiliser une file d'attente. Je vais d' abord désigner la file d'attente en utilisant juste une liste de base juste une liste de base pour visualiser ce qui se passe. Pour commencer, disons que j' ai la lettre A ici. Ce que nous allons faire, c'est d' abord retirer la lettre a. Maintenant, nous avons un et nous allons mettre en file les deux seules manières possibles d'étendre la lettre a. Pour passer d'une séquence d'une lettre de tous les a et b à toutes les séquences de deux lettres possibles de a et de b. Nous allons ajouter aa et ab. Cela prendra en compte toutes les manières possibles de créer une séquence a et b à partir de ce point de départ. Maintenant, nous pouvons le rendre un peu plus complet. Nous allons commencer avec la chaîne vide. Ensuite, nous allons retirer cette chaîne vide de la file d'attente. Ensuite, nous ajouterons les deux seules manières possibles de l'étendre, qui consistent à ajouter un a à la fin ou à ajouter un b à la fin. Ensuite, nous retirerons la file d'attente, puis nous ajouterons a plus a b, donc aa ab. Ensuite, nous recommencerons. Nous allons retirer le premier élément de la file d'attente, qui sera b. Ensuite, nous allons étendre avec ba et bb. Nous allons continuer à le faire. Maintenant, nous allons avoir aa, nous le mettons en file d'attente, puis nous ajouterons aa plus aa plus b, donc aaa, aab. Nous allons continuer à le faire. En nous arrêtant au bon moment, nous nous assurerons d'avoir réellement couvert toutes les séquences de A et de B de longueur k possibles. Sachant qu'il s'agit de l'algorithme, parlons maintenant de la complexité de la mémoire et de l'exécution. Mettez la vidéo en pause ici et voyez si vous pouvez faire face à ces deux complexités. Parlons de la complexité des calculs et de la mémoire. La complexité du calcul et de la mémoire est en fait compliquée dans ce scénario particulier, mais nous en parlerons quand même. Compte tenu de ce que vous savez jusqu'à présent, il ne sera peut-être pas en mesure de trouver celui-ci, mais c'est tout à fait normal. Encore une fois, votre objectif est simplement de comprendre la solution que je présente maintenant. Parlons du nombre de fois que cela prend, ou parlons d'abord du nombre de résultats obtenus ici. Toutes les séquences possibles de trois longueurs de a et de b. Ici, nous allons avoir deux options pour chaque lettre, a ou b fois 2 fois 2. Cela signifie qu'il y a deux options différentes sur trois. Si nous voulons toutes les séquences de longueur k possibles, nous allons en produire deux pour les k réponses différentes. Maintenant, afin de produire deux à k réponses différentes, nous avons dû générer également toutes les solutions à deux longueurs et à une longueur. En réalité, ce que nous avons à faire, c'est de générer deux ou trois options différentes. Nous avons dû passer de deux à deux, puis de deux à un également. Cela est vrai en général. Si nous avions voulu générer les quatre séquences de longueur, nous en aurions généré deux pour une, deux pour les deux, les trois et deux pour les quatre combinaisons différentes et ainsi de suite. En réalité, cela signifie qu'il s'agit en fait d'une somme allant jusqu'à, disons, des valeurs j où j est tout au plus égal à k. Nous avons ici cette méchante sommation d'un tas de termes. Heureusement pour nous, analyse par ordre de grandeur ne concerne que le terme de magnitude le plus important. Ici, nous pouvons simplement résumer cela comme o de 2 à n, ou je suppose k, puisque nous utilisons k. Sachant que cet algorithme est assez lent, c'est la complexité du calcul. Heureusement pour nous, la complexité de la mémoire est, en fait, malheureusement pour nous, la complexité numérique est également la même. O de 2 à k. Il s'agit d'un algorithme assez lent. C'est aussi un algorithme assez cher, mais nous allons laisser cela, que c'est joli, c'est complexe. Mais au moins, compte tenu de ce que nous avons dit jusqu'à présent, c'est une façon de procéder, et nous allons le faire de cette façon pour l'instant. Allez-y, mettez la vidéo en pause ici et essayez de la coder. Voici maintenant une solution. Pour commencer, nous allons créer une file d'attente. Comme nous l'avons déjà dit, nous allons ajouter la chaîne vide. Cette chaîne vide tous les ensembles possibles de séquences de longueur nulle. À partir de là, nous allons générer tous les ensembles possibles de séquences d'une seule longueur, et ainsi de suite. Tant qu'il y a quelque chose dans la file d'attente, nous continuerons à générer encore et encore. Allons-y et supprimons ou retirons la première chaîne de la file d'attente. Si notre mot ici a exactement la longueur k, alors nous allons simplement imprimer ce mot, et nous sommes prêts à partir. Cependant, si le mot n'a pas encore la longueur k , nous l'étendrons. Nous l'étendrons de la lettre a et nous l'étendrons la lettre b. Nous y voilà. C'est tout pour notre fonction. Cela nous donnera toutes les séquences de Kalign possibles car cela garantit que nous allons les étendre avec toutes les possibilités, a et b, et cela garantit que toutes les séquences de Kalign seront capturées au fur et à mesure qu'elles se produisent. S'il y a quelque chose de plus long qu'une séquence de Kalign, alors, eh bien, elle ne mène nulle part. Nous ne continuerons pas à travailler avec elle. En fait, vous pouvez prouver qu'il n'y aura pas de longueur supérieure à k, mais ce n'est pas très important. Le fait est que cette fonction devrait nous donner ce que nous voulons. Allons-y et essayons-le maintenant. le bouton vert « Exécuter » en haut et vous devriez voir que print_baba disparaîtra de cette liste d'échecs. On y va. Print_baba a maintenant disparu de la liste des échecs. Nous avons également réussi ce test. Passons à la question suivante. Dans la question suivante, utilisons maintenant des piles ou des files d'attente pour imprimer les escaliers. En particulier, imprimez le nombre de façons dont nous pouvons monter k escaliers si vous pouvez faire un ou deux pas à la fois. Si vous n'avez qu'un seul escalier, vous ne pouvez le monter que dans un sens. Si vous avez deux escaliers, vous pouvez les monter de deux manières, soit en faisant un pas à la fois, soit en faisant les deux pas à la fois. S'il y a trois marches, vous pouvez soit monter 1,1,1, soit monter deux marches puis une marche, soit monter une marche puis deux marches, soit monter une marche puis deux marches, donc c'est 1,1,1 ; 1,2 ou 2,1. Il y a trois manières de gravir trois marches. Cette fonction est censée calculer le nombre de manières de monter k marches si vous pouvez faire un ou deux pas. Maintenant, avant de considérer l' algorithme, voici un indice. Eh bien, vous pouvez mettre la vidéo en pause ici si vous ne voulez pas l'indice, mais celui-ci est le suivant ; avant nos actions, entre guillemets, pour chaque mot qui n'avait pas encore la longueur k, nous avons pris deux mesures différentes. Vous pouvez ajouter a ou vous pouvez ajouter b. Ici, vous avez quelque chose de similaire. Si vous n'avez pas encore gravi les k marches, vous pouvez effectuer deux actions différentes. Vous pouvez monter une marche ou deux marches. Sachant cela et sachant que nous utilisions auparavant la file d'attente pour représenter toutes les manières possibles de créer un mot, vous pouvez également utiliser cette file d'attente maintenant pour créer toutes les manières possibles de monter des escaliers. Mettez la vidéo en pause ici et voyez si vous pouvez comprendre l'algorithme. Voici maintenant une solution. La solution reflétera en fait assez fidèlement la solution précédente. Ce que nous allons faire, c'est pour chaque escalier, disons que nous avons une file d'attente maintenant, notre objectif sera en sorte que chaque objet de la file d'attente soit un autre moyen d'y parvenir un certain nombre d'étapes. Voici une façon de le dire. Disons que nous en avons zéro. Cela signifie que c'est une façon d' atteindre zéro escalier. Ensuite, nous allons retirer ce 0 de la file d'attente. Ensuite, nous allons ajouter deux éléments à la file d'attente. Vous pouvez faire un pas ou deux. Nous allons prendre 0 plus 1 et 0 plus 2. Vous allez ensuite retirer le premier article de la file d'attente. Ensuite, nous ferons à nouveau la queue. Nous dirons qu'il y a deux possibilités, vous pouvez soit faire un pas, vous pouvez faire 1 plus 1, soit 2, soit faire deux pas, soit faire deux pas, soit trois. Ensuite, nous retirerons de nouveau la file. Nous allons retirer ces deux-là de la liste. Ensuite, nous dirons qu'en voici deux. Vous pouvez faire un ou deux pas à partir de ce moment. Vous pouvez prendre 2 plus 1 ou trois, ou 2 plus 2, soit 4, et suite et ainsi de suite. Tu peux continuer comme ça. En gros, ce qui se passera c'est que si vous comptez le nombre de fois que k apparaît dans cette file d'attente, vous indiquera de combien de moyens il existe pour atteindre ce nombre d'escaliers. C'est tout pour la solution conceptuelle de l'algorithme. Nous allons en fait éviter complexité de la mémoire et de l' exécution pour ce problème particulier, simplement parce qu'il est assez difficile à calculer. Il existe un moyen de le calculer. Nous allons l'ignorer pour l'instant. Je vais inclure une version écrite de la solution dans le fichier de solutions final. En attendant, passons au codage de cette fonction. Encore une fois, mettez la vidéo en pause ici et essayez de coder la solution. Nous allons maintenant coder la solution. Nous allons commencer par créer une file d'attente ici avec seulement zéro élément. Cette file d'attente ne contient désormais aucun élément. Nous allons également initialiser le nombre de façons dont nous pouvons monter jusqu'à k marches est nul. Pendant que nous avons quelque chose dans la file d'attente, donc tant qu'il y a des moyens de monter les escaliers, nous allons sortir de la file d'attente dans un sens pour monter les escaliers. Cela fera sortir la file d'attente dans un sens pour monter les escaliers. Ensuite, si nous avons atteint k pas, nous augmenterons le nombre de manières possibles d' atteindre k pas d'une. Si nous n'avons pas encore atteint k marches, donc les escaliers sont inférieurs à k, alors nous envisagerons des moyens de monter là-haut. Nous envisagerons soit de monter un escalier soit de faire deux pas. Enfin, nous allons renvoyer le nombre total de méthodes qu'il a fallu pour atteindre k pas. Maintenant que vous avez ceci, allons-y et appuyons sur « Exécuter ». On y va. Nous pouvons maintenant voir que print_stairs ne figure plus dans notre liste d'échecs. Nous avons réussi tous les tests. Avant de passer à la question suivante, je voulais aborder cette astuce. Le conseil est de résoudre le problème principal, puis de considérer les cas extrêmes. Nous avons ignoré certains des conseils ici pour les cas extrêmes et vous pouvez les consulter si vous revenez aux diapositives, mais l'idée de base est, encore une fois, concentrer sur le problème principal avant de vous attaquer à Edge cas. Ce n'est pas très pertinent pour le moment, mais au fur et à mesure que nous résolvons les problèmes, nous verrons de plus en plus de cas extrêmes, et parfois ils peuvent nous distraire. Encore une fois, concentrez-vous d'abord sur la résolution du problème central. Ici, nous allons maintenant utiliser des piles et des files d'attente pour vérifier les parenthèses. En fait, c'est le premier problème où nous verrons un tas de cas marginaux aléatoires. Voilà le problème. Faites défiler votre fichier un peu vers le bas et vous verrez que notre objectif est de vérifier si la chaîne fournie contient des parenthèses correspondantes. [RIRES] En fait, je vous ai déjà donné un indice. Vous devriez utiliser une pile, mais allons-y, et faisons défiler la page vers le bas pour voir ce que cela signifie. correspondance des parenthèses signifie que pour chaque parenthèse de départ, vous avez une parenthèse fermante correspondante. Cependant, ce n'est pas seulement s'il existe, il doit être dans le bon ordre. Par exemple, voyez, vous avez ici une parenthèse de départ. En fait, il manque juste une parenthèse de fin, mais voici un cas où vous avez des parenthèses non valides. Ici, vous avez une parenthèse de fin, puis une parenthèse de début. Elles ne sont pas correctement fermées. Cela signifie qu' avant chaque parenthèse fermée, vous avez besoin d'une parenthèse de départ correspondante. C'est ce que signifie correspondre. Il s'agit en fait d'un problème très courant que vous verrez à la fois comme l'exercice et peut-être même lors de l'entretien lui-même. C'est bon à savoir, c'est bon pour comprendre quelle est la prémisse du problème. Encore une fois, nous voulons vérifier si la chaîne fournie contient des parenthèses correspondantes. Encore une fois, l'astuce est d'utiliser une pile. Allez-y, mettez la vidéo en pause ici et voyez si vous pouvez trouver l'algorithme. Parlons maintenant de la solution. Notre solution, comme nous l'avons mentionné précédemment dans l'astuce ou dans l'astuce, consiste à utiliser réellement une pile. Disons que nous avons cette pile juste ici. Cette pile va représenter nombre de parenthèses de départ ou profondeur avec laquelle nous sommes entre parenthèses. Supposons que nous fassions une itération dans la chaîne et que nous ayons vu ces parenthèses de départ, nous allons ajouter une parenthèse de départ ici. Alors maintenant, nous voyons des parenthèses proches. Chaque fois que nous voyons des parenthèses serrées, nous sortons de la pile. Nous sommes sortis de la pile, nous avons retiré un niveau plus haut, nous avons retiré ce groupe. Maintenant que nous voyons d'autres parenthèses de départ, nous allons les rajouter, nous voyons d'autres parenthèses de départ que nous allons rajouter, et puis nous voyons ici des parenthèses fermées, donc allez-y et supprimez-le, puis nous verrons une autre parenthèse de départ, alors ajoutons-la à nouveau. Enfin, nous allons le fermer à nouveau. Maintenant, nous pouvons voir qu'à la toute fin de la fonction, nous avons toujours une parenthèse non fermée, qui est celle-ci. Ce groupe n'est pas fermé. Cela signifie que ce n'est pas un ensemble de parenthèses correspondant, nous pouvons renvoyer faux. Essentiellement, cette pile représente à quel point nous nous trouvons dans cet ensemble de parenthèses imbriquées. Chaque fois que tu descends, cela signifie que nous remontons d'un niveau. Nous nous sommes débarrassés d'un ensemble de parenthèses imbriquées. Si nous ne sommes pas remontés et sortis des parenthèses, c'est que cela ne correspond pas. En même temps, si vous voyez quelque chose comme ça, qui commence par des parenthèses serrées, alors au tout début de la chaîne, la pile est vide, donc il n'y a rien à faire apparaître. Cela nous indiquera immédiatement que, encore une fois, il s'agit d'un ensemble de parenthèses non valide. C'est ainsi que nous allons procéder sur le plan conceptuel. Passons maintenant à la complexité de l'exécution et de la complexité de la mémoire. Mettez la vidéo en pause ici et essayez de la comprendre. Voici la réponse. En termes de complexité d'exécution et de mémoire, les deux sont linéaires. fur et à mesure que nous itérons ici, eh bien, en gros, nous n'itérons sur la chaîne qu'une seule fois. Chaque élément n' est visible qu'une seule fois. Ensuite, pour comprendre la complexité de la mémoire linéaire, imaginez que si vous aviez une chaîne qui ressemble à ceci, alors notre pile serait simplement constituée de toutes ces parenthèses de départ. Nous avons jusqu'à N éléments différents dans notre pile, ce qui signifie que la complexité de notre mémoire est O de N. Passons enfin à la troisième étape, commençons à coder cet algorithme. Mettez la vidéo en pause ici et essayez de la coder. Allons-y et programmons cet algorithme maintenant. Ici, nous allons créer une pile pour commencer, et pour chaque lettre de la chaîne, nous allons vérifier si la lettre commence un nouveau jeu de parenthèses, nous allons pousser sur la pile. Sinon, on peut supposer que la lettre est une parenthèse fermante. C'est quelque chose que je viens d'écrire tout à l'heure. En gros, lors d'une interview, vous devriez vous demander si la chaîne peut contenir d'autres caractères, comme des chiffres ou des lettres, etc. Maintenant, pour des raisons de simplicité, nous allons supposer qu'il n' y a que des parenthèses dans la chaîne. Ici, si ce n'est pas une parenthèse ouvrante, c'est une parenthèse fermante. Pour chaque parenthèse fermante, nous allons sortir de la pile. Enfin, s'il ne reste plus rien dans la pile, alors nous reviendrons à vrai. S'il reste quelque chose dans la pile, cela signifie que nous n'avons pas fermé toutes nos parenthèses, donc nous devons renvoyer false. Maintenant, sachant cela, voici en fait un conseil que j'ai mentionné plus tôt ou dans les diapositives de tout à l' heure, mais que je n'ai pas mentionné. Considérons ici une séquence vide. Que se passe-t-il lorsque votre pile est réellement vide ? Y a-t-il un endroit dans votre code où votre code serait cassé ? Dans ce cas précis, oui, stack.pop. Ici, on ne vérifie pas si la pile est déjà vide, alors allons-y. Si la pile est déjà vide, alors, que faisons-nous ici ? Si la pile est déjà vide et que nous essayons de supprimer une parenthèse ouvrante, cela signifie que nous avons vu une parenthèse fermante avant voir les parenthèses de départ correspondantes. Sachant cela, cela signifie, encore une fois, la chaîne n'est pas valide, nous devons donc renvoyer false. C'est vraiment tout pour les étuis Edge. Les entrées non valides ne s'appliquent pas ici, donc ce qui met fin à ce problème, allons-y et voyons s' il passe tous nos tests. exécutant le code, vous remarquerez que is_valid_parenthèses ne figure pas dans cette liste d'échecs Nous avons donc réussi les tests de cette fonction. Passons au problème suivant. Voici le conseil, considérez réellement les caractères superflus. C'était là, le conseil. Lors d'une interview, assurez-vous de demander si la chaîne peut contenir d'autres caractères pour ce problème particulier. Maintenant, vous devriez essayer cela par vous-même. Utilisez des piles ou des files d'attente pour vérifier s'il existe parenthèses et des crochets correspondants. Ici, nous avons des parenthèses qui s'ouvrent et se ferment, et nous avons aussi des parenthèses qui s'ouvrent et se ferment. Il s'agit d'un regroupement valide car chaque paire de parenthèses correspond parfaitement. Mais il y a un défi supplémentaire. Notez ici que si vous ne considérez que les crochets, ils sont correctement mis en correspondance. Si vous ne considérez que les parenthèses, elles sont également appariées. Cependant, vous remarquerez que cet ensemble de crochets et de parenthèses se croisent, ce qui constitue un regroupement non valide. Sachant cela, essayons de concevoir un algorithme pour ce problème. Mettez la vidéo en pause ici et essayez voir comment vous utiliseriez vos structures de données, piles ou vos files d'attente pour résoudre ce problème. Encore une fois, vous pouvez vous inspirer de votre problème précédent. Mettez la vidéo en pause ici et essayez-la. Voici une solution. Comme avant, nous allons utiliser une pile, sauf que cette fois, la pile contiendra soit des parenthèses de départ, soit des crochets de départ. Il contiendra toujours essentiellement la ponctuation de départ. Sachant que , chaque fois que nous le voulons, disons que nous voyons des parenthèses fermantes, nous essaierons de sortir de la pile. Dans ce cas, nous allons supprimer ce crochet. Nous voyons actuellement des parenthèses fermantes. Les parenthèses fermantes et cette parenthèse ouvrante ne correspondent pas, ce qui signifie qu'il s'agit d'un regroupement non valide. C'est ce qui se produirait dans ce cas précis. Vous verriez sur la pile quelque chose comme ça. Vous verrez un crochet, vous verrez des parenthèses, puis lorsque vous le fermez vous verrez des parenthèses, , vous verrez ces parenthèses ouvrantes par rapport à cette parenthèse fermante. Donc, lorsque ces deux éléments ne correspondent pas, c'est désormais invalide. Sinon, l'algorithme se présente peu près comme avant. Chaque fois que vous voyez une ponctuation d'ouverture, ajoutez-la à la pile, chaque fois que vous voyez une ponctuation de clôture, essayez de faire ressortir la bonne ponctuation d'ouverture et assurez-vous de saisir la bonne ponctuation d'ouverture. C'est tout pour l'algorithme. Encore une fois, examinons maintenant complexité de l'exécution et de la mémoire. Mettez la vidéo en pause ici et voyez si vous pouvez la comprendre. Maintenant, voici la réponse. Pour la complexité de l'exécution et de la mémoire, nous avons O de N. Comme auparavant, pour la complexité informatique, nous itérons simplement une fois sur chaque caractère, donc c'est O de N. Pour la complexité de la mémoire, encore une fois, nous pourrions avoir une chaîne avec juste un tas de ponctuation d'ouverture comme celle-ci. Si vous avez un tas de signes de ponctuation d'ouverture comme celui-ci, alors votre pile est à peu près aussi longue que votre chaîne d'entrée. Ici, la complexité de notre mémoire est également O de N. Maintenant que nous avons franchi ces deux premières étapes, passons maintenant à la troisième étape. Essayons de coder cet algorithme. Mettez la vidéo en pause ici et voyez si vous pouvez coder. Essayons maintenant de coder cette fonction. Nous allons commencer par créer une pile, puis nous allons itérer sur la pile comme nous le faisions auparavant. Si notre caractère actuel est un signe de ponctuation de départ, nous l'ajouterons à la pile. Ensuite, si nous voyons des parenthèses fermantes, vérifiez que la pile actuelle 7. Les listes : tableau vs liste liée: Notre première catégorie concerne les listes d'articles. Nous analyserons deux structures de données, en particulier les tableaux et les listes liées. Nous aborderons ensuite leurs avantages et leurs inconvénients sur la base de notre analyse. Commençons par terminer notre analyse matricielle. Un tableau est simplement une liste d'éléments. En mémoire, les éléments du tableau sont placés les uns à côté des autres. Plus tôt, nous avons constaté que la recherche dans un tableau prend O de n temps car nous devons parcourir la liste entière un élément à la fois pour trouver la valeur. Nous avons également constaté que la récupération prend O de 1 temps constant. Terminons maintenant cette analyse et voyons combien de temps il faut pour insérer un élément dans le tableau. Supposons que vous ayez ce tableau de trois éléments. Nous sommes en train de visualiser une partie de votre mémoire sur votre ordinateur. Nous aimerions insérer un nouvel élément, d'une valeur de quatre. En théorie, nous pourrions simplement allouer un espace pour quatre comme ça. Toutefois, votre ordinateur a peut-être déjà alloué cet espace à d'autres données. Par conséquent, l' opération d'insertion allouera un nouveau morceau de mémoire pour votre nouvelle longueur de tableau, puis l'algorithme copiera chaque élément un par un. Enfin, la valeur du nouvel article sera mise à jour. Pour un tableau de n éléments, l'insertion fait n copies. L'insertion est donc un O d'une opération. En résumé, l'insertion prend un temps linéaire. Voyons combien de temps prend la suppression. Supposons que vous ayez un tableau de six éléments, vous souhaitez supprimer le troisième élément, le numéro 2 ici. Pour ce faire, l'algorithme de suppression déplacera tous les nombres suivants. Il copie 3 vers l'avant, copie 4 vers l'avant, copie 7 vers l'avant, puis libère la dernière place. Par conséquent, pour un tableau de longueur n, la suppression prend n copies. Cela fait de la suppression O de n. Cela complète notre tableau des complexités d' exécution pour le tableau. Vous remarquerez immédiatement que le tableau est très efficace pour récupérer mais inefficace pour tout le reste. Notre matrice est inefficace pour la modification, notamment parce que nous devons conserver toutes les données contiguës en mémoire. En d'autres termes, tous les éléments doivent être côte à côte comme ceci. Mais nous pouvons changer cela. Mettons chaque élément dans une liste où nous le voulons en mémoire. Pour relier tous les éléments dans une liste, nous devons ajouter des liens. Chacun de ces liens est également appelé pointeurs. Chaque pointeur pointe vers emplacement du prochain élément de la liste. Nous devons également ajouter un marqueur indiquant que la liste est terminée. C'est ce que nous appelons une liste de liens raison de tous les liens que nous avons insérés. Cette liste de liens contient de très belles propriétés. Analysons maintenant cette liste de liens. Supposons que nous souhaitions insérer une nouvelle valeur 3 à la fin de la liste, puis nous attribuons simplement deux nouvelles places et nous nous assurons de 2 points à 3. Quel que soit le nombre d'éléments contenus dans la liste liée, nous avons un travail constant à effectuer pour insérer un nouvel élément, allouer deux espaces et modifier un pointeur. Par conséquent, l'insertion pour les listes liées est égale à O sur 1 en temps constant. L'histoire est similaire, même si nous voulons insérer une valeur au milieu de la liste, allouer deux nouveaux espaces pour la nouvelle valeur et un pointeur, puis pointer la valeur précédente de 8 à 3, puis pointez la nouvelle valeur 3 sur 2. Voilà, nous l'avons. L'insertion est terminée. Quelle que soit la longueur de la liste des liens, il suffit d'allouer deux espaces et de modifier deux pointeurs. Il s'agit toujours du temps constant O de 1. Pour résumer, jusqu'à présent, une liste de liens est insérée à temps constant. Voyons maintenant comment fonctionne la suppression ou la suppression. Supposons que nous voulions supprimer 3, le dernier élément. C'est très simple. Nous inversons simplement ce que nous avons fait pour l'insertion. Supprimez l'avant-dernier pointeur. À présent, l'élément 3 ne fait plus partie de la liste liée. Pour supprimer le dernier élément, vous suffit de le modifier d'un seul pointeur. Il s'agit d'un temps constant ou O de 1. La suppression d'un élément au milieu de la liste est également simple. Supposons que vous souhaitiez supprimer 3, le troisième élément, remplacez le pointeur par huit pour passer à 3. Maintenant, en fait, 3 ne fait plus partie de la liste des liens, et c'est tout. Pour supprimer un élément, où qu'il se trouve, suffit de changer un pointeur. C'est à nouveau constant ou O de 1. Pour résumer, jusqu'à présent, une liste de liens est insérée et supprimée en permanence. Voyons maintenant combien de temps prend l'accès à la liste des liens. Supposons que nous recherchions la valeur 4. Nous devons parcourir toute la liste des liens un par un jusqu'à ce que nous en trouvions 4. Tout d'abord, nous allons vérifier le premier élément. Est-ce 4 ? 9 n'est pas 4, alors accédez à l'élément suivant. Est-ce 4 ? 8 n'est pas 4, alors accédez à l'élément suivant. Est-ce 4 ? 3 n'est pas 4, ensuite, 2 n'est pas 4. Donc, pour une liste liée de longueur n, nous avons besoin de n contrôles au maximum. La recherche dans une liste de liens ne prend pas beaucoup de temps. En résumé, une liste de liens possède temps d'insertion et de suppression constant, mais un temps de recherche linéaire. Malheureusement, la récupération d'éléments à partir d'une liste liée est également assez lente. Supposons que nous souhaitions vérifier ou récupérer le troisième élément de la liste liée. n'y a aucun moyen de savoir où se trouve le troisième élément en mémoire , nous devons donc recommencer depuis le début. Nous allons accéder au premier élément, puis suivre son pointeur jusqu'à l'élément suivant. Accédez à l'élément suivant, puis suivez son pointeur jusqu'à l'élément suivant. Enfin, accédez à cet article. Comme il s'agit du troisième élément, renvoyez sa valeur. Pour une liste liée de longueur n, nous devons parcourir jusqu'à n nœuds. La récupération de l'élément avec d' une liste liée s'exécute en un rien de temps. Pour résumer, nous avons maintenant terminé l'analyse de la liste des liens. La modification de la liste, l'insertion ou la suppression sont efficaces. L'accès à la liste, la recherche ou la récupération est inefficace. Maintenant que nous avons analysé les tableaux et les listes liées, voyons quand utiliser lesquels. C'est la partie la plus importante de cette leçon. Même si vous oubliez tout ce que j'ai déjà dit, gardez la diapositive suivante dans votre poche arrière. C' est votre plat à emporter. Voici un résumé des complexités liées à l'exécution. Sur la gauche, nous avons les quatre opérations que nous avons analysées. Dans la deuxième colonne, nous avons les complexités d'exécution des tableaux d'avant. Sur la droite, nous avons lié les complexités d'exécution de la liste. Pour un tableau, la modification est lente, mais la récupération est rapide. Cela signifie que les tableaux sont idéaux pour de nombreux accès aléatoires à un ensemble de données fixe. Pour une liste de liens, l'accès est lent, mais la modification est rapide. Cela signifie que les listes liées sont avantageuses en raison leur taille dynamique, idéale pour contenir des données en constante évolution. C'est ça. Voici la diapositive récapitulative de cette leçon. Pour obtenir une copie de ces diapositives et d'autres ressources, n'oubliez pas de consulter le site Web du cours. Voyons maintenant ces structures de données en action. Dans la leçon suivante, nous nous entraînerons à utiliser et à implémenter ces structures de données, en abordant les deux objectifs d'apprentissage de ce cours. 8. La pratique des listes: Bienvenue dans une autre leçon d' entraînement. Ici, nous allons faire des listes d'entraînement. En particulier, nous allons couvrir la plupart des listes liées. Comme auparavant, accédez à cette URL alvinwan.com/datastructures101/lists. Une fois cette page affichée, formez le projet pour obtenir votre propre copie modifiable. Pour ce faire, cliquez sur le nom du projet en haut à gauche pour obtenir un menu déroulant, cliquez sur les points de suspension pour obtenir un autre menu déroulant, et enfin, cliquez sur le bouton « Fourchette ». Ensuite, je suggère de placer votre Skillshare et de l' enrouler sur ses fenêtres côte à côte , comme indiqué ici. Voici les différents sous-sujets que je souhaite aborder. Nous allons commencer par l'invite. Il s'agit du code que votre intervieweur vous fournira. Nous aborderons ensuite trois catégories d'invites : la mise en œuvre, l'utilisation, puis la combinaison de différentes structures de données. Pour commencer, sur le côté droit, vous devriez voir le code que votre intervieweur est susceptible de vous fournir. Ici, vous auriez une pile, vous auriez une file d'attente. Eh bien, je suppose que stack and queue ne vous fournirait probablement pas, mais vous pouvez certainement les utiliser si vous en avez besoin. C'est le code qui vous sera donné, essentiellement une implémentation de liste de liens. Vous aurez quelque chose qui ressemble à ce qui suit. Vous auriez la valeur du lien et vous auriez également une connexion au lien suivant. Voici un utilitaire que j'ai fourni pour que vous puissiez réellement visualiser votre liste de liens. Cela peut être fourni ou non. Mais si ce n'était pas le cas, vous pouvez également utiliser cette implémentation. Commençons maintenant par notre tout premier exercice. Maintenant, pour tous nos exercices, y compris celui-ci, nous allons suivre les trois mêmes étapes que celles dont nous avons parlé précédemment. Encore une fois, il est très important de garder cela à l'esprit et de le pratiquer. Tout d'abord, nous allons concevoir l'algorithme sans code verbalement ou visuellement. Ensuite, nous indiquerons la complexité de l' exécution et de la mémoire. Troisièmement, nous allons commencer à coder. Voici l'ajout de la liste des liens. Ce que nous allons faire, c'est ajouter un élément à la liste des liens. Donc, ici, nous aurons, disons, une liste de liens contenant 1, 2 et 3. Nous voulons ajouter la valeur quatre. Ensuite, après l'avoir ajoutée, nous aurons une liste de liens de 1, 2, 3, 4. Maintenant, mettez la vidéo en pause ici pour déterminer l'algorithme que vous utilisez. Conceptuellement, quelles seront les étapes. Voici la réponse. Conceptuellement, ce que nous allons faire, encore une fois, c'est que nous n'avons qu'un pointeur vers le début de la liste de liens. Nous allons suivre ce pointeur comme indiqué ici sur le côté gauche avec cette flèche gauche en noir. Nous allons partir de ce pointeur, puis nous allons passer au lien suivant et continuer jusqu'à lien suivant et continuer ce que vous atteigniez la fin de notre liste de liens. Ensuite, à la toute fin de notre liste de liens, nous allons simplement créer un nouveau lien et le joindre à la liste. C'est ce que nous allons faire d'un point de vue conceptuel. Nous allons passer à la fin de la liste des liens, puis nous allons ajouter un nouveau lien. Sachant que maintenant, encore une fois, nous devrons envisager la deuxième étape notre processus en trois étapes. Quelle est la complexité de la mémoire et de l' exécution de cet algorithme d'ajout ? Mettez la vidéo en pause ici et voyez si vous pouvez la comprendre. Voici maintenant la solution. cet algorithme est linéaire complexité informatique de cet algorithme est linéaire simplement parce que vous devez parcourir l' ensemble de la liste liée, qui peut atteindre la longueur N. Cela représente une complexité informatique O sur N. En ce qui concerne la complexité de la mémoire, nous avons une complexité de mémoire O de 1 simplement parce que nous n'avons utilisé aucune mémoire supplémentaire autre que stockage pour l'élément en cours et la liste de liens existante. Nous n'avons pas réellement créé de nouvelle structure de données. Nous avons juste ce lien qui coûte O de 1. Sachant cela, nous allons maintenant coder l'algorithme. Encore une fois, mettez la vidéo en pause ici et voyez si vous pouvez la coder. Voici maintenant une solution. Ici, nous allons passer à la toute fin de la liste. Ici, nous allons dire que link.next n'est pas nul. Cela signifie que tant que nous aurons un autre lien dans notre liste actuelle, nous continuerons à le parcourir jusqu'à la fin. Enfin, à la toute fin de la liste, ce lien se trouvera maintenant après cette boucle while, le dernier élément, donc ce sera 3. Maintenant que nous en avons 3, nous allons écrire link.next est égal à notre nouveau lien, qui contient une valeur 4. Sachant cela, allons-y maintenant et faisons nos tests. Nous pouvons maintenant voir que l'ajout est absent de cette liste d' échecs, nous avons donc réussi notre test d'ajout. Passons maintenant à la question suivante. Maintenant, avant de passer à la question suivante, même à la question suivante, mémorisez comment parcourir une liste de liens. Il en sera presque toujours de même. Vous allez avoir une boucle while, vous allez vérifier que vous n' accédez pas à un objet sans type, puis vous accéderez simplement au lien suivant. C'est ainsi que vous parcourrez presque toujours une liste de liens. Gardez cela à l'esprit car le problème suivant va utiliser quelque chose de similaire. Allez-y, faites défiler votre fichier vers le bas et vous verrez maintenant que voici la question à insérer. Notre objectif est d'insérer après l'index fourni I. En particulier, supposons que vous ayez cette liste liée 1, 2, 3 et que nous voulions insérer un lien juste ici après l'index 0 et que nous voulions insérer la valeur 4. Ici, nous allons insérer après l'index 0, la valeur 4. Nous avons ici 1, 4, 2, 3. Si vous regardez sur le côté gauche, nous avons visualisé à quoi cela ressemblera pour vous aider un peu. [RIRES] Allez-y, mettez la vidéo en pause ici, et voyez si vous pouvez déterminer à quoi ressemblerait l'algorithme. Maintenant, voici la réponse. Nous allons d'abord parcourir la liste jusqu'à ce que nous arrivions au bon lien pour la modifier. Dans ce cas, supposons que nous insérions H après 9, tout comme nous insérons 4 après 1. Ici, nous allons naviguer jusqu'à 9. Une fois que nous aurons atteint la valeur 9, nous créerons un nouveau lien. Nous allons rétablir le lien 9 à 8, puis nous allons rétablir le lien 8 à 2. Il y a trois étapes. Accédez à l'élément approprié, établissez un nouveau lien vers le lien actuel, puis utilisez le lien actuel pour vous connecter au lien suivant. C'est l'algorithme. Maintenant, sachant qu'il s' agit de l'algorithme, mettez la vidéo en pause ici et déterminez la complexité de l'exécution et de la mémoire. La complexité de la mémoire et de l'exécution ici. La complexité informatique sera linéaire. Il se peut que nous devions parcourir jusqu'à la fin de la liste pour insérer quelque chose. complexité de la mémoire est constante car la seule chose que nous créons est ce lien lui-même, qui est O pour 1 coût de mémoire constant. Sachant cela, passons maintenant au code. Mettez la vidéo en pause ici et essayez de coder. Voici maintenant une solution. Comme avant, nous allons commencer par naviguer à l'aide d'une boucle while. En fait, au lieu d' utiliser une boucle while, nous allons utiliser une boucle for car nous savons exactement combien de pas vous allez effectuer. Pour un lien compris dans la plage i, link est égal à link.next. J'ai utilisé un trait de soulignement ici pour indiquer que nous n'allons pas utiliser cette variable. Tout ce qui nous intéresse, c'est que nous accédons à .next.next.next essentiellement 3 fois jusqu'à ce que vous arriviez au bon élément. Une fois que vous y serez, nous allons réattribuer quelques éléments. Nous allons d'abord réattribuer le prochain attribut de la valeur actuelle à la nouvelle valeur. Mais ensuite, nous devons également connecter ce nouveau lien au reste de la liste des liens. Nous allons l'utiliser pour nous connecter au lien d' origine.next. Encore une fois, dans cet exemple sur le côté gauche, 9 pointait à l'origine vers 2. Nous allons maintenant passer aux points 9 à 8. C'est juste ici. Link.NEXT est égal à notre nouvel objet. Ensuite, nous allons passer aux points 8 à 2, et c'est là, dans la deuxième partie. Nous avons le link.next d'origine et nous le remplaçons par le nouveau link.next. C'est ça Il s'agit de notre fonction d'insertion. Allez-y et recommencez vos tests en appuyant sur le bouton vert « Exécuter » en haut. Nous pouvons maintenant constater qu'il y a un échec de moins. Nous ne l'avons pas inséré dans notre liste d'échecs, nous avons passé les tests avec succès. Passons au problème suivant. Ici, un conseil que nous avons eu pour ce problème et pour les futurs est de toujours vérifier s'il n'y a aucune valeur. Donc, une erreur courante que vous rencontrerez avec les problèmes de listes liées est que vous obtiendrez, par exemple, dans ce lien. Ensuite, vous obtiendrez le lien est un objet NoneType. Next n'est pas un attribut d'un objet NoneType. C'est très courant. Lorsque vous débugez, et avant même de déboguer, avant même d'exécuter le code que vous parlez à l'intervieweur, assurez-vous de parcourir votre code et pendant que vous parlez à l'intervieweur, assurez-vous de parcourir votre code et de vérifier s'il n'y a aucun endroit où il se peut qu'il n'y ait aucune valeur et assurez-vous que vous n' appelez pas .next ou .value sur une valeur NoneType. Dans cette fonction particulière, ici même aux lignes 83 et 84, il est fort possible que je n'étais pas valide. Disons que c'était un 100. Ensuite, nous atteignions à un moment donné la valeur NoneType et nous avions essayé de l'appeler ensuite. Pour rendre cette fonction plus robuste, vous devez vérifier cela. Tu devrais en tenir compte. Dans cette implémentation particulièrement simple, nous ne l'avons pas fait, mais juste quelque chose à garder à l'esprit pour toujours, en vérifiant toujours qu'aucune valeur ne figure dans vos interviews et dans les poèmes que vous écrivez. Passons maintenant au problème suivant. Notre objectif est maintenant d'implémenter une pile à l'aide d'une liste liée. Ici, nous avons une liste de liens, nous en avons un, deux. Notre objectif est de pouvoir traiter cela comme s'il s'agissait d'une pile. Si nous appelons point pop dessus, cela nous donnera le dernier élément qui est deux. Si nous appelons push, ici nous poussons 2, poussons 3, puis si nous pop, récupérerons le dernier élément que nous avons poussé, qui est trois. Revenez, vous obtiendrez l' avant-dernier objet que vous avez poussé , soit deux. Notre objectif est d'implémenter une pile mais en utilisant une liste de liens dans le backend. Allez-y, mettez la vidéo en pause ici et voyez si vous pouvez déterminer si l'algorithme, dans ce cas, est, comment allez-vous pousser et comment allez-vous faire apparaître ? Mettez la vidéo en pause ici. Voici la réponse. Conceptuellement parlant, c'est en fait assez similaire au début. Lorsque nous disons push here, nous allons à peu près écrire la fonction append dont nous avons parlé précédemment. Pouvons-nous dire pop ici, nous allons écrire une nouvelle fonction, supprimer. Nous n'avons pas encore écrit de fonction de suppression, mais elle sera à peu près comme n'importe quelle autre fonction qui supprime d'une liste de liens. Maintenant que nous connaissons l'algorithme, arrêtez la vidéo ici et voyez si vous pouvez comprendre la complexité des calculs et de la mémoire. La solution pour cette partie, la complexité de l' exécution et de la mémoire sera en fait linéaire. Nous allons parcourir jusqu'à la fin de la liste des liens, puis y ajouter des éléments. Dans le cas d'un pop, nous allons parcourir jusqu' à la fin de la liste des liens pour en supprimer. Maintenant, sachant cela, la complexité de la mémoire est constante. La complexité de la mémoire, tout ce que vous faites est de créer un nouveau lien, soit O pour un coût de mémoire. Vous n'êtes pas en train de créer une toute nouvelle liste. Vous ne créez pas une autre structure de données qui stocke des éléments. Vous ne créez qu'un seul lien. Le coût de la mémoire est O d'un. Maintenant, mettez la vidéo en pause ici et essayez de la coder. Écrivons maintenant le code. Ici, nous allons implémenter le push à peu près comme l' ajout réimplémenté plus tôt. Nous allons d'abord définir un lien variable local qui est le début de notre liste de liens actuelle , puis tant que link.next n'est pas nul. Donc, tant que nous avons quelque chose de cette liste de liens, parcourons-la. [BRUIT] Enfin, à la toute fin, nous allons ajouter un nouveau lien. C'est à peu près tout pour la méthode push de la fonction push. Passons maintenant à la suivante. Pour supprimer quelque chose, nous allons à nouveau définir ce lien variable local en commençant par la liste des liens. Ensuite, pendant que nous sommes loin de la fin, donc nous ne voulons pas vraiment le tout dernier lien, nous voulons l'avant-dernier lien parce que ce sera notre nouvelle queue. Nous allons à nouveau traverser. Ensuite, ce que nous allons faire à ce stade, c'est d'abord saisir la valeur du tout dernier élément avant de le supprimer. Ici, nous voulions obtenir la valeur du tout dernier lien. Ensuite, nous allons le dissocier. Maintenant, notre avant-dernier lien ne pointe vers rien. Il s'agit maintenant de notre tout nouveau dernier lien, puis renvoyez enfin la valeur. C'est ainsi que nous supprimons réellement de la toute fin de la liste des liens. Allons-y et cliquons sur le bouton vert, tout en haut, pour exécuter notre fichier et vérifier nos tests. On y va. Nous pouvons maintenant voir que notre stack via Linked list a réellement disparu. n'y en a plus dans notre liste d'échecs, nous avons donc réussi ces tests. Passons au problème suivant. Avant de passer à ce problème, nous avons encore une astuce. Vous voulez facilement poser l'une de vos propres questions, il suffit de mélanger et de faire correspondre l'une d'entre elles. Vous avez parlé de trois structures de données différentes : des listes liées, des piles et des files d'attente. Pour créer une nouvelle question, il suffit de l'implémenter, d'en choisir une à l'aide, puis d'en choisir une autre. Chacune de ces combinaisons vous posera un tout nouveau problème que vous pourrez essayer. Tant que vous pouvez réussir les mêmes tests que ceux que vous avez écrits pour une pile, sauf en utilisant votre toute nouvelle structure de données, vous êtes prêt à partir. Cela vaut pour tout le reste. Si vous avez des tests pour la file d'attente, assurez-vous simplement que votre toute nouvelle structure de données peut réussir ces tests, puis les tests étaient une liste de liens, etc. Il suffit de mélanger et d'assortir n'importe laquelle de ces combinaisons pour obtenir un tout nouveau problème. Implémentons maintenant la suppression du cycle pour une liste liée. En particulier, recherchez et supprimez un cycle dans une liste de liens s'il existe. Pour l'instant, pour des raisons de simplicité, vous pouvez supposer que toutes les valeurs des liens sont distinctes. C'est très important car la première question que vous allez vous poser lorsque vous verrez un cycle de recherche et de suppression est de savoir comment allez-vous détecter un cycle ? Une façon de détecter un cycle serait que si j'ai déjà vu cette valeur auparavant, alors je sais que j'ai atteint un cycle. Je suppose que c'est pour clarifier les choses. Supposons que vous vous déplaciez de gauche à droite le long de cette liste de liens. Au fur et à mesure que vous progressez, si vous en voyez trois deux soudainement, vous savez que vous avez atteint un cycle. Mais cela, vous ne pouvez dire que si vous savez que toutes les valeurs des liens sont distinctes. C'est pourquoi le fait que les valeurs de lien soient distinctes est une question très importante pour ce problème. J'ai écrit qu'ici toutes les valeurs sont uniques. Ce sera l'une de vos premières questions à poser à votre intervieweur. Votre deuxième question, et celle-ci est un peu plus avancée. Vous voulez demander s'il y a une durée maximale de cycle ? Cela a à voir avec l'implémentation, car si vous voulez garder trace de toutes les valeurs que vous avez vues jusqu'à présent, et que vous voulez ensuite dire : « D'accord, ai-je déjà vu cette valeur ? » Vous pourriez alors ne jamais voir de cycle. Cette liste complète de liens peut être longue d'un million et qu'il n'y a aucun cycle nulle part, alors vous l'avez gardée , cette énorme boutique d' un million d'articles qui attend de voir si l'un de ces millions les articles apparaissent à nouveau. C'est une bonne question à se poser. Y a-t-il une durée maximale de cycle ? Parce que de cette façon, vous n' auriez pas à conserver tous les millions d'articles si vous saviez que la durée maximale du cycle n'est que de cinq. Ce sont de bonnes questions à garder à l'esprit pour résoudre ce problème. À mesure que vous progresserez et que vous vous efforcerez de résoudre ces problèmes, vous commencerez à comprendre les questions à poser. Donc, pour l'instant, si vous pensez que ce sont des questions insensées qui sortent de nulle part, c'est normal. Tout comme vous en verrez de plus en plus, vous vous familiariserez avec les types de questions à poser. Pour l'instant, voyons si vous pouvez penser à un algorithme. J'en ai donné des parties , mais mettez la vidéo en pause ici et voyez si vous pouvez trouver un moyen de supprimer les cycles , et voici la réponse. En gros, ce que vous allez faire est de conserver une collection de toutes les valeurs que vous avez déjà vues. Si vous avez déjà vu la valeur, vous savez qu'il s'agit d'un cycle et que vous pouvez briser le cycle en réaffectant simplement link.next en conséquence. Sachant cela, c'est maintenant l'algorithme. Quelle est la complexité de l'exécution et de la mémoire ? Mettez la vidéo en pause ici. Pour la complexité de la mémoire et de l' exécution, en particulier pour la complexité informatique, vous allez avoir O of N. Nous allons parcourir l'ensemble de cette liste un par un. Nous devons le faire pour déterminer s'il y a un cycle ou non. Car la deuxième question est quelle est la complexité de la mémoire ? Pour ce qui est de la complexité de la mémoire, nous allons encore une fois conserver une collection de toutes les différentes valeurs que nous avons vues jusqu'à présent. C'est une complexité de mémoire O of N. O de N complexité de mémoire et O de N complexité de calcul. Sachant cela, essayons maintenant de le coder. Mettez la vidéo en pause ici. Maintenant, allons-y et codons ça. Ici, nous allons commencer par créer un ensemble de valeurs. Donc, si vous ne l'avez pas déjà vu, un ensemble est une structure de données qui vous permet vérifier l'adhésion en temps constant. signifie que vous pouvez faire quelque chose comme celui-ci dans la scène, et cela, quelle que soit la durée de votre set, s'exécutera toujours en temps constant. C'est un set. Nous allons utiliser l'ensemble pour suivre toutes les valeurs que vous avez vues jusqu'à présent. Bien qu'il y ait autre chose dans notre liste de liens, nous allons vérifier si la valeur suivante figure dans notre liste de valeurs de scène. Si c'est le cas, alors nous allons rompre la connexion avec le lien suivant. Encore une fois, si le lien suivant se trouve dans notre liste, j'ai vu des valeurs, nous allons rompre ce lien et nous allons nous arrêter là. Nous supposons qu'il n'y a qu'un seul cycle dans notre liste. Encore une fois, ce serait une excellente question à poser à votre intervieweur. Y aura-t-il plus d'un cycle ? Dans cette question particulière, nous allons faire semblant qu'il n' y a qu'un seul cycle. Voir .ADD et ensuite nous aurons lié la valeur ici. Ce que nous faisons ici, c'est dire, d'accord, nous avons considéré qu' il n'y a pas de cycle ici. Comme il n'y a pas de cycle, ajoutons la valeur des liens actuels à notre liste de valeurs visibles. Enfin, il s'agit de la traversée standard d'une liste de liens, nous allons simplement accéder à l'élément suivant et cela continuera . C'est ça Allons-y, exécutons cette fonction et veillons à ce que nos tests soient réussis. Et voilà, nous pouvons voir que le cycle de suppression ne figure plus dans notre liste de fonctions défaillantes. Passons à la question suivante. Pour la question suivante, et aussi pour celle-ci, un conseil est de toujours dessiner vos listes de liens et de vérifier s'il n'y a pas de liens brisés. Ce que je veux dire par dessin sont essentiellement les illustrations que j'avais auparavant ici. besoin, dessinez-les pour comprendre si Au besoin, dessinez-les pour comprendre si vous reliez les deux de la bonne manière. J'ai abordé certaines de ces questions assez rapidement parce que j'ai déjà écrit la solution et que je les connais. Mais en gros, si vous rencontrez un tout nouveau problème, les chances de créer un lien incorrect sont très élevées. C'est tout à fait normal tant que tu le dessines. Si vous le dessinez, vous pouvez trouver les bons liens pour vous connecter. C'est l'un de mes conseils ici. Dessinez votre liste de liens et vérifiez s'ils ne sont pas rompus. Maintenant, pour ce problème particulier, nous allons en discuter uniquement de manière conceptuelle. En fait, j'ai écrit une solution entièrement fonctionnelle en code pour vous, mais comme elle est assez complexe, nous n'en parlerons que de manière algorithmique. Pour cette question, notre objectif est d'utiliser ou créer un nouvel objet de fichier en utilisant les structures de données que nous avons déjà vues. Notre objet de fichier va être fusionné avec d'autres fichiers. [RIRES] Je viens de vous montrer une partie de la description de la solution. Mais votre objectif est de créer un objet de fichier qui puisse officiellement fusionner avec d'autres fichiers. L'idée est qu'il existe un grand nombre de ces fichiers. Cela signifie que vous ne voulez pas copier toutes les données dans un seul fichier volumineux. Si vous faites toutes ces copies, cela va prendre beaucoup de temps. Comment combiner un tas de fichiers sans les copier ? Si vous ne voulez pas l'indice, allez-y et mettez la vidéo en pause ici. Mais un indice que j'ai pour vous est que nous ne voulons pas copier, donc au lieu de copier, stockons un pointeur vers le fichier suivant. Nous aurons le fichier 1 et ensuite nous dirons, à partir du fichier 1, que nous savons quel est le fichier suivant est le fichier 2. Tout ce que vous allez faire est de stocker une connexion ou un pointeur. Cela devrait ressembler beaucoup à l' une des structures de données que nous venons de couvrir et que j'ai utilisées. Maintenant, mettez la vidéo en pause ici et voyez si vous pouvez comprendre l'algorithme. Voici maintenant la solution. En gros, nous allons utiliser une liste de liens. Chaque fichier sera un lien. Chaque fichier pointe alors vers le fichier suivant et indique qu'il s'agit de la prochaine valeur de fichier à parcourir. C'est ainsi que vous allez stocker cet énorme fichier fusionné. Mais ce n'est pas tout, il y en a un peu plus car nous devons prendre en charge cette fonction de fusion. formidable de savoir comment nous allons les stocker. Nous n'avons pas besoin de faire des copies, mais comment fusionner réellement un nouveau fichier ? Eh bien, le nouveau fichier émergent, il est exactement comme vous l'ajouteriez à n'importe quelle autre liste de liens. Vous passez à peu près à la fin de la liste des liens et vous ajoutez le nouveau fichier. C'est à peu près ça. Pour ce problème ou cet exercice, la seule difficulté conceptuelle est de réaliser qu'il faut utiliser une liste de liens. C'était vraiment le problème du pointeur. Maintenant que nous avons abordé le problème des pointeurs, nous allons passer à autre chose simplement parce que j'ai une solution écrite à ce problème et qu'il y a annotations ligne par ligne pour chacune d' faire et comment cela fonctionne , mais les détails ne sont pas très importants. Passons à la question suivante. Encore une fois, aucun autre navire n'est ici. Listes liées que nous utilisons pour les collections de taille dynamique. Dans ce cas particulier, cet ensemble de fichiers est un ensemble de collections dimensionnées de manière dynamique. Nous ne savons pas quelle est sa taille, nous pouvons y ajouter un tas de fois, et nous pourrions même en retirer un certain nombre de fois. Les listes liées sont idéales pour ces collections, car vous n'avez pas à copier des données chaque fois que vous souhaitez ajouter ou supprimer un objet. Chaque fois que vous souhaitez ajouter ou supprimer un lien, c'est un temps constant. Maintenant, cependant, les tableaux sont parfaits pour un accès aléatoire. Nous en avons parlé un peu auparavant, mais en gros, cela signifie que si vous voulez accéder à l'élément ith d'un tableau, vous savez exactement où il se trouve en mémoire. Vous allez directement à cette partie en mémoire. Cependant, pour une liste liée, si vous souhaitez obtenir le ième élément que vous avez vu auparavant, vous devez parcourir la liste complète, donc pas aussi efficacement. C'est le conseil. Les listes liées sont destinées à des collections de taille dynamique, les tableaux sont destinés à un accès aléatoire. Pour notre dernière question, votre objectif est de combiner des structures de données pour trouver un palindrome dans une liste de liens. Un palindrome est un mot qui est élevé de la même manière à l'envers, tout comme il s'agit d'un sport comme une voiture de course. Si vous retournez une voiture de course, vous aurez toujours une voiture de course. Ici, votre mot sera représenté sous forme de liste de liens. Ici, nous avons un lien qui contient r, et qui pointe vers le lien suivant qui contient a, pointe vers le lien suivant qui a c, puis pointe vers e, pointe vers c, pointe vers a, ainsi de suite et ainsi de suite. Notre liste de liens représente le mot « voiture de course ». Nous voulons vérifier si cette liste liée est un palindrome. Déterminez quelles autres structures de données que vous pouvez utiliser pour voir également dans cette liste de liens sont un palindrome. Mettez la vidéo en pause ici et voyez si vous pouvez la comprendre. La solution conceptuelle à ce défi assez complexe est que vous voulez à la fois une pile et une file d'attente. Au fur et à mesure que vous progressez et parcourez cette liste liée, vous ajoutez des éléments à la pile et à la file d'attente. Ensuite, une fois que vous avez terminé de gérer l'ensemble de la liste des liens, il vous suffit de faire apparaître une barre oblique, de la retirer de chaque file d'attente d'empilage, puis de vérifier si chacune d'entre elles est égale. C'est génial parce que la pile s'efface à la fin, la file d'attente supprimée dès le début donc vous vous déplacez le long de la chaîne en marche arrière et en avant même temps en suppression de la pile et de la file d'attente. C'est parfait pour nous car dans un palindrome, une façon de vérifier s'il s'agit d'un palindrome est de vérifier si le premier personnage est vous êtes le dernier. Au deuxième, vous passez à l' avant-dernier et ainsi de suite. En le retirant de la pile et de la file d'attente, vous obtenez cela. Faisons une pause ici. Voyons voir, c'est l'algorithme. Quelle est la complexité de l'exécution et de la mémoire ? Voici la réponse. En termes de complexité d'exécution et de mémoire, nous avons une complexité linéaire. Car la complexité de la mémoire est linéaire parce que nous stockons une pile et une file d'attente chacune peut avoir une longueur maximale de n, et nous avons également complexité de calcul linéaire parce que nous itérons au-dessus de chacune de ces lettres. En fait, nous itérons deux fois, mais peu importe, c'est o de n. Maintenant que nous connaissons l' algorithme et que nous connaissons sa complexité, essayons de le coder. Mettez la vidéo en pause ici et essayez de la coder. Passons maintenant à la solution. Nous allons commencer par initialiser à la fois la pile et une file d'attente. Maintenant que nous avons ces deux structures de données, parcourons la liste des liens, comme nous l'avons dit, et pour chaque lien, nous allons l' ajouter à ces deux structures de données. Ici, je vais ajouter à la pile. Je vais pousser la pile, puis je vais également faire la queue dans la file d'attente. Ensuite, je passerai au lien suivant. Comme je l'ai déjà dit, ce code de traversée est à peu près toujours le même. Maintenant que cela est terminé, passons en revue ces deux structures de données, la pile et la file d'attente, et nous assurons que pour chaque élément que nous supprimons, elles sont exactement les mêmes. Tant qu'il y a quelque chose dans la pile, sortez de la pile et retirez-la de la file d'attente. Tant qu'ils correspondent, nous sommes prêts à partir. S'ils ne correspondent à aucun moment, nous renvoyons faux. Si rien ne renvoie faux, tout le match et nous pouvons retourner vrai. C'est ça Allons-y maintenant et évaluons cela. le bouton vert Exécuter tout en haut et vérifiez que tous vos tests sont réussis. Ici, nous pouvons voir que notre fonction est palindrome. Le lien ne se trouve nulle part dans la liste des échecs. Nous avons réussi ce test. Ces trois fonctions restantes sont des fonctions bonus. J'ai également inclus des solutions complètes pour eux et des explications dans le code, afin que vous puissiez également les essayer à votre rythme. Si vous avez des questions, n'hésitez pas à les poster dans la section discussion. C'est tout pour cette leçon. Accédez aux diapositives, au code complet et à la nature des solutions sur le site Web du cours. C'est tout pour les listes, agisse de tableaux ou de listes liées. 9. Mappages : Hashmaps: Dans cette leçon, nous allons présenter une structure de données pour les mappages. Un mappage est ce à quoi il ressemble, un mappage d'un élément à un autre. Ici, nous associons le chat au numéro cinq. Dans ce cas, supposons que nous cartographions l'animal en fonction de son âge. animal est ce que nous appelons la clé de la cartographie, et l'âge est ce que nous appelons la valeur de la cartographie. Nous pouvons également avoir des paires de valeurs clés supplémentaires dans le mappage. Notez que ce mappage n' a aucun sens de l'ordre, chaque paire clé-valeur étant complètement séparée l'une de l'autre. La structure de données qui stocke ce mappage est appelée HashMap. Nous expliquerons comment fonctionne une HashMap, discuterons de ses avantages et de ses inconvénients, puis discuterons brièvement d'un concept de bonus. Voici pourquoi cette structure de données est appelée carte de hachage. À la base, une HashMap utilise une fonction appelée fonction de hachage. Cette fonction de hachage prend une valeur de longueur arbitraire, comme cat, puis transforme cette entrée pour produire une sortie de taille fixe, comme deux. Cette fonction de hachage est importante, et donc en ce qui concerne cette sortie, voyons comment les deux sont utilisées. Supposons que nous souhaitions insérer des clés et des valeurs dans une table de hachage. Sur la droite, nous avons une table de hachage où zéro est l'adresse mémoire du premier slot, l' un est l'adresse mémoire du second slot, et ainsi de suite. Nous voulons mapper la clé cat à la valeur cinq, pour ce faire, nous allons hacher la valeur cat. Cela nous donne l'adresse mémoire 2, donc dans la position deux, placez la valeur cinq. Nous allons répéter cela pour plus de données, pour mapper le chien à trois, le hachage. Cela nous donne l'adresse mémoire 3, donc en position trois, placez la valeur trois. Nous répétons cela une fois de plus, pour faire correspondre le cochon à quatre, le cochon à hacher. Cela nous donne l'adresse mémoire zéro, donc en position zéro, placez la valeur quatre. Ce processus prend juste une constante ou O d' une fois pour chaque paire clé-valeur que nous insérons. Pour supprimer de la HashMap, nous suivons des étapes similaires. Pour supprimer cat de la HashMap, commencez par hacher cat pour en obtenir deux, puis à la position deux, supprimez la valeur. Cette opération est également constante ou O d'une seule fois. Pour résumer, l'insertion et la suppression d' une HashMap se font à la fois. Très vite. Disons que nous voulons maintenant rechercher dans la HashMap, dont la valeur correspond à cat. Presque le même processus, hacher le chat pour obtenir son adresse mémoire, qui est deux. Ensuite, à la position deux, saisissez la valeur cinq et renvoyez-la. Par conséquent, nous disons que la recherche d'une HashMap prend la constante O, encore une fois O d'une fois. Pour résumer, la recherche dans une HashMap prend la constante O d'une seule fois. Pour une HashMap, la recherche et la récupération sont les mêmes, nous évitons donc d'analyser la récupération séparément. Nous allons maintenant comprendre les avantages et les inconvénients de ces HashMaps. En résumé, les HashMaps ont des temps d'exécution très impressionnants, temps, des modifications et un accès constants . En raison du fonctionnement des HashMaps, elles sont idéales pour toutes les données avec des identifiants uniques. Par définition, les HashMaps ne sont pas conçues pour les données de commande. Comme nous l'avons déjà dit, chacune de ces paires de valeurs clés est complètement distincte. n'y a aucun sens de l'ordre, il n'y a aucune relation entre des paires de valeurs clés distinctes. Nous avons déjà discuté des deux premières sections, ce qu'est une HashMap et de quoi elle est idéale. Nous discuterons de la section bonus après avoir terminé le contenu principal. Pour obtenir une copie de ces diapositives et d'autres ressources, n'oubliez pas de consulter le site Web du cours. Ceci conclut notre discussion principale sur HashMaps. Si vous êtes satisfait de ce niveau de détail, n'hésitez pas à passer à la prochaine leçon avec HashMap practice. Sinon, parlons maintenant de la section bonus. En particulier, nous avons discuté d'une mise en garde pour les HashMaps appelée collisions de hachage. Nous avons déjà dit que les HashMaps sont des cartes temps constant pour la modification et l'accès. Cependant, cela n'est pas toujours vrai. temps d'exécution dépend en fait de la façon dont un HashMap a été implémenté et voici pourquoi. Parfois, ce phénomène , mentionné précédemment, appelé collision de hachage, se produit. Par exemple, supposons que nous souhaitions insérer deux paires de valeurs clés, des cartes pour chats sur cinq et des cartes pour chiens sur trois. Comme avant, nous hachons le chat pour en avoir deux. En position deux, nous plaçons ensuite la valeur cinq, comme avant. Maintenant, pour insérer notre deuxième paire clé-valeur, nous avons un hachage pour en obtenir deux, à la position deux, nous avons maintenant un problème. Nous ne pouvons pas remplacer les données existantes, nous avons donc deux options. La première option est appelée adressage ouvert. Dans l'adressage ouvert, nous trouvons simplement un autre emplacement dans la HashMap, si le prochain emplacement est vide, placez-y votre nouvelle valeur. Une façon de trouver un emplacement vide est de simplement parcourir les emplacements jusqu'à ce que vous en trouviez un vide, et d'y placer votre valeur. Il existe également des stratégies pour trouver des créneaux, dont nous ne parlerons pas ici. une autre technique complètement différente pour chaînage est une autre technique complètement différente pour gérer les collisions de hachage. Dans cette technique, nous traitons chaque emplacement comme une structure de données à part entière. Par exemple, nous pouvons traiter chaque emplacement comme une liste liée, puis pour l' insérer en position deux, nous en insérons simplement trois dans la liste liée. Nous pouvons également traiter chaque emplacement comme une HashMap, toute structure de données que nous faisons avec ses propres compromis une fois de plus. En résumé, nous avons défini une collision de hachage et avons également vu deux manières de gérer une collision de hachage. Adressage ouvert ou recherche d'autres emplacements vides à utiliser ou chaînage où nous traitons chaque emplacement comme sa propre structure de données. Cela conclut notre section bonus sur les collisions de hachage N' oubliez pas de consulter notre prochaine leçon pour vous entraîner avec HashMaps. 10. Pratique de cartographie: Bienvenue dans la pratique des structures de données cartographiques. Ici encore, nous allons pratiquer d'autres exercices et passer en revue quelques conseils d'entretien liés à la structure des données cartographiques. En particulier, ces structures de données sont également appelées Hashmaps. Nous utiliserons donc beaucoup ces noms, Hashmaps. Comme avant, accédez à cette URL alvinwan.com/datastructures101/mappings. Cela vous amènera à repl.it. Je sais que nous avons déjà parlé ces instructions à plusieurs reprises. Je vais y revenir une fois de plus au cas où, une fois que vous aurez vu cette page, bifurquer le projet pour obtenir votre propre copie modifiable. Cliquez sur le nom du projet en haut à gauche pour obtenir une liste déroulante. Cliquez sur les points de suspension pour obtenir un autre menu déroulant, puis cliquez sur le bouton « Fourchette ». Ensuite, je suggère de placer votre fenêtre Skillshare et les fenêtres repl.it côte à côte, comme indiqué ici. Vous devriez alors voir quelque chose qui ressemble à ce que vous avez sur le côté droit. Parlons maintenant types d'exercices que vous allez voir. Vous aurez les exercices de mise en œuvre, d'utilisation et de combinaison. Si vous faites défiler l'écran vers le bas, vous verrez que notre tout premier exercice consiste à implémenter une pile. Nous allons le faire en trois étapes, comme nous l'avons fait dans toutes les autres leçons. Nous allons d'abord concevoir l'algorithme sans aucun code. Nous allons signaler la complexité de l' exécution et de la mémoire. Ensuite, nous allons réellement coder l'algorithme. Appliquons ces trois étapes au tout premier algorithme, ou à notre premier exercice ici. Implémentez une pile qui limite toutes les valeurs de la pile à trois occurrences seulement. Si une valeur comportant plus de trois occurrences est poussée, ignorez simplement cette valeur. Donc, dans ce cas précis, nous avons un exemple ici. Nous initialisons d' abord une pile, puis nous poussons la valeur une ou dix fois. Cependant, seules les trois premières valeurs sont réellement ajoutées à la pile. Tout le reste est ignoré. Vous pouvez ensuite pousser d'autres valeurs qu' une et elles seront ajoutées normalement à la pile. Allez-y et essayez ceci. Tout d'abord, concevez l'algorithme qui implémentera réellement cette pile avec une limite. Mettez la vidéo en pause ici et essayez de trouver un algorithme. Voici la solution algorithmiquement. Ce que nous allons faire, c'est d' utiliser d' abord l' implémentation de la pile de base. Vous pouvez donc voir ici que ma classe de pile plafonnée hérite en fait de la classe de pile de base. Sachant cela, nous allons imposer des restrictions quant au moment où vous pouvez réellement pousser vers une pile, et c'est tout. Pour ce faire, nous allons conserver une HashMap, mappant toutes les valeurs à leur nombre dans la pile. Chaque fois que vous appuyez, vous incrémentez cette valeur. Si cette valeur dépasse la limite, nous l'ignorerons simplement, puis pop s' assurera de diminuer ce nombre. En mode push, vous vérifiez le nombre, l' ajoutez s'il est correct, puis vous l'incrémentez. Dans Pop, vous diminuez le décompte. Voilà donc l'algorithme. Passons maintenant à la complexité de l'exécution et de la mémoire. Mettez la vidéo en pause ici et voyez si vous pouvez la comprendre. Pour ce qui est de la complexité d'exécution, elle dépend de la complexité de l'algorithme d'origine. Dans ce cas précis, le push est linéaire et pop est la façon dont nous l'avons implémenté, également linéaire. Les opérations push et pop sont donc toutes deux des opérations linéaires. maintenant à la complexité réelle de la mémoire, quoi cela ressemble-t-il ? Eh bien, nous devons créer une nouvelle valeur ici. Ce n'est pas exactement o de n. Nous avons une valeur ajoutée à la HashMap pour chaque nouvelle valeur, mais ce n'est pas autant que le nombre total de valeurs que nous avons ajoutées. Nous n'avons que le nombre de valeurs uniques dans notre HashMap. Nous devons inventer une nouvelle lettre. Au lieu de o pour n, nous allons dire que c'est o de k par exemple, et nous définirons k comme le nombre de valeurs uniques qui ont été ajoutées à la pile. Si vous aviez réellement cela dans une interview, vous diriez quelque chose comme ça. Nous devons en fait définir une nouvelle variable, k, où k est le nombre de valeurs uniques, et notre algorithme, la complexité de notre mémoire pour notre algorithme est o de. C'est tout pour la complexité. Passons maintenant au code. Alors, mettez la vidéo en pause ici et essayez de coder. Dans le constructeur, nous allons initialiser un nouveau compteur. Depuis les collections, import, default, dict. Il s'agit d'un autre type de dictionnaire. Ce dictionnaire fait que si vous accédez à une clé qui n'a pas de valeur actuelle, il initialisera cette valeur à l'aide de cette fonction. Dans ce cas particulier, pour ce compteur, si nous accédons au compteur 0, 0 n'est actuellement pas une clé valide pour ce dictionnaire, donc il l'initialisera avec cette fonction int. La valeur par défaut de la fonction int est zéro. Par défaut, le compteur automatique de 0 me donnera 0. En fait, le compteur automatique de tout, me donnera également 0. C'est ainsi que fonctionne ce dictionnaire par défaut, et cela simplifiera un peu le code. Maintenant que j'ai ceci, implémentons maintenant la fonction push. Comme nous l' avons déjà dit, la première chose à faire est de vérifier si le nombre actuel est inférieur à la limite. Si c'est en dessous de la limite, alors nous allons continuer. S'il est inférieur à la limite, nous augmenterons le nombre, puis nous le mettrons sur la pile. Dans Pop, tout ce que nous ferons c'est simplement décrémenter le compte. Ici, nous allons d'abord atteindre la valeur. Ici, nous allons sortir de la pile, puis une fois que nous avons créé cette valeur allons décrémenter le nombre de cette valeur, puis nous allons renvoyer la valeur. Voyons maintenant si nos tests Cap Stack sont réussis. Tout en haut, appuyez sur le bouton vert, et voilà, Cap Snack ne figure plus dans la liste des échecs, donc nous avons réussi ce test. Passons à la question suivante. Un conseil est que les Hashmaps sont idéales pour les données avec des identifiants uniques. Dans ce cas précis, nous savons que chaque valeur, ou la prémisse du problème, est que nous contrôlons s'il faut ou non pousser sur la pile en fonction de la valeur. La valeur elle-même est donc l'identifiant unique. Parce que nous avons cet identifiant unique, Hashmaps étaient parfaites pour ce problème. Cependant, les hashmaps sont pires pour les données ordonnées. S'il existe une relation entre vos données, supposons que j'ai une séquence de chiffres, de un à 10, et que j'ai besoin de connaître cet ordre. Ou une autre façon de le dire serait, disons que j'ai 10 valeurs et je les insère dans une structure de données. Si je dois me souvenir de l' ordre dans lequel je l'ai inséré, hashmaps ne sont pas la structure de données à utiliser, car les hashmaps oublient tout l'ordre. Ils ne font que maintenir un mappage des clés aux valeurs. Ils ne se souviennent pas de l'ordre dans lequel vous insérez les clés. C'est donc important. hashmaps sont idéales pour les données avec des identifiants uniques, mais elles ne le sont pas aussi pour les données pour lesquelles l'ordre est important. Pour la question suivante, faites défiler l'écran vers le bas pour voir la question suivante. Renvoie un histogramme de toutes les lettres uniques et de leur nombre d'occurrences. Je suppose que ça aurait dû passer en premier. Il s'agit d'un sous-ensemble du problème précédent. Quoi qu'il en soit, mettez la vidéo en pause ici et voyez si vous pouvez comprendre l'algorithme. La solution conceptuelle est que nous allons initialiser une HashMap en tant que compteur, et chaque fois que nous allons itérer sur la chaîne, et pour chaque nouvelle valeur, nous allons accéder à notre compteur. Si nous avons déjà vu cette valeur, nous allons en ajouter une au décompte. Si nous n'avons jamais vu cette valeur auparavant, nous allons initialiser le nombre à un. Voilà donc l'algorithme. Quelle est la complexité de l'exécution et de la mémoire ? Mettez la vidéo en pause ici. Voici la réponse. La complexité d'exécution est linéaire. Nous devons répéter chaque lettre de la chaîne. n'y a aucun moyen de contourner cela. Le second, la complexité de la mémoire. Encore une fois, nous devons inventer une toute nouvelle variable. Cette variable est le nombre de valeurs uniques, disons k. Cet algorithme est o de k, où k est le nombre de valeurs uniques présentes dans la chaîne. C'est tout pour la série de moissonneuses-batteuses, essayons maintenant de la coder. Mettez la vidéo en pause ici et essayez le code. Passons maintenant à la solution dans le code. Ici, nous allons créer un compteur. Ce compteur va être un dictionnaire. En fait, ce que je vais faire, c'est utiliser le dictionnaire par défaut d'avant. De cette façon, le dictionnaire s'initialise à zéro. Ici, nous aurons des collections, import, defaultdict. Ensuite, ici, pour chaque lettre de la chaîne, nous allons incrémenter le nombre correspondant. Ici, nous allons incrémenter le nombre correspondant et enfin renvoyer le compteur. Maintenant, je veux aussi montrer l'implémentation sans ce defaultdict. Supposons que vous n'ayez pas utilisé le defaultdict. Supposons que vous créiez simplement un dictionnaire normal. Ensuite, nous vérifierons ici si la lettre se trouve dans le comptoir. Si nous avons déjà vu cette lettre auparavant, nous allons simplement l'incrémenter d'une unité. Si nous ne l'avons jamais vu auparavant, nous l'initialiserons à un. contre-lettre est égale à un. Allons-y maintenant et exécutons ceci pour vérifier si unique est maintenant un test de réussite. On y va. Unique a maintenant réussi tous ses tests. Nous avons également terminé cet exercice. Passons maintenant à l'exercice suivant. Un conseil est de vous assurer que votre clé existe bien avant d'y accéder. C'est ce que nous avons fait ici. À la ligne 103, nous avons vérifié si la lettre se trouvait dans le comptoir. En d'autres termes, si nous avions déjà vu cette lettre auparavant et qu'il y avait déjà une clé valide dans notre cartographie. Sachant cela, passons donc à la question qui suit. Utiliser notre structure de données pour trouver la valeur la plus fréquente dans une liste de nombres entiers. J'ai spécifié des nombres entiers pour rendre cela un peu plus simple. Mais il y a plusieurs questions que vous aimeriez poser à votre intervieweur. La première question serait s'ils n'avaient pas spécifié les nombres entiers, ils ne le feraient probablement pas. Ils diraient très probablement des chiffres. Ensuite, vous devriez vous demander s'il peut y avoir des valeurs négatives ? Peut-il y avoir des valeurs décimales ? Quelle est la gamme ? Quel est l'ensemble des valeurs possibles que je pourrais voir ? La deuxième question que vous voudriez vous poser est la suivante : et s'il y a égalité ? Que la question elle-même n'est pas bien définie en cas d'égalité. Maintenant, en cas d'égalité dans cette description du problème, signalez n'importe lequel des nombres à égalité avec la fréquence la plus élevée. C'est généralement ce qui se passe. Mais ce sont de bonnes questions à poser et cela vous donne quelques points intéressants dans votre entretien. Dans cette question particulière, nous avons une liste de chiffres, et je veux savoir quel est le plus fréquent, mettez la vidéo en pause ici et voyez si vous pouvez comprendre l'algorithme. Voici la solution. Nous allons faire quelque chose de très similaire à la précédente. Nous allons utiliser une HashMap pour stocker les nombres pour chaque valeur de notre liste. Une fois que vous aurez obtenu ce compteur, utiliserons le compteur pour déterminer quel était le meilleur. Ce serait une façon de procéder. Une autre façon de procéder qui ne nécessite pas deux passes de données serait de conserver, au fur et à mesure que vous ajoutez des données au compteur, une variable qui représente la valeur la plus fréquente. Si vous voyez une valeur qui comporte soudainement plus d'instances, remplacez cette variable. Vous le verrez en action dans une seconde. Mais conceptuellement, l'idée principale est de conserver un compteur de toutes les valeurs uniques , puis d'utiliser ce compteur. Maintenant que nous connaissons l'algorithme, mettez la vidéo en pause ici et voyez si vous pouvez déterminer la complexité de la durée d'exécution et de la mémoire. Voici la réponse. Comme auparavant, nous avons exactement la même complexité de mémoire d'exécution que les fonctions précédentes. La complexité au moment de l'exécution sera linéaire. Vous devez parcourir chaque élément de la liste. n'y a aucun moyen de contourner cela. Le second est O de k, où k est le nombre de valeurs uniques. Je suppose que c'est en train de devenir un motif maintenant. Mais au moins pour ces exercices, O de k est la bonne fois, alors gardez cela à l'esprit. nombre de valeurs uniques est linéaire. Maintenant que nous avons abordé la complexité, nous avons abordé l'algorithme, arrêtez la vidéo ici et essayez le code. Voici la solution. Écrivons ceci maintenant. Nous allons commencer par counter et counter sera un dictionnaire vide. La plus grande valeur sera de n'en avoir aucune, disons. Pour la valeur en nombres, nous allons vérifier si la valeur se trouve dans le compteur. Si nous avons déjà vu cette valeur, je vais en fait la modifier un peu. Si la valeur n'est pas dans le compteur, nous l' initialiserons à zéro. Quelle que soit sa valeur , nous l'incrémenterons d'une unité. Si le compteur est supérieur à la valeur la plus élevée, donc si le nombre actuel est supérieur au nombre le plus élevé, nous réaffecterons, puis nous renverrons la valeur la plus élevée. Avant d'exécuter cette fonction, vous devez garder à l'esprit une chose qui est, eh bien, l' une des tactiques que j' aborderai dans un prochain cours est que vous devez toujours exécuter virtuellement votre code. Ce que je veux dire par là, c'est simplement exécuter le code dans votre tête comme si vous étiez l'interprète. Si vous détectez des bogues avant d'exécuter le code, c'est généralement un autre point limite pour vous. Dans ce cas précis, nous verrions en fait une erreur ici à cause de counter greatest. meilleur ici est nul et il n'en existe pas encore dans le comptoir. Cela revient à notre conseil précédent, assurez-vous toujours que la clé existe avant d'essayer d'y accéder. Dans ce cas précis, je vais ajouter la touche Aucun ici, et je vais la mettre sur négative. De cette façon, toutes les autres valeurs avec un nombre seront supérieures à celle-ci. Dans la toute première itération, remplacez la valeur la plus élevée par la valeur actuelle. C'est tout pour cette fonction. Essayons maintenant d'exécuter les tests et de nous assurer que les tests les plus fréquents n' apparaissent plus comme un échec. Cliquez sur le bouton vert « Exécuter » tout en haut. Tu y vas. Vous pouvez maintenant constater que le test le plus fréquent n'est plus un échec. Ici, nous voulons considérer les entrées vides. Il y a un cas où vous pourriez avoir quelque chose d'étrange à se produire si vous transmettiez une liste vide à la liste la plus fréquente, alors vous n' en récupéreriez simplement aucune, ce qui est une valeur par défaut raisonnable. Mais vous devez simplement vous assurer que votre fonction ne se brise pas si vous obtenez une entrée vide. Dans ce cas, notre fonction ne s'interrompt pas. Elle n'en renvoie aucune. Donc, tant que nous déclarons que la fonction ne renverra aucune valeur en cas d'entrée vide, alors c'est parfaitement valide. Pour notre prochaine question. Celui-ci est assez difficile sur le plan conceptuel. Nous allons utiliser une structure de données ou n'importe quelle structure de données pour trier un ensemble de voyages. Un certain nombre d'étapes sont formatées en tant que source et destination. Vous pouvez les considérer comme des villes d'origine et de destination. Une fois que nous l'avons obtenu, nous voulons calculer le chemin complet. Nous voulons trouver la position de départ réelle et la position finale réelle ou ultime. Vous pouvez supposer pour l' instant qu'il n'y a qu'un seul chemin et qu' il y en a un qui est complet. Cela signifie qu' il n'y a pas de lacunes. Ne vous retrouvez jamais à une position aléatoire au milieu avec un tas d'étapes indépendantes et il n'y a pas de cycles. Tu ne passeras jamais de un à deux à un. Si vous passez de un à deux, vous passerez toujours à trois, quatre, ainsi de suite, ainsi de suite. Votre objectif est d'imprimer la séquence des étapes dans ordre de la première à la dernière. Ici, nous avons un tas d'étapes. Nous sommes passés de trois à deux, de un à trois et de deux à cinq. Votre objectif est de savoir quelle est la bonne séquence d'étapes. Ici, la séquence correcte est de un à trois, puis de trois à deux, puis de deux à cinq. Mettez la vidéo en pause ici, découvrez les structures de données que vous souhaitez utiliser et comment vous les utiliseriez. Voici la solution. Conceptuellement, nous allons d'abord découvrir quelle est la position de départ ultime. Pour ce faire, nous allons créer un ensemble de Hashmaps. Ces Hashmaps seront mappés de la destination à la source. Ensuite, nous partirons de n'importe quelle destination arbitraire. À partir de cette destination, nous allons vérifier si la source se trouve dans la HashMap ? La source actuelle est-elle une autre destination des étapes ? Si c'est le cas, nous passons à la destination et à la source de ces étapes , et vous continuez à le faire. Supposons, par exemple, que nous partons de deux, puis que nous nous demandions : y a-t-il trois dans notre cartographie ? C'est vrai, il y en a trois dans notre cartographie. Cherchons la source correspondante. Premièrement, est-ce qu'il y en a un dans notre cartographie ? Non, cela ne figure pas dans notre cartographie. Cela signifie donc que l'une d'elles est la position de départ ultime. C'est ce que nous allons faire. Nous allons créer une cartographie de la destination à la source. Ensuite, nous allons continuer à parcourir jusqu'à ce que nous arrivions à la source ultime. Une fois que vous y êtes, c'est la première étape. Nous avons obtenu la source ultime. Nous devons maintenant imprimer cette série d'étapes. Nous devons revenir en arrière, partir de la source et continuer à traverser. Nous allons commencer par un, nous allons passer à trois, puis nous en chercherons trois. On en voit trois, puis on passe à deux. On en cherche deux, il y en a deux ici. Ensuite, nous continuons à le faire. Vous continuez à traverser vers l'avant. Vous avez besoin d'un ensemble de Hashmaps qui vous donnent la direction inverse. Ensuite, vous devez configurer HashMap qui vous donne la direction à suivre. que nous allons faire. Je vais créer deux Hashmaps. Un HashMap relie toujours la destination à la source. On fait toujours des liens de la source à la destination, c'est donc notre algorithme. Maintenant, quelle est la complexité de l'exécution et de la mémoire ? Mettez la vidéo en pause ici. Voici la réponse. La complexité de notre mémoire est linéaire en termes de nombre d'étapes, car pour chaque étape, nous l'ajoutons à ces deux Hashmaps ou à ces deux dictionnaires. maintenant à la complexité de notre environnement d'exécution. Le nombre d'étapes est linéaire car nous devons accéder à chacune de ces étapes au moins une fois, et heureusement pour nous une seule fois. Sachant cela, écrivons maintenant la fonction, le code. Mettez la vidéo en pause ici et essayez le code. Passons maintenant à la solution. Ici, nous allons initialiser deux Hashmaps ou deux dictionnaires. L'un va aller en avant, l'autre va être en arrière. Pour chaque paire de source et de destination de nos étapes, nous allons renseigner les deux. Le mappage prospectif ira de la source à la destination. Le mappage rétrograde ira de la destination à la source. Maintenant que nous avons rempli ces deux mappages, passons de n'importe quelle source arbitraire à la source ultime. Bien que la source soit en arrière, je suppose que c'est un peu flou, mais ici je vais juste le préciser. Ici, la source est égale à la première étape, puis ce sera la source de la première étape. Tant que la source est à l'envers, nous continuerons à la parcourir. Une fois cette boucle terminée, source ne figure plus dans le mappage rétrograde, ce qui signifie que la source est la source ultime, le premier endroit où nous sommes allés. Ensuite, tant que la source se trouve dans le dictionnaire prospectif ou dans le mappage prospectif, nous l'imprimerons. Ici, nous allons utiliser les chaînes f en Python. Vous pouvez l'imprimer comme vous le souhaitez , puis nous allons parcourir cette voie. Tant que notre source se trouve dans le mappage prospectif, nous accèderons à cet élément dans le mappage prospectif pour sa destination. C'est à peu près ça. Exécutons maintenant cette fonction et veillons à ce que nous la transmettions, obtenons le chemin à partir des tests. Voilà, nous n' avons qu'une seule série de tests d' échec qui concernent une autre fonction, donc nous avons réussi cet exercice. Ne parlons pas de cette question difficile. Cette question est également assez difficile, donc nous allons en parler uniquement de manière algorithmique, nous n'allons pas vraiment la coder. Encore une fois, j'ai écrit des solutions pour vous, mais nous ne parlerons tout simplement pas du code ici. J'ai annoté chaque ligne des solutions afin que vous puissiez les parcourir et les comprendre partie la plus importante ici est l'algorithme. Pour résoudre ce problème, nous allons créer un dictionnaire d' une taille maximale qui fonctionne comme l'argent liquide utilisé le moins récemment. Dans ce dictionnaire, chaque fois que vous insérez, mettez à jour ou accédez à une clé, mettez à jour ou accédez à une clé, considérée comme utilisant cette clé, et si le dictionnaire contient plus de clés que la taille maximale, vous supprimerez la clé la moins récemment clé utilisée. Voyons un exemple de cela. Disons que j'ai ce nouveau dictionnaire et j'insère la valeur 1 avec la clé a, donc nous allons simplement regarder les clés ici, les valeurs n'ont pas trop d' importance. Nous avons inséré une valeur pour la clé a, puis une valeur pour la clé b. À ce stade, b est la dernière valeur utilisée et 1 est la valeur la moins récemment utilisée. Cependant, ici, j'accède à a. Maintenant, a devient la valeur la plus récemment utilisée , nous l'avons échangée. L'une correspond à a, donc a est la plus récemment utilisée et l'autre valeur est la moins récemment utilisée. Maintenant, nous attribuons une nouvelle valeur à la touche c et vous remarquerez qu'à ce stade, b était la valeur la moins récemment utilisée ici, donc b est supprimé et il ne nous reste plus que a et c. Dans ce dictionnaire en particulier, la taille maximale était de deux. C'est ainsi que nous avons vu l'une des clés tomber. oubliez pas que chaque fois que vous accédez à, mettez à jour ou insérez une valeur pour une clé qui compte comme accédant ou utilisant cette valeur, et chaque fois que vous insérez si vous dépassez la taille maximale, vous perdez le moins récemment valeur utilisée. Sachant tout cela, réfléchissons maintenant à la manière de le concevoir de manière algorithmique. Mettez la vidéo en pause ici et voyez si vous pouvez trouver un algorithme. Voici la solution. Pour réellement implémenter ce cache, nous allons conserver une liste à double lien. Avant de parler d'une liste de liens, une liste de liens conserve un lien vers le lien suivant Vous devriez donc ressembler à ceci. Vous en auriez un qui renvoie vers deux, des liens vers trois. Cependant, une liste à double lien inclut en fait les deux directions, trois sait que sa valeur précédente est deux, deux savent que sa valeur précédente est une. La raison pour laquelle vous souhaitez cette liste à double lien est que nous voulons que la liste liée garde une trace de la commande entre toutes nos données et cette commande nous indiquera que les plus récemment utilisées et les valeurs les moins récemment utilisées sont. Heureusement, avec une liste de liens, il est très facile d' insérer une valeur et de supprimer une valeur à la fois. Ce sont deux opérations à temps constant. Notez que cela n'est pas vrai pour un tableau. Dans un tableau, si vous voulez vous déplacer, disons trois. Disons que nous l'avons eu. Disons que nous avions 1, 2, 3, 4, 5 et disons que cinq est maintenant la valeur la plus récemment utilisée. Votre nouvelle liste devrait être 5, 1, 2, 3, 4. Avec une liste à liens doubles, il s'agit d'une opération à temps constant, vous suffit de réattribuer les connexions comme nous en avons parlé précédemment. Cependant, pour un tableau, vous devez copier la position de 1-2, 2-3, 3-4, 4-5, puis en copier cinq au début. Vous devrez effectuer n copies, n opérations pour remanier cette liste. Cependant, avec une liste à liens doubles, vous n'avez rien à faire de tout cela. C'est une opération à temps constant. C'est pourquoi nous voulons une liste à liens doubles à combiner avec notre cartographie ou une HashMap pour implémenter ce cache le moins récemment utilisé. Sachant que nous voulons une liste à liens doubles, comment allons-nous réellement l'utiliser ? Parlons des deux fonctions dont nous avons réellement besoin. Nous avons deux fonctions différentes. Je ne vais pas vraiment étoffer complètement ces fonctions, mais je vais ajouter un pseudo code ici juste pour que vous sachiez à quoi ressemblerait la structure générale du code. Ici, nous aurions la possibilité d'obtenir un élément et nous aurions également une autre fonction qui nous permettrait de définir un élément. L'idée de base ici est que sous ces deux fonctions, nous mettrions à jour la clé, nous dirions quelque chose comme créer la clé la plus récente », puis la même chose ici. Nous allons également créer la clé la plus récente, et c'est à peu près tout pour la logique de haut niveau. La plupart des détails se seraient produits ici. Dans la fonction « Créer le plus récent », vous feriez toutes les réaffectations nécessaires à la fois pour supprimer un élément de la liste liée , puis pour le réinsérer au tout début, et est-ce que c'est. C'est la solution conceptuelle à ce problème. Vous utiliseriez une liste à liens doubles et vous utiliserez également une carte. Cela semble assez complexe, je ne vais pas coder, moins pas ici dans la leçon. J'ai déjà écrit les solutions et les solutions seront mises à votre disposition avec du code entièrement annoté. Cependant, la partie la plus importante de cette question consistait à utiliser la liste à liens doubles. Il y aura de nombreuses questions de ce type dans vos entretiens où vous devrez trouver une nouvelle combinaison de différentes structures de données afin d'atteindre vos objectifs. Dans ce cas précis, nous voulions un cache utilisé au moins récemment, et nous voulons qu'il soit très efficace L'utilisation de cette liste à liens doubles nous permet de garder cette fonction efficace. Cela nous amène à la deuxième partie de la question. Quelle est la complexité de l'exécution et de la mémoire de notre algorithme ? En particulier, quel est le temps d'exécution de votre mémoire, la complexité de l' insertion et de l' accès réel à une valeur ? Mettez la vidéo en pause ici, et voici la solution. Obtenir la valeur est assez simple. Obtenir la valeur elle-même, accéder à une valeur dans une HashMap, c'est tout un, c'est du temps constant. Mais la vraie question est combien de temps faut-il pour mettre à jour la valeur la plus récente ? Parce que cela implique de supprimer et de réinsérer dans une liste à liens doubles. Heureusement, l'insertion et la suppression d'une liste de liens se font en permanence. étant, nous savons que cet algorithme, cette structure de données est un temps d' accès constant. C'est génial Nous avons maintenu l'efficacité d' une HashMap et maintenant, qu'en est-il de l'affectation ? Qu'est-ce qui met à jour cette HashMap ? Eh bien, heureusement, c'est aussi un temps constant. Il est temps de mettre à jour une HashMap elle-même et encore, faire en sorte que cette paire clé/valeur soit la plus récente. Cette opération elle-même est à nouveau constante, comme nous en avons parlé plus tôt. Parce que cette opération à temps constant, créer quelque chose de plus récent consiste simplement à l'insérer et à le supprimer d'une liste à liens doubles. Tout cela pour dire que nous avons trouvé une belle combinaison de structures de données pour maintenir le temps, l' insertion et l'accès constants à une structure de données. C'est la solution la plus efficace que vous puissiez obtenir. Je suppose que le point à retenir ici est que connaître les bonnes structures de données peut vraiment signifier une différence d'ordre de grandeur, une différence d'ordre de croissance entre une implémentation efficace et inefficace. Dans ce cas, l'utilisation de listes à liens doubles est ce qui nous a efficacité et c'est une compétence utile pour les entretiens, peut-être moins pour le travail, mais si vous aviez un système de production massif, si vous aviez un application critique qui utilisait des structures de données inefficaces, vous auriez alors la possibilité de vous auriez alors la possibilité de créer un impact commercial massif. C'est tout pour cet exercice. Encore une fois, pour accéder à toutes ces diapositives grossières à toutes les solutions, assurez-vous d'accéder au site Web du cours. Enfin, cela conclut la leçon pratique sur les mappages de barres obliques de HashMap . 11. Arbres : largeur vs. profondeur: Dans cette leçon, nous allons discuter manière de stocker des données de manière hiérarchique. Structure de données appelée arbre. Nous expliquerons comment fonctionne un arbre, comment traverser un arbre, comment organiser un arbre, ce que signifie O (logn) time. Enfin, nous aborderons les avantages et les inconvénients de cette nouvelle structure de données. Commençons par ce qu'est un arbre. Un arbre est constitué d'un nœud racine. Ce nœud racine possède deux nœuds enfants. Chacun de ces nœuds possède alors deux autres nœuds enfants chacun. Cette structure est ce que nous appelons un arbre. En fait, comme chaque nœud a deux enfants, nous l'appelons un arbre binaire. Supposons que vous souhaitiez rechercher une valeur ou que nous souhaitions modifier cet arbre, nous devons savoir comment traverser un arbre. Voici deux manières différentes d'y parvenir. La première méthode s'appelle Breadth First Traversal, ou BFS en abrégé. Dans BFS, nous parcourons les nœuds gauche à droite niveau par niveau. On accède d'abord à trois. Nous avons terminé le premier niveau, alors passons au niveau suivant. Ensuite, nous accédons à 7, puis à 2, nous avons terminé le deuxième niveau. Passons donc au dernier niveau. Nous accédons à zéro, un, neuf et huit. Nous avons terminé le dernier niveau, donc nous en avons terminé avec BFS. Notre deuxième méthode pour parcourir cet arbre s' appelle Depth-First Traversal, ou DFS en abrégé. Ici, nous accédons à partir du nœud racine, trois, nous accédons également à sept. Nous continuons à traverser plus profondément, nous accédons donc à deux. Maintenant que nous sommes dans une impasse, nous revenons à sept et explorons le plus profondément possible. Nous accédons donc à un. Encore une fois, nous sommes dans une impasse. Nous revenons donc à sept, revenons à trois, et encore une fois, nous explorons le plus profondément possible. On accède à deux puis à neuf. Nous sommes dans une impasse. Revenez donc à deux et accédez enfin à huit. Et ce sont les deux manières de traverser un arbre, par la largeur ou par la profondeur. Nous allons maintenant expliquer une façon d'organiser les données dans un arbre. C'est ce que l'on appelle l'arbre de recherche binaire. Remarquez que nous avons réorganisé les valeurs. En particulier, nous y avons fait en sorte que l'enfant gauche soit toujours inférieur au parent. Par exemple, trois ici est inférieur à cinq et deux est inférieur à trois. Nous avons également organisé ces valeurs de manière à ce que le bon enfant soit toujours supérieur au parent. Par exemple, huit est supérieur à cinq. Ainsi, l'enfant droit est toujours plus grand et l' enfant gauche est toujours moins. Cette structure ordonnée nous permet de gérer les données de manière très efficace. Supposons que nous souhaitions insérer des données dans l'arbre. Ici, nous voulons en insérer six. Pour ce faire, commencez par le nœud racine 5. À partir de là, nous chercherons de manière itérative une maison pour six personnes. Puisque six est supérieur à cinq, nous savons que six doit appartenir à la droite. Nous avons maintenant la valeur huit. Comme six vaut moins de huit, nous savons que six doivent appartenir à la gauche. n'y a pas de nœud ici, donc c'est maintenant la maison de six. Ceci conclut l'algorithme d'insertion. Supposons que la profondeur de l'arbre soit d, alors cet algorithme prend jusqu'à d opérations. Par conséquent, l'insertion prend beaucoup de temps pour s'exécuter. En résumé, l'insertion prend du temps à O (d). Voyons maintenant comment fonctionne la suppression. Supposons que nous supprimions six affichés en rouge. Eh bien, c'est assez simple. Supprimez simplement ce nœud et le pointeur de son parent. Cependant, supposons que nous avons supprimé du milieu de l'arbre. En particulier, nous voulons en supprimer cinq. Essayons ce que nous avons fait la dernière fois, il suffit d'en perdre cinq. Cependant, il y a maintenant un trou dans l'arbre. Nous pouvons utiliser l'un ou l'autre des enfants pour combler le vide, trois ou huit. Ici, nous allons utiliser le huit bon enfant. Alors, augmentez de huit. Cependant, il y a maintenant un écart où il y en avait huit auparavant. Par souci de cohérence, nous utiliserons le bon enfant de huit, neuf. Encore une fois, passez à neuf heures. Maintenant, il y en a un tout là où il y en avait neuf , mais ce n'est pas grave. n'y a plus d'enfants. Nous pouvons donc simplement supprimer le pointeur supplémentaire. Tout comme avec l'algorithme précédent. Cet algorithme prend jusqu'à d opérations. La suppression prend donc beaucoup de temps. Résumer l'insertion et la suppression d' un arbre de recherche binaire prennent du temps. Notre objectif est de rechercher la valeur six. Nous partons du nœud racine cinq, comme pour l'insertion, nous comparons la valeur six souhaitée avec le nœud cinq actuel. Six est supérieur à cinq, donc on va à droite. Nous accédons maintenant à huit. On compare, six c'est moins que huit, donc on va à gauche. Maintenant, nous accédons à six, c'est la valeur que nous recherchons. Nous avons donc terminé la recherche. Cet algorithme peut prendre jusqu'à d opérations. La recherche est donc O of d. Pour résumer, un arbre de recherche binaire propose la modification et l'accès à O of d. Notez que dans un arbre, il n'est pas possible de récupérer directement le huitième nœud, car il n'y a pas d' ordre global des nœuds et vous ne savez pas où se trouvent les nœuds en mémoire. Par conséquent, il n'y a pas d'analyse au moment de l'exécution du fetch. Ceci conclut notre analyse des arbres. Mais il nous reste encore une chose à faire. Nous aimerions traduire ces durées d'exécution. Tous nos temps d'exécution sont exprimés en fonction de la profondeur de l'arbre ou d. Visualisés, voici un arbre et voici la profondeur de l'arbre. Dans ce cas, nous avons une profondeur de quatre. Nous aimerions exprimer ces temps d'exécution en termes de n, le nombre de nœuds, dans ce cas il y a 15 nœuds. Cela est dû au fait que les temps d'exécution de toutes nos structures de données précédentes étaient exprimés en termes de n, le nombre d'éléments. Par conséquent, nous devons également exprimer nos nouveaux temps d'exécution en n pour nous assurer que ces temps d'exécution sont comparables. Voici le même arbre. Essayons de comprendre la relation entre d et n. Considérons la première couche. Il s'agit de la profondeur 1 avec un nœud. Considérez les deux premières couches. Il s'agit de la profondeur 2 avec trois nœuds. Les trois premières couches, c'est la profondeur 3 avec sept nœuds. Prenez en compte toutes les couches. Il s'agit de la profondeur 4 avec 15 nœuds. Il peut être difficile de remarquer un schéma. Donc, au lieu de compter le nombre de nœuds, je vais compter le nombre de nœuds plus un. Maintenant, si vous regardez les chiffres en rouge, voyez-vous un schéma ? Comme vous l'avez peut-être remarqué, le nombre de rouges, nombre de nœuds double à peu près. Par conséquent, nous pouvons affirmer que n est approximativement égal à deux de la puissance de d. Nous avons maintenant une relation mathématique entre d et n. Puisque nous voulons intégrer d à nos complexités d'exécution, résolvons pour d. Pour résoudre d, nous allons d'abord réécrire l'équation, puis appliquer des logarithmes aux deux côtés. N'oubliez pas qu'avec les logs, nous pouvons déplacer l'exposant d en dehors du log en tant que coefficient. Ensuite, nous ignorons simplement le logarithme deux constant. Maintenant, nous obtenons que le log de n est approximativement d. Nous pouvons maintenant le brancher. Auparavant, ces temps d'exécution étaient exprimés en termes de d. Brancher d est égal à logn. Nous obtenons maintenant un O de connexion pour toutes les runtimes de modification et d'accès. À l'aide de cette analyse, nous allons maintenant discuter des avantages et des inconvénients des arbres de recherche binaires. Les arbres de recherche binaires de certains ont des temps d'exécution impressionnants, juste O (logn). En pratique, O de log n est très proche de o d' un temps constant. De par leur conception, les arbres de recherche binaires sont idéaux pour les séquences aléatoires. Plus l' étalement est uniforme, mieux c'est. Cependant, les arbres de recherche binaires sont les pires pour les données séquentielles, et voici pourquoi. Disons que j'ai une séquence de nombres de 0 à 10. Nous créons d'abord le nœud racine 0, puis nous avons répondu à un, puis à deux, puis à trois, puis à quatre, puis à cinq. La liste est longue, et comme vous pouvez le voir, nous avons essentiellement une ligne droite au lieu d'un arbre de recherche binaire plein. Cela signifie que la profondeur n'est plus logarithmique, mais exactement égale au nombre de nœuds. Cela signifie que tous nos algorithmes prennent désormais O de n ou temps linéaire. En résumé, les arbres de recherche binaires sont vraiment inefficaces pour les données séquentielles. En résumé, nous avons discuté de ce qu'est un arbre, traversée en largeur par rapport à la profondeur d'abord, ce qu'est un arbre de recherche binaire, la signification du O du log n time et de certains avantages et inconvénients des arbres de recherche binaires. Pour obtenir une copie de ces diapositives et ressources, n'oubliez pas de consulter le site Web du cours. Voyons maintenant ces structures de données en action. Dans la leçon suivante, nous nous entraînerons à utiliser et à implémenter ces structures de données, en abordant les deux objectifs d'apprentissage de ce cours. 12. La pratique des arbres: Bienvenue à la dernière leçon d'entraînement de ce cours. Dans cette leçon, nous allons nous entraîner avec les arbres, en particulier avec une recherche en largeur plutôt qu'en profondeur. Allons-y et commençons ici. Comme auparavant, rendez-vous sur alvinwan.com/datastructures101/trees. Sur ce lien, vous verrez quelque chose comme ça. Transférez le projet pour obtenir votre propre copie, cliquez sur le nom du projet, cliquez sur les points de suspension et cliquez sur la fourchette. Je suggère de placer votre Skillshare et votre fenêtre de réponse côte à côte afin que vous puissiez coder pendant que je code. Vous devriez alors voir un écran comme celui-ci, continuer, faites défiler la page vers le bas et vous arriverez au premier exercice appelé bfs ou recherche en largeur. Avant de commencer, un conseil est donc de mémoriser comment effectuer une recherche en largeur et en profondeur d'abord, abrégée ici en bfs et dfs, car ce sera toujours pareil. Dans ce cas précis, nous n' utilisons pas une technique appelée récursivité. Donc, sans récursivité, la façon de faire bfs et dfs ressemble toujours à ceci. Sachant cela, essayons maintenant de mettre en œuvre une recherche par largeur. Voici à quoi ressemble une traversée de recherche d'un arbre en premier lieu . Ici, nous avons un arbre, 1, 2, 3, 4. Laissez-moi vous montrer à quoi cela ressemble. Ici, vous en auriez un, puis vous auriez un enfant ici qui aurait deux ans, et puis vous auriez un autre enfant juste là, ce serait trois. Ensuite, vous aurez également un arbre comme celui-ci. Voici à quoi ressemble cet arbre. Vous auriez essentiellement l' une des racines, l'enfant gauche sera deux, et puis l'enfant gauche de deux sera trois. Alors c'est le bon enfant de l'un d'entre eux. Voici à quoi ressemble l' arbre. Sachant que c'est à cela que ressemble cet arbre, voici la première traversée de recherche. La traversée d'abord en largeur nous en donnera un d'abord, puis deux, puis quatre, puis trois. C'est une traversée et on l' appelle aussi traversée de l' ordre des niveaux, donc ici, nous descendons les niveaux à la fois, 1, 2, 4, 3. Si nous en avions eu cinq ici par exemple, nous aurions eu 1, 2, 4 , 3, 5 et ainsi de suite. Voilà à quoi ça ressemble. Sachant qu'il s'agit désormais d'une traversée en largeur , voici un indice. Mettez la vidéo en pause maintenant et essayez vous-même ce problème si vous ne voulez pas l'indice. L'astuce est que vous devrez utiliser l'une des structures de données dont nous avons parlé précédemment. Pour ce faire, vous devrez notamment utiliser une pile ou une file d'attente. Allez-y, mettez la vidéo en pause ici et essayez de concevoir l'algorithme pour une traversée en largeur d'abord. Voici maintenant la solution. La solution va impliquer l'utilisation d'une file d'attente. Ce que nous allons faire, c'est que dans cette file d'attente, nous allons commencer par ajouter la racine. Une fois que nous avons ajouté la racine, nous allons prendre la racine et mettre tous les enfants en file d'attente pour cette racine. Une fois que nous l' aurons fait, nous retirerons la file d'attente. Le retrait de la file d'attente va nous donner le tout premier objet. Ensuite, nous allons mettre tous ses enfants en file d'attente. Ça va faire trois ans et tout reste, c'est un enfant de deux enfants. En fait, une façon de procéder serait d'inclure une visualisation. Ici, nous en avons un, nous allons en retirer un, et nous allons ajouter tous ses enfants deux et quatre. Ensuite, nous allons retirer deux de la file d'attente , puis nous allons mettre en file d'attente ses enfants, qui ne sont que trois. Disons qu' il y en a peut-être un autre, disons qu'il y en a cinq. Ici, nous en aurions trois et cinq. Ensuite, nous prendrions enfin notre. Puis quatre, nous mettions tous ses enfants en file d'attente, ce qui n'est rien et ainsi de suite. L'idée est que vous remarquerez que l'ordre de retrait de la file d'attente était 1, 2, 4. Ensuite, il y aura trois et cinq, qui est exactement ce qu'est BFS. La file d'attente nous donne exactement une traversée d' arbre en commençant par la largeur. Sachant cela, voyons maintenant quel est le temps d'exécution en termes de complexité de la mémoire. Mettez la vidéo en pause ici. Voici la solution. Le temps d'exécution et la complexité de la mémoire vont tous deux varier. Vous vous demandez peut-être ce qu'il y a là-dedans ? Eh bien, n est le nombre de nœuds. C'est important. Avant, nous avions ce cas où nous définissions nous-mêmes une variable. Nous définissons une variable comme un nombre de valeurs uniques qui sont entrées. Dans ce cas, par défaut pour un arbre, cette variable n sera le nombre de nœuds de l'arbre. Vous pouvez également le redéfinir, vous pouvez redéfinir le n comme la hauteur de l'arbre ou le définir comme autre chose, mais généralement, n est le nombre de nœuds de l'arbre. Sachant que, lorsque vous signalez la complexité de votre mémoire d'exécution pour un arbre, vous devez l'indiquer en termes de nombre de nœuds, qui pour nous sera égal à o sur n, car vous devez traverser chaque nœud, c'est ce qu'est une traversée en largeur d'abord et ensuite, vous devez ajouter tous ces nœuds à votre file d'attente. À un moment donné, en fait, désolé d'avoir menti un peu, votre file d'attente ne dépassera jamais la largeur maximale de l'arbre. Nous verrons ce que signifie la largeur plus tard, mais nous dirons simplement pour l'instant que o de n est la complexité de la mémoire. Nous pourrons jouer avec cette nuance plus tard, je vous expliquerai pourquoi, il y a une meilleure réponse. Pour l'instant, allez-y, mettez la vidéo en pause et essayez de la coder. Écrivons la solution. Ici, nous allons définir une file d'attente et la première valeur de la file d'attente sera en fait la racine. Tant qu'il y a quelque chose dans la file d'attente, nous allons retirer la file d'attente. Ensuite, nous allons prolonger, donc nous allons faire la queue en fait. Pour chaque branche de l'arbre, nous allons mettre la branche en file d'attente, donc mettez la branche en file d'attente. Enfin, nous allons imprimer la valeur actuelle. Cela nous donnera une traversée d' abord en largeur. Voyons maintenant si cela passe nos tests. Cliquez sur le bouton vert Exécuter tout en haut et vous pouvez voir que bfs ne figure plus dans notre liste de fonctions défaillantes. Vous avez réussi ce test. Passons à la question suivante. En fait, avant de passer à la question suivante, un conseil est que vous devriez toujours utiliser du nouveau, attendez. L'un des conseils est que vous devez toujours utiliser une file d'attente pour une traversée en largeur en premier. Vous l'avez vu en exemple ici. Tu as vu comment t'en servir. Gardez cela à l'esprit. Ce sera à peu près toujours la façon dont vous implémentez bfs sans récursivité. Nous parlerons de la récursivité dans un prochain cours. Sachant cela, nous allons maintenant implémenter la recherche en profondeur. La recherche en profondeur ressemblera à ce qui suit. Disons que nous avions cet arbre et cet arbre ait à peu près la même structure. C'est une structure un peu différente en fait. Laissez-moi dessiner ceci pour vous. Nous avons ici la racine 1. Son enfant gauche aura 2 ans et l'enfant gauche de 2 ans aura 3 ans. Alors il n'y a pas d'autres enfants ici. Le bon enfant de 1 va avoir 4 ans, juste ici. Alors, l'enfant gauche de 4 ans aura 5 ans. Ici, nous allons frapper. Une chose à noter est que je n'arrête pas dire que les enfants gauche et droit sont parce que les problèmes d'arbre sont généralement construits autour de votre arbre binaire où vous n'avez qu'un seul enfant gauche et un enfant droit. La façon dont nous avons implémenté un arbre ici, nous pouvons avoir un nombre illimité de branches. Vous n'êtes pas limité à la gauche et à la droite. Techniquement parlant, 5 n'est pas un enfant gauche de 4, 5 est la seule branche de 4. Je dis juste gauche et droite par habitude, mais ça n'a pas vraiment d'importance. Le fait est que voici à quoi ressemble grossièrement l'arbre. Nous avons 1 à la racine, ses enfants ont 2 et 4 ans, puis le seul enfant de 2 a 3 ans, seul enfant de 4 a 5 ans. Sachant cela, traversez d'abord en profondeur ou empruntez d' abord l'un de ces chemins. De la façon dont nous l'avons implémenté, 1 empruntera d'abord ce chemin par ici 4, puis nous descendrons jusqu' à 5 avant de remonter et d' explorer d'autres chemins. C'est à cela que ressemblera la traversée en profondeur. Il explorera jusqu'à une feuille. Encore une fois, une feuille est un nœud de l'arbre qui n'a pas d' enfants, pas de branches. Il explorera d'abord toute la descente , puis il remontera et commencera à explorer d'autres avenues. C'est à cela que ressemble la traversée en profondeur. Vous voyez en bas, il y aura 1, 4, 5, puis il remontera et explorera 2, puis 3. C'est une traversée qui passe d'abord par la profondeur. Essayons de trouver un algorithme. Mettez la vidéo en pause ici. Voici la solution. Pour la traversée en profondeur, eh bien, nous utilisions auparavant une file d'attente pour la traversée en premier lieu en largeur. Pour une traversée en profondeur d'abord, nous allons utiliser une pile. La pile va fonctionner de manière très similaire. Nous allons continuer à ajouter des objets à la pile, et nous allons continuer à en sortir. Voici à quoi ça va ressembler. Quand je commence par 1, nous allons faire apparaître 1, puis nous allons ajouter ses enfants 2 et 4. Maintenant que nous en avons 2 et 4, nous allons faire apparaître le dernier élément qui est 4. Ensuite, nous allons ajouter ses enfants, soit 5. Ensuite, nous allons passer à 5. Vous pouvez voir où cela va. Jusqu'à présent, nous sommes passés par 1, 4, 5. Une fois que nous en aurons fini avec 5, nous passerons à 2. Cela nous donnera notre première traversée en profondeur à l'aide d'une pile. Sachant que c'est l'algorithme, parlons de la complexité de la mémoire et de l'exécution. Quel est le temps d'exécution en termes de complexité de la mémoire ? Mettez la vidéo en pause ici, et voici la réponse. La complexité de la mémoire ici sera linéaire en termes de nombre de nœuds. ce qui concerne la complexité de la mémoire, nous allons digérer la complexité de la mémoire. Pour ce qui est de la complexité informatique, nous allons avoir complexité de calcul linéaire car nous devons effectuer des itérations sur tous ces nœuds. Même mise en garde que celle que j'ai mentionnée précédemment concernant la complexité de la mémoire, elle n'est en fait pas linéaire en termes de nombre de nœuds, mais nous en reparlerons plus tard. Maintenant, allons-y et essayons de coder cette fonction. Mettez la vidéo en pause ici et essayez-la. Allons-y et programmons cette fonction. Ici, dans notre traversée en profondeur, nous allons commencer par initialiser une pile. Cette pile contiendra notre nœud racine. Ensuite, nous allons répéter. Tant que nous avons quelque chose dans la pile, nous en sortirons. Ensuite, pour chaque branche de notre nœud actuel. Pour les branches situées dans les branches supérieures actuelles, nous allons ensuite placer cette branche sur notre pile , puis nous allons imprimer notre valeur actuelle. C'est à peu près tout pour notre traversée en profondeur. Allons-y et vérifions-le que cela fonctionne. Appuyez sur le bouton vert « Exécuter » tout en haut. Voilà, dfs ne figure plus dans notre liste d'échecs, nous avons donc réussi les tests dfs. Le conseil ici est que vous devez utiliser une pile pour une traversée en profondeur. Passons maintenant à la question suivante. Pour chaque nœud de l'arborescence, ajoutez un nouvel attribut appelé parent qui pointe vers son parent. Ici, nous allons utiliser bfs ou dfs pour l'attribution des parents. Cet attribut parent pointera vers le parent du nœud dans l'arborescence. Allons-y et dessinons à nouveau cet arbre. Disons que nous avons cet arbre juste ici. Nous avons ici 1, et son seul enfant a 2 ans et 2 a deux enfants, qui ont 3 et 4 ans. Ça va ressembler à ça et il n'y a pas d'autres succursales, juste ces gars-là. Maintenant que vous l'avez, nous allons réellement peupler les parents. Nous allons implémenter cela pour que chaque arbre pointe vers son parent. Donc 2 pointera vers 1, 3 pointera vers 2, 4 pointera vers 2. Sachant cela, réfléchissons-y et concevons un algorithme pour cela. Mettez la vidéo en pause ici. Parlons de la solution. Pour cette question, peu importe que vous utilisiez bfs ou dfs. Dans les deux cas, vous pouvez faire en sorte que cela fonctionne. En gros, l'algorithme sera nous allons effectuer une traversée et si vous regardez ci-dessus, nous avons en fait itéré sur tous les enfants ou toutes les branches pour leur courant nœud. Pendant cette itération, vous allez mettre à jour cette branche pour qu'elle pointe vers le nœud actuel, qui est le parent. Peu importe la traversée que vous utilisez. C'est l'algorithme et en fait, c'est à peu près la solution de code. Allez-y et considérez maintenant quelle est la complexité de la mémoire et de l' exécution ? Mettez la vidéo en pause ici. Comme auparavant, étant donné que nous utilisons efficacement DFS et BFS, la complexité d'exécution et de calcul est la même qu'auparavant. La complexité informatique est O de N et la complexité de la mémoire, disons pour l'instant, est essentiellement O de N. Sachant cela, allons-y et essayons le code. Mettez la vidéo en pause ici et essayez-la d'abord. Passons maintenant à la solution. Je vais tricher un peu. En fait, je vais simplement copier et coller à partir de la fonction précédente, qui exécutait déjà DFS. Allons-y et collez-le ci-dessous. Je vais supprimer cette instruction d'impression , puis je vais attribuer branch.parent est égal à courant. C'est ça. Allons-y et vérifions-le que cette fonction est correcte. Nous allons appuyer sur le bouton vert « Exécuter » tout en haut. On y va. On constate maintenant que les parents de la population ne figurent plus dans la liste des échecs aux tests. Nous avons réussi tous ces tests. Comme je l'ai déjà dit, BFS, DFS, tant que vous mémorisez cette implémentation, vous la verrez très souvent. Au moins sans récursivité, voici à quoi cela va ressembler, alors assurez-vous de connaître cette implémentation. Conseil précédent, considérez toujours les entrées vides également. Dans ce cas particulier, si notre arbre était vide, alors notre fonction échouerait parce qu'ici nous allons apparaître, nous allons obtenir du courant, le courant sera nul, et puis nous allons pour tenter d'accéder à ses branches. Encore une fois, pour tous vos entretiens et pour toutes vos questions, assurez-vous de réfléchir à ce que vous feriez avec des commentaires vides. Dans ce cas précis, nous aurions dû dire que si l'arbre n'est pas un arbre, alors nous ne ferons rien, nous y retournerons. Il est important de garder cela à l'esprit. Passons à la question suivante. Ici, nous allons utiliser BFS ou DFS pour calculer la valeur maximale dans un arbre extrêmement large mais peu profond. Allons-y et considérons ce qui suit. Réfléchissez à ce que cela signifie pour votre choix de traversée. Quelle est la complexité spatiale maximale d'une recherche en largeur ou d'une recherche en profondeur ? Allez-y. Cela est en fait lié à la nuance dont nous avons parlé plus tôt. Mettez la vidéo en pause ici et réfléchissez-y d'abord avant de pouvoir envisager l'algorithme. En fait, alors que vous considérez l'algorithme. [BRUIT] Voici la question suivante. Nous allons obtenir la valeur maximale d' un arbre extrêmement large mais peu profond. La partie importante de cette question est de considérer ce qu' un arbre extrêmement large mais peu profond fait à votre algorithme. Pourquoi est-ce important ? Qu'est-ce que cela signifie pour votre choix de traversée ? Nous avons parlé plus tôt d'une nuance subtile concernant la complexité spatiale ou mémorielle de votre mode de traversée. Cette question se concentre vraiment sur ce point, pour essayer de comprendre ce que cette nuance signifie pour votre algorithme. Mettez la vidéo en pause ici et voyez si vous pouvez le comprendre. Quelle est la différence entre arbre extrêmement large mais peu profond et un arbre profond mais très étroit pour BFS ou DFS ? Mettez la vidéo en pause ici. Voici la réponse. Pour un arbre extrêmement large mais peu profond, vous devez utiliser DFS. La raison en est que BFS ou traversée en largeur, c'est la complexité de l'espace ou le nombre maximum d' éléments dans la file d'attente ou la pile, ou quelle que soit la collection que vous utilisez , sera la largeur du arbre. Alors que pour la recherche en profondeur ou DFS, l'espace maximum que nous utiliserons est équivalent à la profondeur de l'arbre. Si j'ai un arbre extrêmement peu profond, vous voudrez que DFS minimise votre consommation d'espace. Parce que si vous avez un arbre très peu profond, vous aurez une collection très courte à considérer. Sachant cela, allons-y et concevons l'algorithme pour obtenir la valeur maximale. Mettez la vidéo en pause ici et essayez de concevoir l'algorithme. Voici la solution. Pour l'algorithme, nous allons simplement prendre la valeur maximale chaque fois que vous traversez un nœud. Chaque fois que vous traversez un nœud, comparez la valeur de ce nœud à la valeur la plus élevée au niveau mondial. Si votre valeur actuelle est supérieure, remplacez-la simplement. Ceci est très similaire à l'exemple de fréquence maximale dont nous avons parlé plus tôt. Dans ce cas, nous prenons en compte la valeur maximale. Maintenant que nous avons examiné l'algorithme, nous avons examiné le mode de traversée, mettez la vidéo en pause ici et voyez si vous pouvez trouver complexité de la mémoire et de l' exécution. Voici la réponse. Pour ce qui est de la complexité de l' exécution, encore une fois, c'est linéaire dans le nombre de nœuds, c'est O of N. Pour la complexité de la mémoire, eh bien nous en avons déjà parlé, c'est exactement pourquoi nous avons choisi DFS pour ce problème. La complexité de votre espace ou de votre mémoire sera la profondeur de l'arbre. Ce n'est pas exactement O de N. On ne sait pas non plus, du moins pour l'instant, exactement quelle serait la profondeur de l'arbre. Nous allons simplement lui attribuer une nouvelle variable. Nous allons dire que D est la profondeur de l'arbre, donc notre algorithme est o de d. Maintenant, essayons de le coder. Mettez la vidéo en pause ici. Maintenant que nous avons une implémentation DFS, je vais à nouveau être paresseux. Je vais juste le copier et le coller. Revenons ici, puis nous allons copier cette implémentation DFS, puis nous allons faire défiler la page vers le bas et la coller. Maintenant que nous avons cette implémentation DFS, nous allons supprimer l'instruction d'impression. Comme nous l'avons déjà dit, pour chaque nœud que nous prenons en compte, nous allons mettre à jour la valeur maximale. Supposons que la valeur maximale au tout début soit juste la valeur racine. Ensuite, lorsque nous explorons chaque nœud, nous allons prendre le maximum entre la valeur actuelle et la valeur la plus élevée. Enfin, nous allons renvoyer la valeur maximale. Essayons d'exécuter cette fonction et de nous assurer qu'elle passe tous les tests. Allez-y et appuyez sur le bouton vert « Exécuter » tout en haut. On y va. Nous pouvons voir maintenant que get maximum ne figure plus dans la liste des tests ayant échoué. Passons maintenant à la question suivante. Nous allons combiner des structures de données pour calculer la largeur de l'arbre. Voyons maintenant quelle est la largeur de l'arbre. La largeur de l'arbre est le nombre maximum de nœuds à une profondeur ou à un niveau donnés. Gribouillons encore une fois cet arbre. Ici, nous en avons un et un a un enfant, ce qui ne fait que deux, et deux ont deux enfants, qui ont trois et quatre ans. Ici, nous en avons trois, puis nous en avons quatre. Voilà à quoi ressemble cet arbre. La largeur de cet arbre est alors de deux car ce niveau contient deux éléments. Maintenant, si nous en avions un autre ici, disons que nous en avions cinq, et ensuite nous en avions un autre, six, disons, alors la largeur de cet arbre serait de trois parce que vous avez au plus trois sur un seul niveau. Sachant cela, allons-y et mettons à jour. Discutons de l'algorithme. Continuez et mettez la vidéo en pause ici et voyez comment vous calculeriez la largeur de cet arbre. Voici une solution. Heureusement pour nous, nous avons un mode de traversée qui nous permet de calculer la profondeur beaucoup plus facilement, qui sera une traversée par ordre de niveaux ou BFS. Vous pouvez le faire de deux manières . La première est que vous pouvez utiliser une autre structure de données pour suivre nombre de nœuds présents à une certaine profondeur. Le second est le BFS modifié afin que vous traversiez un niveau à la fois et que vous gardiez une trace du moment où vous commencez le niveau suivant. Ce sont vos deux options. Ce sont deux algorithmes différents. Nous allons implémenter la première dans laquelle nous allons utiliser une autre structure de données, lorsque vous utilisez un mappage. Maintenant que vous en avez parlé, parlons de la complexité de l'exécution et de la mémoire. Mettez la vidéo en pause ici et voyez si vous pouvez la comprendre. Voici la réponse. Pour des raisons de complexité d'exécution, les deux algorithmes, quel que soit celui que vous avez choisi, seront O sur N, où n est le nombre de nœuds. Les deux complexités informatiques sont linéaires en ce qui concerne le nombre de nœuds. Maintenant, si vous décidez d'utiliser plusieurs structures de données, dans lesquelles vous conservez une cartographie de la profondeur au dénombrement, cela ajoutera à la complexité spatiale de O of D dans la profondeur. Vous allez être linéaire en termes de profondeur car vous stockez une valeur pour chaque profondeur. Toutefois, si vous utilisez l'algorithme dans lequel vous modifiez le BFS sur place, votre algorithme aura la valeur O de largeur. Les deux algorithmes ont au moins O de largeur, car la ligne de base, c'est exactement comme ça que fonctionne le BFS d'origine. Cependant, l'algorithme qui utilise en plus une HashMap pour stocker ce mappage de la profondeur au décompte sera O de largeur plus O de profondeur. Nous allons implémenter la solution la moins efficace, ce qui peut sembler rétrograde, mais j'ai déjà implémenté la solution la plus efficace, vous pourrez donc la vérifier si vous voulez voir la mise en œuvre la plus efficace. Mais pour l'instant, je vais implémenter la solution la moins efficace. Allez-y, mettez la vidéo en pause ici et voyez si vous pouvez créer le code vous-même. Voici notre solution. Allons-y et écrivons. Nous allons utiliser notre structure de données préférée ici. Nous allons utiliser un dictionnaire par défaut. Nous allons commencer par initialiser une file d'attente. Chaque élément de cette file d'attente correspondra à la profondeur du nœud actuel, en plus du nœud lui-même, car nous devons suivre la profondeur afin de savoir quel nombre se trouve profondeur du nœud actuel en plus du nœud lui-même, car nous devons suivre la profondeur afin de savoir quel dans notre compteur de largeurs à mettre à jour réellement. Voici notre compteur, nos largeurs, et il va initialiser toutes les largeurs à zéro. Tant que nous avons quelque chose dans la file d'attente, nous allons retirer la file d'attente, puis nous allons mettre à jour le dictionnaire des largeurs en incrémentant cette valeur d'une unité. Enfin, pour chaque branche, nous allons mettre en file d'attente la profondeur incrémentée d' un et le nœud lui-même. Chaque fois que vous passez du statut de parent à celui d'enfant, nous augmenterons la profondeur d'une unité. Enfin, nous allons renvoyer la largeur maximale que nous voyons. Cela nous donnera la largeur maximale et toutes les largeurs que nous avons comptées. Nous allons maintenant l'exécuter et nous assurer qu'il passe tous nos tests. On y va. L'absence de résultats signifie que tous nos tests de documentation ont été réussis. Vous avez enfin terminé tous les exercices de cette leçon. Pour toutes ces diapositives, solutions complètes et autres exercices pratiques, n' oubliez pas de visiter ce site Web. C'est tout pour notre pratique sur les arbres , largeur/profondeur versus traversée. Vous avez vu un tas de problèmes ici. Vous avez également constaté de nombreux problèmes lors des leçons d'entraînement précédentes. J'espère qu' ils ont été très utiles. Passons maintenant à notre toute dernière leçon où nous allons terminer tout cela. 13. Conclusion: Félicitations pour avoir terminé le cours. Nous avons abordé une tonne de sujets, des ordres de croissance, des piles et des files d'attente, des listes de liens, cartes de hachage, des arbres. C'était un cours assez difficile avec une tonne de contenu et des questions vraiment brutales. Vous avez terminé 20 exercices approfondis, 20 conseils d'entretien et vous avez pratiqué la méthode en trois étapes pour résoudre des énigmes encore et encore. C'était beaucoup de contenu et les diapositives de synthèse sont d' excellents outils à mémoriser. Cependant, le point le plus important à retenir est en fait le processus en trois étapes. En ce qui concerne les entretiens, c'est la clé. Voici le processus en trois étapes unique : concevoir des algorithmes sans code, signaler les complexités liées à l'exécution et à la mémoire, et enfin, coder l'algorithme. Maintenant, pour approfondir votre compréhension pendant les trois jours suivant le cours, créez une question sur la structure des données chaque jour. Je vous encourage également à poser votre question dans la section de discussion. Vous avez juste besoin de dormir entre les deux pour réfléchir aux structures de données. Il n'est pas nécessaire que ce soit le meilleur travail de votre vie. Toute question fera l'affaire et la publiera dans la section de discussion. J'ai vraiment hâte de les voir et c'est tout. Un travail fantastique. C'est le début de votre préparation à l'entretien et vous êtes sur de bonnes bases. Consultez mon Skillshare pour plus de cours sur la science des données, l'apprentissage automatique et d'autres concepts de programmation importants. Pour plus de préparation aux entretiens, suivez-moi sur Skillshare pour plus de mises à jour, car nous aborderons puzzles de codage les plus couramment utilisés et les astuces spécifiques aux interviews. Félicitations encore une fois pour avoir atteint la fin du cours et jusqu'à la prochaine fois.