C++ : Préparer l'entrevue de codage

1. Bienvenue à ce cours !: Bonjour les gars et bienvenue à la programmation C plus souffle. L' interview de codage. Mon nom est Alex et l'époque d'un développeur de logiciels expérimenté qui travaille avec C plus depuis environ quatre ans. Maintenant, la structure de cette classe va être divisée en éléments clés qui sont discutés document objectif appelé interviews pour les développeurs de logiciels. Tout d'abord, nous allons parler des complexités d'un algorithme, fois le temps et l'espace. Ensuite, nous sauterons dans les tableaux. Ensuite, nous allons regarder les cordes. Encore une fois, les questions d'entrevue basées sur des chaînes sont le sujet sur lequel nous allons nous concentrer. Ensuite, nous allons examiner quelques algorithmes de tri très importants comme le tri des bulles, le tri rapide et ainsi de suite. Nous allons également regarder les arbres. Ce sont des traversals, et quelques autres questions d'entrevue que vous pouvez recevoir sur DOM. Et aussi, nous allons jeter un oeil aux piles et aux files d'attente. La classe est créée pour toute partie qui soit une fois pour apprendre des algorithmes dans le langage de programmation de C plus, ou quelqu'un qui veut travailler dans le domaine de l'ingénierie logicielle. Et une fois que vous apprenez des questions qui peuvent être données sur les entrevues afin qu'ils puissent fonder leurs entrevues. n'y a pas de pré-requis pour ce cours. Ensuite, votre volonté d'apprendre et une connexion Internet. En ce qui concerne le projet de classe, ce sera une question qui peut être reçue dans un scénario d'entrevue que vous pouvez regarder. Pensez à la tête, peut être le temps vous-même pendant 30 minutes et essayez de trouver le meilleur extrait que vous obtenez. Donc ça a appelé ça semble intéressant. J' ai hâte de vous voir dans la prochaine leçon. Commençons. 2. Notation de Big O: Bienvenue dans la section deux, la notation « big O ». Dans la première conférence, nous allons parler du grand O, du gros Oméga dans la complexité temporelle. Commençons. La notation « big O » est une notation mathématique qui décrit le comportement limitatif d'une fonction lorsque l'argument tend vers une valeur ou un infini particulier. En informatique, la notation Big O est utilisée pour classer les algorithmes en fonction de la croissance des besoins en temps d' exécution ou en espace. À mesure que la taille des entrées augmente. Ne pas le comprendre complètement peut vraiment vous nuire au développement d'un algorithme. Non seulement vous pourriez être durement facturé pour ne pas vraiment comprendre Big O, mais vous aurez également du mal à juger quand votre algorithme devient plus rapide ou plus lent. Lors de l'analyse de l'efficacité des algorithmes, nous utilisons un gros O. Par exemple, le temps, le nombre d'étapes nécessaires pour résoudre un problème de taille n peut être estimé à n fois n à la puissance de deux plus huit fois n plus un. Au fur et à mesure que n grandit, le n au pouvoir de deux termes finira par dominer cela. Tous les autres termes peuvent être négligés. Par exemple, lorsque n est 500, le terme cinq fois n à la puissance de deux est cent, dix cents fois plus grand que les deux fois n. Ignorer la lettre aurait effet négligeable sur le la valeur de l'expression dans la plupart des cas. De plus, le coefficient n'est pertinent si nous le comparons à un autre ordre d'expression. La notation « Big O » capture donc ce qui reste. Nous écrivons o of n au pouvoir de deux. Examinons maintenant quelques exemples des complexités temporelles que certains algorithmes informatiques. L'un est appelé constant. Par exemple, un algorithme qui détermine si un nombre est pair ou impair aura cette complexité temporelle. O of log n est appelé logarithmique. Par exemple, la recherche d'un élément avec une recherche binaire dans un tableau trié. Je vais présenter ces types de recherche et comment elle fonctionne dans une section ultérieure de n est appelée linéaire. Il s'agit de la complexité temporelle de l'itération dans un tableau à diverses fins. Par exemple, pour trouver un élément et ainsi de suite. O of n à la puissance de deux est appelé quadratique. C'est le cas lorsque vous avez deux forces imbriquées dans un tableau. Cela peut s'avérer utile lorsque vous souhaitez trier un tableau. Enfin, aucune factorielle n'est appelée factorielle. Et nous rencontrons cette complexité temporelle lorsque nous essayons de le faire, les solutions de force brute calculent des permutations sans restriction. En général, en encodant les entretiens, vous entrez la complexité temporelle que pour que votre algorithme prenne moins de temps à s' exécuter et à être plus efficace et optimisé. Cependant, vous pouvez commencer par une solution qui n'est pas si géniale si c'est la première idée que vous arrivez à la résoudre , puis à adopter une approche plus optimisée. universitaires utilisent Peek, oh, grosse thêta et la grosse oméga pour décrire les temps d'exécution. Dans le milieu universitaire, le grand Omega est le concept équivalent, mais pour les obligations inférieures, l'impression, les valeurs d'un tableau sont de gros oméga. Après tout, vous savez qu'il ne sera pas plus rapide que ce moteur d'exécution. Big Theta donne un lien étroit sur l'exécution. On peut dire que la liaison de la fonction d'en haut et d' en bas est représentée par la notation thêta. Le comportement asymptotique exact est effectué par notation d Thêta. Dans ce cours, nous utiliserons uniquement la notation Big-O pour nos algorithmes de la manière dont l'industrie a tendance à l' utiliser en essayant toujours offrir la description la plus stricte du moteur d'exécution. 3. Aperçu du tableau et du vecteur: Bonjour et bienvenue dans la section trois tableaux. Dans cette section, nous parlerons d'une structure de données de base nommée effacer qui se pose beaucoup dans les questions d' entrevue sur le codage. Et il est très important pour vous de bien comprendre cela dans la programmation. Lorsque nous pensons à un tableau, nous pensons à une structure de données qui ressemble à un ensemble d'éléments, des emplacements de mémoire stockés. L'idée est de stocker plusieurs articles du même type ensemble. Cela facilite le calcul de la position de chaque élément en ajoutant simplement un décalage à une valeur de base. Par exemple, l'emplacement mémoire du premier élément du tableau, généralement indiqué par le nom du tableau. La valeur de base est l'indice 0, et la différence entre les deux index est le décalage. Pour plus de simplicité, nous pouvons penser à une flotte de matrices à l'étage où la valeur est placée à chaque étape, disons un de vos amis. Ici, vous pouvez identifier la localisation de n'importe lequel de vos amis en connaissant simplement le compte rendu de l'étape sur laquelle ils se trouvent. N'oubliez pas que l'emplacement du prochain index dépend du type de données que nous utilisons. Et il est écrit, par défaut, des tableaux réguliers de portée locale. Par exemple, ceux déclarés dans une fonction ne sont pas laissés non initialisés. Cela signifie qu'aucun de ses éléments n'est envoyé à une valeur particulière. Leur contenu est indéterminé au moment où la théorie est déclarée. Mais les éléments d'un tableau peuvent être explicitement initialisés à des valeurs spécifiques lorsqu'ils sont déclarés en incluant ces valeurs initiales. Par exemple, vous pouvez voir ici la première ligne de notre image. Le nombre de valeurs entre les louanges ne doit pas être supérieur au nombre d'éléments du tableau. Par exemple, dans notre image sur la première ligne, a été déclaré avec cinq éléments spécifiés par le numéro entre crochets. Et l'éloge contient exactement cinq valeurs. Un pour chaque élément. Déclarez-le avec moins. Les autres éléments sont définis sur leurs valeurs par défaut, ce qui signifie qu'ils sont remplis de zéros pour les types fondamentaux . La valeur des éléments d'un tableau est accessible tout comme la défaillance d'une variable normale. Le même type. La syntaxe est le nom , puis entre crochets, l'index. Notez que le troisième Fu élémentaire spécifiait F-O-O. Ensuite, entre parenthèses, le numéro deux. Puisque le premier est F0 de 0, le second est F0 F1. Et par conséquent, le troisième est un de deux. la même raison, son dernier élément, c'est F0, F4. Par conséquent, si nous écrivions quelque chose comme F0 05, nous aurions accès au sixième élément de F-O-O et, par conséquent, nous dépasserions réellement la taille du tableau. En C plus, plus. Il est syntaxiquement correct de dépasser la plage de valeurs des indices d'un tableau. Cela peut créer des problèmes puisque X se trouve dans éléments de franges externes ne causent pas d'erreurs de compensation, mais peuvent entraîner des erreurs lors de l'exécution. cet égard, il est important de pouvoir distinguer clairement les deux utilisations que les crochets ont liées à l'effacement. Ils effectuent deux tâches différentes. La première consiste à spécifier la taille des tableaux lorsqu' ils sont déclarés. La seconde consiste à spécifier des indices pour les éléments de tableaux concrets lorsqu'ils sont accessibles. Ne confondez pas ces deux utilisations possibles des crochets avec des tableaux. À un moment donné, nous devrons peut-être transmettre un tableau à une fonction en tant que paramètre, C plus plus. Il n'est pas possible de transmettre l'intégralité de la mémoire de bloc représentée par un tableau à une fonction directement en tant qu'argument. Mais ce que vous pouvez faire, c'est que vous pouvez passer ses entrées à la place. En pratique, cela a presque le même effet et il s'agit fonctionnement beaucoup plus rapide et plus efficace de ce point de vue de base. Pour accepter un paramètre de tableau pour une fonction. Les paramètres peuvent être déclarés en tant que type, mais avec des crochets vides du tableau correspond à la taille réelle de la matrice. Par exemple, pour une procédure. Et puis dans la liste des paramètres, int arg. Puis quelques supports vides. Cette fonction accepte un paramètre de type tableau de type int appelé ARG. Pour coller cette fonction, un tableau déclaré int, mes éléments de tableau, il suffirait d'écrire un code comme cette procédure de mon tableau. Il s'agirait donc d'une vue d'ensemble du type de tableau dans C plus plus. Bien sûr, vous pouvez effectuer de nombreuses autres opérations avec chacun des éléments. Vous pouvez les échanger et ainsi de suite. Ensuite, dans les conférences à venir, nous allons jeter un coup d'œil à une variété d' algorithmes qui se présentent très souvent dans le codage des questions d' entrevue. Et nous examinerons leur complexité, leurs différentes approches et, fondamentalement, comment les résoudre afin que nous puissions mieux être préparés pour vos futurs entretiens. 4. Supprimer dans un tableau: Bonjour les gars et bienvenue à la troisième conférence, en supprimant un tableau. Dans cette conférence, nous allons parler façon de supprimer un élément d'un tableau. Cette question comporte deux variantes. À partir d'un tableau où nous savons quelle est la valeur du nombre que nous voulons supprimer du tableau. Et la variation dans laquelle nous savons quelle est la position de l'élément dans le tableau que nous voulons supprimer. Ici, nous avons la variation laquelle la valeur de l'article est saisie et non le dépôt, mais l'autre est très similaire à celui-ci. Lançons le code et après la dette et quelques explications à ce sujet. Nous pouvons penser à la complexité de ce programme comme nous le ferions dans une situation d'entrevue. Commençons par la moyenne. Comme bonne pratique, il est toujours bon de séparer vos fonctions de la fonction principale, puis d'appeler votre fonction que vous avez écrite pour une question spécifique de la fonction principale. Dans une question d'entretien et un scénario d'entretien, ils peuvent même vous donner la fonction sans le corps. C'est juste un en-tête. Ensuite, vous écrivez la fonction qui devrait faire comment cela a démarré SQL pour. Dans notre situation, lorsque nous sommes entrés dans la fonction principale, nous avons déclaré notre tableau int que nous allons supprimer, initialisé avec des valeurs intégrales codées en dur. Ensuite, chaque côté divise la taille de la théorie par la taille d'une intégrale. Ensuite, nous avons écrit x c'est six. Nous voulions en supprimer six de ce tableau. Maintenant, nous allons appeler la fonction delete element, qui renvoie la nouvelle taille du tableau après la suppression, et supprime évidemment l'élément du tableau. Cette fonction de suppression d'élément, comme vous pouvez le constater, comporte trois arguments. Le premier argument est notre tableau dans lequel nous voulons supprimer l'élément. L'article suivant. L'élément désigne la taille de la matrice. Et le dernier élément est le numéro que nous voulons supprimer du tableau, dans notre cas six. Et comme vous pouvez le constater, ce sont les arguments que nous transmettons lorsque nous appelons la fonction. Ce que fait cette fonction, c'est qu'elle déclare une variable i utilisée pour parcourir le tableau. Ensuite, dans une boucle for-loop, nous parcourons tout le tableau, en prenant chaque élément. Et si l'élément est égal à l'élément x D que nous voulons supprimer de notre tableau. Ensuite, on se brise. X se trouve dans le tableau et I est l'index où x a été trouvé. Nous allons diminuer la taille du tableau car il sera d' une taille plus petite qu'auparavant, car nous allons évidemment supprimer un élément de celui-ci. Ensuite, nous allons simplement déplacer tous les éléments d'un seul espace devant. Lesley, je vais retourner la taille du tableau. Voici la nouvelle longueur de la matrice. Ensuite, nous allons voir Monte-Carlo, puis le parcourir et le montrer. Donc, si nous exécutons cela, nous allons voir que la nouvelle baie de la tour devrait être 1158910. Vous pouvez voir que c'est la matrice. Pensons maintenant à la complexité de l'espace diamant. La complexité de l'espace est évidemment linéaire car nous ne déclarons aucune autre variable. Si c'est le cas, ils sont considérés comme constants. Cet espace est linéaire, puis la complexité temporelle , nous parcourons le tableau une fois ici. Et évidemment, une fois ici. La complexité temporelle est également linéaire. Peut-on le faire dans une plus grande complexité que celle-ci ? Eh bien, non, parce que notre élément peut être le premier, alors il serait toujours linéaire car nous devons parcourir tout le tableau. À cette étape. Il s'agissait de supprimer un élément de la baie. Et vous pouvez faire la variation lorsque vous supprimez un élément d' un tableau où vous savez que la position est très similaire à celle-ci. Mais vous pouvez essayer ça chez vous. Et dites-moi comment ça s'est passé. 5. La recherche linéaire dans un tableau: Bonjour les gars et bienvenue à la quatrième conférence. Dans cette conférence, nous allons parler de la recherche dans un tableau d'entiers, plus précisément de la recherche linéaire. Le scénario est que nous avons un tableau d' entiers dont les nombres ne sont pas triés. Donc, tout type de nombres entiers. Et le problème avec S gas pour trouver un numéro de cette baie et renvoyer son indice. Maintenant, nous écririons évidemment une fonction distincte de la fonction principale que nous appelons, appellerait depuis la fonction principale et l'utiliserait pour trouver notre élément. Comme vous pouvez le voir dans mon code ici, nous déclarons qu'un taux, il est codé en dur, valeurs 2341040. Ensuite, la valeur x qui est là. Ensuite, comme d'habitude, nous allons utiliser la fonction size of helper pour calculer la taille de notre tableau. Ensuite, nous allons donner notre int, qui sale la valeur de la fonction de recherche. Cette fonction renvoie un int et elle prend trois paramètres. Notre tableau, la taille de notre baie et le nombre que nous voulions trouver. Ensuite, je vais le parcourir à l'aide de cette variable auxiliaire appelée. Pendant que nous le parcourons, nous trouvons l'élément dont nous avons besoin, puis nous allons renvoyer son indice. À la fin, nous allons revenir moins un, ce qui signifie que nous ne l'avons pas trouvé. Retournez-moi, comme vous le savez probablement déjà, mais je vais vous le rappeler. Si vous ne le savez pas, l'instruction return lorsque vous êtes assis dans votre fonction arrête cette fonction et elle va essentiellement à l'endroit où la fonction est appelée et renvoie cette valeur. Qu'y a-t-il après un retour qui a été chauffé ? La fonction ne s'exécute pas. Ce retour moins une instruction ne sera chauffé que si ce retour n'est jamais exécuté. Donc, si notre valeur n'a jamais été trouvée dans le tableau, le résultat avec l'index de la valeur du tableau que nous voulons trouver. Si le résultat est moins un, bien sûr, je vais dire que l'élément n'est pas présent. Et s'il veut dire qu'il est présent dans le résultat de l'index renvoyé par notre fonction. moment, comme vous pouvez le constater, si vous exécutez ce programme, nous verrons que cet élément est présent dans l'index trois. Vous savez, le comptage dans un tableau est basé sur zéro, ce qui signifie que le premier index est 0. C'est pourquoi celui-ci sera un à n. Le nombre de recherches pour Dan est l'indice trois. Parlons maintenant de la complexité. La complexité de l'espace est la taille de notre début, qui est linéaire par rapport à l'entrée. Ensuite, la complexité temporelle, eh bien, la complexité temporelle est donnée par notre fonction car ici nous parcourons notre tableau une fois. Cela signifie une complexité temporelle linéaire. Maintenant, pouvons-nous faire cela mieux que linéaire ? Eh bien, non, parce que dans le pire des cas, l'élément que nous voulons trouver cette position et cela signifie que nous devons parcourir tout le tableau pour finalement le trouver dans la dernière position. Et cela prendrait du temps linéaire. Dans ce problème, la complexité spatiale et temporelle n'est guère linéaire. Passons à la prochaine conférence, où je vais vous montrer un moyen plus efficace de le faire. Mais dans une condition, et c'est le tableau qui est trié de plus en plus ou en déclin. 6. Recherche binaire dans un tableau: Bonjour les gars et bienvenue à la conférence cinq, recherche binaire dans un tableau. Il s'agit essentiellement du premier algorithme plus sérieux que nous allons aborder dans ce cours. Et celle-ci est plus souvent donnée lors d'entretiens. Et peut-être pas ces variations de base, mais d'autres variations qui peuvent avoir d'autres contraintes ou ne vous ont pas demandé sans cesse de mettre en œuvre cela. Mais un autre type de problème où vous devez utiliser ce type d'algorithme. Le problème est que, compte tenu d'un tableau trié de n éléments, vous devez écrire la fonction pour commencer à donner un élément x dans ce tableau. Une approche simple, comme nous l'avons vu lors de la dernière conférence, consisterait à effectuer une recherche linéaire sur votre tableau. La complexité temporelle serait linéaire, comme nous l'avons vu dans cet espace, la complexité serait linéaire. Mais une autre approche pour effectuer la même tâche en utilisant la recherche binaire et étant donné que notre tableau est déjà trié. Ainsi, ce que fait essentiellement la recherche binaire, elle recherche un tableau trié en divisant à plusieurs reprises l'intervalle de recherche. Inspirez, commencez par un intervalle couvrant l'ensemble du tableau. Si la valeur de la clé de recherche est inférieure à l'élément situé au milieu de l'intervalle. Plus étroit l'intervalle au bas, aidez-le, réduisez-le vers le haut de la main. Vérifiez à plusieurs reprises jusqu'à ce que la valeur soit trouvée ou l' intervalle exactement. L'idée de la recherche binaire est d'utiliser les informations selon lesquelles le tableau est trié. Réduction de la complexité temporelle, logarithmique. Maintenant, si nous regardons cette image, nous pouvons en voir un exemple. Nous avons ce tableau qui a 2581216233856172091. Nous allons prendre m au milieu serait bas et il serait 0 et h serait neuf. Les trois indices avec lesquels nous travaillons, nous devons rechercher 23. Eh bien, nous allons vérifier, et 16 est inférieur à 23. Nous allons donc passer à droite. Nous allons prendre l, m, la moyenne arithmétique de n et h, et nous pouvons voir que 23 sont plus petits, 36. Je vais chercher dans la moitié gauche. Et en ce moment, il y aurait six, parce que ce sera moi moins un. M aurait cinq ans. Ici, nous avons cherché 23 sans même regarder des articles comme 5812 ou même 72. Examinons maintenant le code et voyons comment il fonctionne. La fonction principale ressemble beaucoup à la dernière fonction principale que nous utilisons pour la recherche linéaire sur un tableau d'entiers. La seule différence est la fonction qu'il utilise et renvoie les indices où notre nombre a été trouvé. , cette fonction de recherche binaire Comme vous pouvez le constater, cette fonction de recherche binaire prend quatre arguments. Le premier est notre tableau d'entiers. Le second, le troisième est le R. Ou dans le cas où cette photo serait h. Parce que c'est juste ici, il y avait haut. Ils signifient essentiellement la même chose. Et puis x est le numéro que nous avons cherché. Nous allons passer des appels récursifs. Commencer par dire, n' est-ce pas si juste est plus grand ou égal à L. Nous allons déclarer se réunir dans le GRE et lui donner essentiellement la moyenne de R et L. Si vous vous demandez, pourquoi ce L plus R n'est -il pas divisé par deux ? Et c'est écrit comme ça. Eh bien, cela porte d'abord moins l puis ajoute. Cela permet d'éviter les cas de débordement. Le nombre est assez grand pour dépasser la mémoire et pour que votre programme se bloque. Si le tableau de viande était égal à x, le nombre que nous ne recherchions pas, nous devrions renvoyer l' index car nous l'avons trouvé. S'il est plus grand que l' élément recherché, nous ne pouvons regarder que dans le sous-tableau de gauche. Nous allons donc appeler récursivement la recherche binaire d' ARR Again L. Et puis au lieu de la zone que j'appellerai mi-moins un, nous allons seulement regarder dans le sous-tableau gauche. Dans l'autre cas, nous allons regarder dans le sous-tableau droit en donnant l'appel récursif au lieu de l Dans le deuxième argument, mi-plus un. Enfin, si aucun autre retour n'a été touché au retour des appels récursifs. Maintenant, je vais revenir moins un. Comme vous pouvez le constater, si nous exécutons ce programme, numéro dix a été retrouvé à nouveau à l'index trois. Comme je l'ai déjà dit, la complexité de l'espace est linéaire car nous avons déclaré le tableau, puis la complexité temporelle est logarithmique. Merci à cet algorithme sympa. Si le tableau n'est pas trié, vous ne pouvez pas trouver un élément dans une meilleure complexité temporelle que linéaire. Cela n'est rendu possible ici que parce que nous savons le tableau est trié et que nous avons ainsi moyen plus rapide de le parcourir. Il s'agit de recherche binaire. Vous pouvez essayer de l' implémenter vous-même sans regarder cet algorithme. Il s'agit d'une question d' entretien importante et d'un algorithme important que vous devriez vraiment connaître très bien. 7. Cordes: Bonjour les gars et bienvenue à la section quatre. Dans cette section, nous parlons de cordes. Les chaînes sont des objets en C plus, plus les trois séquences de caractères présentes. La classe String standard prend en charge ces objets avec une interface similaire à celle d'un conteneur standard d'octets. Mais je pense que des fonctionnalités spécialement conçues pour fonctionner avec des chaînes de caractères à un octet. Ici, on peut parler de fonctions membres telles que swap, qui permute le contenu de deux chaînes, ajoute, qui ajoute une chaîne à une chaîne donnée et renvoie un pointeur sur la chaîne résultante. Insérer, effacer, trouver du SDR et bien d'autres. Je vais joindre ici une photo avec des descriptions pour chacun d' entre eux afin que vous puissiez les lire et comprendre ce que chacun d'eux fait. Nous pouvons également parler d'opérateurs surchargés, comme la flexion de deux rues. Ils se tiennent avec le signe plus égal à concaténation, cette fois avec le signe plus. L'opérateur de l'égalité, mettant en œuvre jusqu'aux signes d'égalité et ainsi de suite. Ce verre a également une variété de constructeurs. Celui qui crée une chaîne vide. Celui qui prend comme argument, la chaîne entre crochets. Vous pouvez écrire votre chaîne et elle initialisera cet objet boisson avec le flux que vous êtes juste là. Celui qui prend un entier et un caractère et instancie la chaîne avec ce caractère qui sera répété par le nombre de fois donné. Pour utiliser des chaînes, vous devez inclure un fichier d' en-tête supplémentaire, code des illustrateurs qui sera inclus. Et puis le point h entre parenthèses triangulaires. Vous avez également constaté que vous pouvez inclure iostream provenant d'une entrée, d'un flux de sortie, et que vous devez généralement écrire et lire une entrée clavier. Notez que cette classe gère les octets indépendamment du codage, est utilisée pour gérer séquences multipliées ou des caractères de longueur variable, tels que UTF huit. Les membres de cette classe, tels que la longueur ou la taille, ainsi que ses itérateurs, fonctionneront toujours en octets, non en caractères encodés réels. Lors des prochaines conférences, nous allons examiner de plus près certaines questions de codage d'entrevues qui pourraient se poser avec des chaînes. Mettons-nous au travail. 8. La concaténation et la recherche de la longueur d'une Concatenation et la recherche de la longueur d'une ficelle: Bonjour les gars. Dans cette conférence, nous allons parler contact nation et de trouver la longueur de la rue. Commençons par parler de concaténation. L'opérateur Plus peut être utilisé entre deux chaînes. Dois-je les ajouter ensemble et créer une nouvelle ficelle ? C'est ce qu'on appelle la concaténation. Nous allons le traiter en C plus. Plus est en fait un objet, comme nous l'avons déjà parlé. Lors de la dernière conférence. L'objet Nice contient des fonctions pouvant effectuer certaines opérations sur des chaînes. Par exemple, vous pouvez également concaténer des chaînes avec la fonction append. Vous pouvez le faire de la manière que vous préférez. Parler à un niveau plus concret. Vous pouvez voir dans votre code quelque chose comme chaîne S correspond à a plus b, où a est une autre chaîne et B est également une chaîne. Et concaténez-les en faisant ce jumeau de A et B à la fin. Et il fera en gros un est trois, contient les deux premier jour et ensuite B. Maintenant, pour obtenir la longueur d'une chaîne, vous pouvez utiliser la fonction length a deep. Il se peut que certains programmes C plus plus utilisent la fonction size pour obtenir la longueur de la chaîne. Ce n'est qu'un alias vide. C'est à vous de choisir si vous souhaitez utiliser la longueur ou la taille. Bien sûr, si vous vouliez implémenter ce problème sans utiliser ces fonctions prédéfinies, ce sera assez simple. Vous devrez parcourir chaque caractère du tableau avec une boucle for, puis avoir une intégrale instanciée avec 0 incrémentée pour chaque caractère. De cette façon, vous pouvez obtenir la longueur sans ces fonctions prédéfinies. Vous pouvez accéder aux caractères d'une chaîne, comme vous le feriez dans un tableau de voitures en faisant référence à son numéro d'index entre crochets. Pour modifier la valeur d' un caractère spécifique. Chaîne, reportez-vous au numéro d'index et utilisez des guillemets simples, car il s'agit d'un caractère. 9. Changer la boîte de la chaîne: Bonjour, là. Dans cette conférence, nous allons parler de la façon dont nous pouvons changer le flux de cas. Le problème est que nous devons convertir toutes les majuscules en minuscules et vice versa. Industrie. La nouvelle approche consisterait ici à itérer la chaîne et à utiliser la fonction ISA per pré-build pour déterminer si chaque caractère est dans une application réelle ou non. S'il est majuscule, nous le convertirons en minuscules à l'aide de la fonction prédéfinie inférieure au CO2. Et s'il n'est pas majuscule, convertit en majuscules à l'aide deux fonctions prédéfinies supérieures. Maintenant, nous pouvons également le faire sans ces fonctions prédéfinies en ajoutant ou en soustrayant la valeur 32. Parce que c'est la différence entre les nombres entre une valeur majuscule et une valeur minuscule. Par exemple, la lettre majuscule a une valeur ascii de 65, et la minuscule a une valeur ascii de 97, soit 65 plus 32. Vous pouvez également utiliser ce petit diable pour faire ce problème. Si l'intervieweur spécifie que vous n'êtes pas autorisé à utiliser des fonctions de chaîne prédéfinies. Maintenant, si nous regardons le code, nous avons cette fonction principale où nous déclarons un flux STR, spécifie également la portée std car nous n'avons pas utilisé l'espace de noms std. Vous pouvez donc soit écrire l'espace de noms à l'aide de l'espace de noms std, soit dire std. Et ces deux doubles points avant Amy, membre de la STD que vous écrivez. Dans la ligne suivante, nous avons initialisé la chaîne STR avec cette chaîne ici. Ensuite, nous appelons la fonction de transformation sur ce STR en utilisant trois itérateurs du début de la chaîne SDR à la fin de l' historique ou de la chaîne, alors nous n' allons pas respirer March a appelé The Change Case pour chaque personnage de celui-ci. Ce n'est qu'un moyen d'y parcourir. À la ligne 16, les fonctions Change Case prennent un caractère et renvoie un caractère, comme vous pouvez le voir dans son en-tête. Et c'est juste une fonction if qui vérifie si le caractère est majuscule, puis elle renvoie les minuscules. Et si ce n'est pas le cas, c'est qu'il s'agit d'une minuscule. Dans ce cas, nous retournerons la cellule de caractères majuscules la cellule de caractères majuscules après avoir transformé la chaîne entière avec cette fonction, elle sera presque à chaque premier Casey. Ensuite, nous allons l'écrire sur l'invite de commande de sortie. Et comme vous pouvez le constater, si nous exécutons ce code, nous obtenons la chaîne exacte dans laquelle nous avons initialisé la casse inversée. J'ai déjà dit que vous pouvez utiliser le petit hack 32 pour faire ce problème sans aucune fonction intégrée. 10. Compter les mots/les voyelles: Bonjour les gars et bienvenue à la quatrième conférence. Dans cette conférence, nous allons parler de la façon dont vous pouvez vous diriger vers les voyelles dans une corde. Fondamentalement, une chaîne plus grande qui a des espaces entre les mots. Quelque chose comme des échantillons ou Pablo peut être un prix. Ce que le problème ressemble c'est que la fonction que vous êtes censé écrire reçoit un argument qui est une chaîne, puis vous devez renvoyer le nombre de voyelles. Pour un dîner de mots. C'est le problème dont nous allons parler aujourd'hui dans cette conférence. Comme vous pouvez le constater, je l'ai déjà codé pour vous, mais nous allons courir, comme nous le faisons d'habitude. Félicitations, en discutant de ce que tout fait fondamentalement , c'est généralement que nous commençons par la fonction principale. Ici, nous déclarons une corde que j'ai appelée SDR et Nike feet ABC space. Et maintenant, nous avons deux fonctions pour compter le nombre de valeurs dont il dispose. La première fonction reçoit le troisième caractère, revient brillant. Ce qu'il fait. Merci à ce personnage. Empeigne. Par exemple, il s' agirait d'une minuscule. Il le ramène en majuscules. Nous pouvons vérifier que les dents supérieures sont impeccables et non pas les minuscules, car nous aurions eu cinq conditions ici avec l'opérateur OR entre elles. Ce que nous faisons, c'est y retourner, le personnage. Personnage. Le personnage est un personnage comme celui-ci, E, I, O, U. Aucun de ces sièges est vrai ? Ensuite, nous revenons à cette fonction. Comme vous pouvez le voir, il est appelé à partir une autre fonction appelée voyelles comptées. Celui-ci reçoit un TR basé sur des paramètres de chaîne. Initialise et intègre, compte. La valeur 0. Ensuite, nous parcourons la chaîne, à travers chacun de ses caractères. Ensuite, si le personnage mort voyelle, nous augmentons le compte. À la fin, nous le retournons. Il s'agit d'une méthode très simple pour renvoyer le nombre de cordes de voyelles. Parlons maintenant de la complexité de cet algorithme. Tout d'abord, cet espace est linéaire parce que nous ne déclarons pas plus que ce traitement lui-même. Ensuite, la complexité temporelle est linéaire à, car nous parcourons chacun des caractères de la chaîne, fois temps, espace et lieu. Il s'agit d'un gros O linéaire de n. Maintenant, passons au problème suivant, je vais compter les mots. Cela va être fait en écrivant une fonction qui reçoit du paramètre qui est un flux, puis renvoie un entier. Clara Decker, maintenant que nous initialisons avec 0 et un personnage que nous appelons la mort précédente préforme s' initialise avec l'espace. Maintenant, nous mangeons le chemin à travers le flux que nous recevons comme paramètre. Si l' espace de caractères actuel dans la leçon précédente, nous incrémentons. Maintenant, qu'est-ce que cela signifie ? Eh bien, cela signifie que nous avons trouvé le début d'un nouveau mot parce que le personnage, maintenant ce n'est pas l'espace de l'espace précédent, autrefois un nouveau mot. Enfin, nous allons mettre à jour la précédente avec x of i. Lorsque nous regardons la prochaine itération. Courant, précédent, d'où l'ours précédent. Orientation décente. Nous allons renvoyer le numéro maintenant. Merci, vous ne pouvez pas voir. Si nous appelons cette fonction, elle en renvoie deux. Parce que notre chaîne ABC espace D0 serait considérée comme ayant un abc. Et alors, ce ne sont pas des mots réels. Mais si vous tapez une phrase que nous n'avions pas de sens, cela en vaudrait la peine. parlant maintenant de la complexité de cet algorithme, je pense qu'il est assez clair que cet espace concerne l'entrée, car nous ne déclarons rien plus que le flux lui-même. Nous avons une complexité spatiale linéaire, une complexité temporelle. Ce serait également linéaire parce que nous mangeons le retardé une fois dans le flux pour vérifier la condition et la valeur précédente. Juste ici. Nous avons discuté de deux algorithmes de base qui se présentent. Quelques questions. Problèmes de démarrage. Ils sont très basiques, mais il est très important de commencer par les plus élémentaires pour comprendre les complexités et comment les faire de manière optimale. Parce que vous pouvez ensuite construire sur les fondations, la profondeur. Vous devez résoudre et comprendre des algorithmes et des problèmes plus complexes à l'avenir. Le prochain chapitre dont nous allons parler doit inverser une chaîne, ce qui est une question d'interview plus fréquemment rencontrée. 11. Inverser une chaîne: Bonjour les gars, bienvenue. Cette conférence, nous allons parler de la façon d' inverser une série donnée. Comment allez-vous faire cela ? problème dit, c'est que compte tenu de ce gène à partir de l'entrée, du clavier ou d'un fichier, vous lui donnez simplement la valeur que je code en dur la tapisserie Jeff matrique de tâche, et le problème est de l'inverser. Par exemple, si nous avons une chaîne, si votre fonction avec idéalement nous avons tendance à diffuser se réfère à la dette serait inversée. ne discuterons pas de la façon dont nous implémentons cette fonction et de la complexité de chaque cellule, tout d' abord, nous avons déclaré une chaîne. Il est écrit Bienvenue sur les places. Ensuite, nous appelons simplement cette fonction. Cette fonction ne renvoie rien. Il s'agit d'une fonction de type de retour vide. Nous initialisons la longueur du flux, puis nous effectuons une itération vers la santé du flux. Ce que nous faisons, c'est que nous échangeons entre eux, les personnages correspondants. Par exemple, lorsque je vois ou que nous allons échanger ces T-R-I-E savoureux r i n moins u, o moins un, moins un. Parce que le comptage basé sur zéro des tableaux décents, nous allons parler pour échanger le premier élément, qui est 0, un élément moins un, un zéro. Par exemple, la chaîne. Nous allons prendre l'intention G moins une. Il va falloir la seule indexation puis n moins deux, qui sera ensuite échangée, puis échangez-les. Points. Nous chauffons au milieu de la rue, nous nous arrêtons. Il s'agit essentiellement de la façon la plus optimale d'effectuer cette opération. Et ceci, vous pouvez voir si je chauffe, nous allons recevoir ces gènes à l'envers. Parlons maintenant de la complexité spatiale de cet algorithme. Tout d'abord, cette complexité de l'espace est linéaire car nous ne recevons pas la complexité temporelle. N divisé par deux, car la moitié du tableau cesse de correspondre les caractères entre eux. Comme nous le savons, seuls le n et sa puissance. La notation Big O de la complexité temporelle serait, même que la complexité de l'espace linéaire à cet algorithme. Au cours de la prochaine conférence, nous allons voir comment vérifier si un mot ou une chaîne est un palindrome. Benadryl, ce qui signifie que ce rêve que vous avez d'abord est le même. Passons à autre chose et parlons de la façon dont nous pouvons le faire. La complexité de cet algorithme serait. 12. Vérifier le palindrome: Bonjour les gars et bienvenue à la conférence du cours. Nous allons voir comment vérifier si cela a fonctionné ? Ce qui signifie qu' une chaîne est un palindrome signifie que c'est la même chose. C'est la même chose si nous le lisons de gauche à droite. Par exemple, un BBA serait un Benadryl car il s' agirait probablement d'une forme ABB. Ce serait toujours un BBA. Celui-ci serait aussi un peu dramatique, mais ceux-ci ne le seraient pas parce que nous l'avons lu de gauche à droite au-delà la demi-vie, le début. Répétez l'opération de droite à gauche. Nous avons deux LC WE. Maintenant que nous avons compris quel est le problème, vous feriez un entretien. La première étape consiste à comprendre quel est le problème une fois de vous. Nous pouvons réfléchir à la façon de résoudre ce problème. Mais comme nous venons de parler de la façon d'inverser une chaîne, agit d'un problème très similaire dans ces derniers très facilement réalisés si nous avons l'algorithme inverse, car nous aurions juste besoin de vérifier si notre flux serait égal à l'inverse de celui-ci. Avec p égal, ce serait probablement vrai. Mais maintenant, nous allons adopter une autre approche de ce problème. Résolvez le fait de fonctionner comme une chaîne de paramètres. Et ensuite, nous ne reviendrons aucun diplôme car vous allez simplement imprimer sur la sortie ce gène reçoit en tant que paramètre. Le paramètre va commencer par les valeurs initiales 0, puis vieillir avec la taille de notre flux. Ensuite, alors que l'index, l' index, l'index, ce cas XDR n'est pas égal à la STR. Donc, le personnage magique depuis le début, pas la scène que nous allons imprimer. La chaîne n'est pas apparente. Dessinez-moi le retour aux chemins croisés de la fonction h et del. Ce qui signifie que l'âge n' est pas inversé, signifie que tout le flux, nous pouvons dessiner cela. Vous pouvez voir si je fais glisser, ça vérifie chacune de ces astuces. Donc, un BPA, un BB, CC, un BB ou non. La complexité. La complexité est facile à considérer aujourd'hui, mais parce que nous avons cette constante de napa autre que le flux d'entrée, serait le cas, deux divisés par deux parce que nous avons tous besoin d' avoir ce gène. Nous avons atteint la moitié de h serait la boucle de while avec IT. La complexité est linéaire instagram en ce qui concerne le précis, ce serait évidemment topo l' a empêché de le faire. Parce que vous devez encore vérifier la théorie pour vous assurer que tous les personnages sont égaux afin que vous puissiez confirmer que vos élèves sont à propos de la dernière conférence de cette section, la prochaine conférence. Nous allons vérifier si deux chaînes sont des anagrammes, ce qui signifie publier les mêmes caractères. Il y en a plus. Découvrez comment pouvons-nous faire pour être l'algorithme le plus optimal. 13. Vérifiez si 2 chaînes sont des anagrams: Bienvenue de retour. Dans cette dernière conférence ici, vous parlez de comment pouvez-vous vérifier une force donnée ? Des mots ? Il peut s'agir de phrases. Ce qui signifie qu'ils sont composés de personnages. Qu'est-ce que je veux dire par échantillon ? Nous avons deux mots, comme chien. chien serait anagramme parce qu'un T1, 01. Ce serait encore un accord parce que le décompte dans ces derniers s'exécute avec f one g, et celui-ci nous a deux anagrammes de G. Le problème nous demande d' écrire la fonction pour vérifier si deux chaînes sont ou non des anagrammes. Comme vous pouvez le constater, la fonction principale commence par initialiser chacune de ces chaînes. Nous appelons une fonction qui prend comme paramètres deux flux seront vrais. Si ce G est que j'intègre la fonction cosinus, nous déclarons deux entiers qui se lient. Nous allons d'abord vérifier que les chaînes ont la même longueur. Cela signifie qu'ils ne peuvent pas avoir les mêmes personnages. Comme il est évident que deux quantités de caractères ne peuvent pas être égales avant la sortie du TPI du haut-parleur, ils vont trier les chaînes. Les étoiles, les trient en fonction des valeurs ascii, les trient par ordre alphabétique. Ensuite, nous allons être trois gènes en même temps. Est-ce que nous en avons utilisé un, mais nous aurions pu l'utiliser parce que fondamentalement la même chose. Nous ne serions pas dans cette fonction, cette ligne car elle pourrait déjà renvoyer un faux booléen. Nous parcourons chacun de ces gènes et nous vérifions leur caractère, disons égaux, non égaux, nous retournons faux. Nous arrivons à la fin d'eux à la place, personnages parlés sont égaux et nous pouvons revenir vrais. Nous mettons cette fonction qui renvoie chaque état de un à dix. Nous pouvons ces flux, les grammes seront cartographiés. Sinon, nous pouvons dire qu'ils ne le sont pas. Par exemple, si nous voyons ces deux chaînes, le bon exemple, vous pouvez voir qu'elles sont n. Si nous changeons le deuxième flux, ce qu'il ferait est essentiellement avec cette condition, soit fausse ou Nous pouvons même les faire de la même taille, lettres différentes et les deux, ce sont toujours des patients noirs que vous pouvez voir ici parce qu'ils les trient par ordre alphabétique et verraient les trient par ordre alphabétique que l'un est p, un est G. Mieux vaut cette tendance si énoncée ici, trois fois fausse. Parlons maintenant de la complexité du programme. Saline tient compte de la complexité de l'espace. Nous pouvons envisager le premier streaming. La complexité de l'espace serait énorme O of n plus m. Merci de rester avec moi. Dans cette section. Nous allons continuer avec la prochaine section. Sujet très important concernant les questions de codage de l'entrevue. Tri. Que ce soit si nous parlons de la crèche ou comme vous pouvez le voir, cela peut être très utile lorsque nous travaillons avec des cordes. Nous allons donc dissimuler leur section complexité maintenant. 14. La fonction STL sort(): Bonjour les gars et bienvenue à la deuxième conférence. Dans la deuxième conférence, nous parlons de la fonction de tri disponible dans la bibliothèque standard de C plus plus. Vous pouvez l'utiliser comme alternative simple lorsque l'intervieweur n'essaie pas réellement de tester votre capacité à trier un tableau ou une structure de données, mais cela est nécessaire pour effectuer le reste de votre problème. Vous pouvez essayer d'utiliser ces fonctions de tri. Et c'est un scénario où vous avez besoin de trier vos éléments, mais vous n'avez pas besoin d' implémenter vous-même l'ensemble de l' algorithme. Le tri est l'une des données les plus élémentaires fournies par les fonctions. Cela signifie évidemment organiser les données d'une manière particulière, qui peut augmenter ou diminuer ou n' importe quelle autre fonction de comparaison que vous pourriez utiliser en fonction de la structure de données dont vous disposez. Dans des environnements plus complexes. Supposons que vous ayez des structures de type chat. Vous voulez les commander en fonction du nombre de moustaches qu'ils possèdent. Vous devrez implémenter cette fonction de comparaison spécifique. Vous pouvez réellement passer le troisième argument à cette fonction. Nous le verrons plus tard. Il les triera essentiellement par moustaches numériques. Il y a une fonction intégrée. Comme je l'ai déjà dit, le C plus plus STL provient de la bibliothèque standard. Nom de cette fonction. Les intérêts des usages internes sont dans plus de détails sur chaque implémentation car l'intervieweur peut même SQ, comment ces fonctions sont implémentées s'il voit que vous l'utilisez. Eh bien, il utilise un hybride de tri rapide, tri de tas et de tri par insertion. En fonction de quelques facteurs. Par défaut, il utilise le tri rapide. Que se passe-t-il si le tri rapide fait un partitionnement injuste plus que n long ? Il passe au tri des tas. La taille de la baie devient vraiment petite. Il passe à nouveau au tri par insertion. Maintenant, si nous examinons ce code ici, nous pouvons voir cette fonction ici même en action. Vous pouvez voir dans la fonction principale que nous avons regardé unaire que nous avons initialisé un tableau codé en dur. Ensuite, nous avons obtenu la taille en utilisant la taille des opérateurs. Ensuite, nous utilisons cette fonction ici qui prend deux itérateurs. Nous lui avons donc donné ARR, qui est le pointeur du premier élément du tableau. Ensuite, ARR plus n, qui est la fin de la matrice. Ensuite, c'est le tri. Pour le voir en action. Nous l'avons également imprimé à l'écran après le tri et, comme vous pouvez le voir ici , nous l'avons trié de plus en plus. Maintenant, comme je l'ai dit, vous avez passé cette fonction de tri, troisième paramètre de comparaison qui ordonne les éléments d'une manière différente. Montre-toi ça. Je garderai cette fonction de tri, paramètre, fonction de comparaison qui trie les éléments de façon décroissante. C'est ce qu'on appelle plus de battement. Cela a altéré notre situation de moins en plus. Bien sûr, nous pouvons implémenter votre propre fonction ici, que vous pouvez écrire vous-même au-dessus la fonction principale qui prend deux paramètres et renvoie un booléen sur quelle que soit la condition vous voulez réorganiser, c'est vrai. Cette année serait moyen très intéressant et facile de contourner le tri lors d'une entrevue. Comme je l'ai dit, si l' intervieweur est cette dette, curieux de voir si vous pouvez réellement trier le tableau vous-même ou S2 pour un algorithme de tri spécifique. De plus, compte tenu de la complexité temporelle par son implémentation, c'est n fois log de n. Et c'est en fait la meilleure complexité par laquelle vous pouvez commander un tableau. Dans les prochaines conférences, nous allons maintenant examiner de plus près certains algorithmes de tri réellement implémentés. La façon dont ils travaillent. Nous examinerons également leurs complexités. Découvrez quelques façons de trier un tableau ou une autre structure de données que vous pourriez avoir. 15. Bubblesort: Bonjour les gars et bienvenue à la troisième conférence. Dans cette conférence, nous parlerons l' algorithme le plus basique qui trie un tableau que vous pouvez implémenter vous-même très facilement. C'est ce qu'on appelle le tri à bulles Il n'a pas la meilleure complexité temporelle et spatiale. Mais nous y arriverons dans une seconde. Tout d'abord, je dois dire à propos de cet algorithme, outre le fait qu'il s'agit l' algorithme de tri le plus simple existant, comment il fonctionne en échangeant à plusieurs reprises les éléments adjacents s' ils sont mal commande. Voyons maintenant cet exemple afin que nous puissions mieux visualiser qu' en regardant le code. Comment l'algorithme est-il réellement une cellule blanche ? Nous allons intégrer le tableau 5142 dans ce qu'il fait. Fondamentalement payé les deux premiers éléments. Et il voit que cinq sont plus gros qu'un, donc il les échange. Ensuite, il faut que 545 soit également plus grand que quatre, donc il les échange à nouveau. Ensuite, 525 est plus grand que deux, donc il les échange. Et à la fin, nous en avons 58. Ils sont correctement positionnés, sorte qu'ils ne font aucun échange. Puis il passe encore une fois. prenant des éléments deux par deux, comme je l'ai déjà dit, éléments adjacents, paraphrasez-les s'ils sont dans le mauvais ordre et s'ils le sont, les échange, sinon, ce n'est pas le cas. Un sur quatre est dans le bon ordre, donc il ne sera pas échangé pour lui ou pas dans le bon ordre parce que quatre est plus grand que deux, donc nous les échangerons. 45 sont dans le bon ordre, puis 58 sont dans le bon ordre. Une fois encore. Vous pouvez voir à ce stade que notre tableau est déjà trié, mais notre algorithme ne sait pas encore s'il est complètement trié, car il n'aurait pas pu le faire à ce stade. Il a donc besoin d'un autre espoir, c'est qu'il n' échangera évidemment aucun élément parce qu'ils sont déjà ou en troisième envoi. Mais comme vous pouvez le constater dans la troisième base, il reprend les éléments de Dubaï, et il ne fait aucun échange. Examinons maintenant le code de cet algorithme. Comme vous pouvez le voir dans la fonction principale, nous déclarons qu'il s'agit généralement d'un tableau codé en dur avec des valeurs. Ensuite, nous déclarons une intégrale, et cette fois pour manger la taille de notre baie que nous avons déclarée, en utilisant à nouveau à la taille de l'opérateur. Ensuite, nous appelons la fonction de tri des bulles. Comme vous pouvez le constater, il faut deux paramètres, notre tableau, et il monte maintenant dans la pile. Vous pouvez voir qu'il entre dans la fonction de tri des bulles. Il renvoie un vide car il trie simplement le tableau et ne renvoie rien. Pour le premier élément prend le tableau là-dedans, j'ai dit, le deuxième élément est la taille de celui-ci. Nous allons maintenant déclarer deux éléments, moi et J. Theta. Je suis juste habitué à parcourir le tableau. Ça se passe comme ça. Requête. Chaque élément du tableau, nous passerons à nouveau de 0 à n moins I moins un. Vous pouvez ignorer car il est basé sur zéro. Il va essentiellement du premier élément théorique à l'élément n moins. Ensuite, il vérifie si ARR de j est plus grand que ARR de g plus un. Ce qui signifie que nous avons un élément plus grand devant un élément plus petit. Et nous ne pouvons pas avoir ce SP1 notre baie dans l'ordre croissant. Échangez les adresses des éléments situés à, avant lesdits indices. Affichage qui rend le changement enceinte. Et quand nous revenons à imprimer la théorie, vous pouvez voir que lorsque nous exécutons le programme imprime le tableau trié plus en plus avec le fait que la deuxième boucle sur l'itère jusqu'à n moins I. Il y a une raison derrière cela. Parce que les éléments du tableau après n moins j'ai déjà trié. Parce que si on y pense, d'abord, ça passe de 0 à n moins un. Ainsi, la fin de la théorie dans la deuxième boucle va de 0 à n moins I moins un, ce qui est également n moins un. Donc, ça va jusqu'au bout. Il permet de garder la chance que le dernier élément se trouve à la dernière position. Ensuite, passez de 0 au dernier élément. Et ensuite, l' élément de chaîne va itérer sur les deux n moins un moins I, qui sera un, c' est-à-dire n moins deux. Donc, en excluant le dernier élément. Fondamentalement, il va chercher le deuxième plus gros élément du tableau et ainsi de suite. C'est ainsi que fonctionne l'algorithme. Il a continuellement trente, où l'élément le plus important à mettre à la fin de la théorie. À la fin, je comprends que la fin n'est pas déjà triée. Lors de la première itération, elle recherchera le plus grand et le plus grand élément. La deuxième itération de la deuxième plus grande, et ainsi de suite, atteint le premier élément du tableau est déjà triée. Si nous parlions de la complexité temporelle et spatiale de cet algorithme, la complexité de l'espace est linéaire par rapport à l'entrée car nous venons de déclarer ce tableau ici, puis nous déclarons deux variables, en itératant trois, mais qui sont considérées comme des constantes. La complexité de l'espace est donc grande O de m et elle est linéaire. Maintenant, arriver à la complexité temporelle de cet algorithme est grand O of n à la puissance de deux. Il s'agit donc d'une complexité temporelle quadratique lorsque l'algorithme itère pour chaque élément du tableau. Une autre itération pour fondamentalement pas vraiment tout le rayon, mais vous comprenez l'idée. Il tend asymptotiquement à une complexité quadratique. Encore une fois, nous avons une fonction d'échange dont je n'ai même pas parlé. Ce que cela fait. Comme vous pouvez le constater, il ne renvoie rien qu'il faut pour intégrer des pointeurs et il échange entre eux. C'est un algorithme de tri très rapide et simple que vous pouvez utiliser sur une course que vous vouliez trier l'anglais de plus en plus. Mais sachez simplement que sa complexité temporelle est quadratique et pas le meilleur type de complexité temporelle que vous puissiez avoir lors du tri d'un tableau, ce que BASF aurait déjà dit n log n. propose d' implémenter cet algorithme maintenant que ce n'est pas la complexité de cette fois, comme vous pouvez le voir dans la prochaine conférence, il existe de meilleurs algorithmes de tri que vous pourriez apprendre et en fait mettre en œuvre pendant votre entretien lorsque vous êtes interrogé à ce sujet. Mais c'est un fondement. Et c'est un algorithme assez basique. Il est agréable de commencer par entrer en contact avec un algorithme de tri plus facile pour commencer. 16. Quicksort: Les gars, bienvenue à la quatrième conférence. Dans cette conférence, nous parlerons de Quicksort. Quicksort est un autre algorithme de tri qui fonctionne sur les baies. Et c'est un algorithme plus efficace que de proposer un tri du point de vue de la complexité temporelle et de la complexité de l'espace. Maintenant, contrairement à March vers, Quicksort est un algorithme de division et de conquête. Ce qu'il fait, c'est juste un gros élément et partitionne le tableau donné autour du pivot. Beaucoup de versions différentes de Quicksort, ce grand pivot de différentes manières serait toujours choisir le premier élément. Une autre façon serait de toujours choisir le dernier élément, ce pivot, comme nous le ferons dans notre implémentation. Vous verrez cela dans une seconde. Ensuite, vous pouvez choisir un élément aléatoire est point. La meilleure façon serait de choisir le SPM médian. Le tri rapide du traitement des clés est la partition. La cible de la partition. Compte tenu d'un tableau et d'un élément x de pivot de tableau. Ce que cette fonction de partition fait, c'est qu'elle place x et sa position correcte dans un tableau, ce qui signifie que tous les éléments plus petits seraient alors sur sa gauche. Et tous les plus grands éléments seront là dessus, n'est-ce pas ? Ce processus ne devrait prendre que la complexité temporelle linéaire. Nous examinons le code et essayons de le comprendre. Nous allons voir que dans la fonction principale, nous avons déclaré un tableau comme nous le faisons toujours avec ces valeurs codées en dur. Ensuite, nous prenons sa longueur en utilisant la taille de l'opérateur. Ensuite, nous appelons une fonction appelée Quicksort qui prend trois paramètres. Le premier paramètre est le tableau. Le deuxième paramètre, les points roses sont liés à ceux que vous souhaitez trier, dans notre cas, l' index du premier élément, qui est égal à 0. Le dernier élément, ce troisième paramètre, la limite supérieure que vous vouliez trier dans notre cas, le dernier index d'élément, et c'est n moins un. Nous avons également déclaré quelques fonctions de portage d'oxygène. Une théorie de l'impression. Le second consiste à échanger deux éléments à l'aide de pointeurs. Maintenant, si nous allons à la fonction QuickSort qui appelée à partir de la fonction principale, nous allons tout d'abord vérifier si le bas est plus petit que cela n'est fait, vérifier si le bas est plus petit que cela n'est car plus tard, nous allons appelez cette fonction de manière récursive dans les sous-tableaux gauche et droit du pivot. Nous devons donc toujours veiller à ce que la limite inférieure soit inférieure à l'obligation supérieure. Ensuite, je vais donner la valeur de la perdition de notre tableau. Et les limites inférieures et supérieures sont l'indice de partitionnement. Ce qui signifie, où est notre pivot à la bonne position dans le tableau qui serait trié. Dans cette déposition dont nous venons de parler. La position où tous les éléments à gauche et plus petits que lui, et tous les éléments qu' il contient sont plus grands que lui. Peu importe leur ordre car le tableau est trié ou non. Ça n'a pas d'importance. Cet élément se trouve à la position de la piste où cette condition se produit. Ensuite, nous appellerons cette fonction récursivement notre tableau, la position basse et la position pivot moins un. Ensuite, notre index pivot du tableau plus une limite supérieure, ce qui signifie que nous appellerons de manière récursive le tri rapide pour le sous-tableau gauche et le sous-tableau droit du pivot qui est correctement positionné à ce stade. Voyons ce que fait cette fonction de partition. Il faut également trois paramètres comme la fonction QuickSort. Nous déclarons un pivot. Integral prend le dernier élément car, comme je l'ai dit, nous allons implémenter la variation de QuickSort où le pivot est considéré comme le dernier élément du tableau. Ensuite, nous déclarerons moi, ce qui serait moins un, moins un, parce que le premier élément de notre tableau serait 100 moins un est moins un. Nous verrons dans un peu pourquoi nous le prenons moins un et non 0. Ensuite, nous utiliserons une autre intégrale pour parcourir tout le tableau. Itération dans l'ensemble du tableau. Nous disons que si l'ARR de g, c'est-à-dire l'élément actuel de l'itération, est plus petit que le pivot. Nous allons d'abord incrémenter I, puis nous échangerons ARR de I de j puis nous passerons sur ces colorants, itération linéaire à travers le tableau. Et 28, nous trouvons un objet plus petit que notre pivot. Dans ce cas, le dernier élément du sous-tableau auquel nous sommes, nous le mettrons au début du tableau. Au début, eh bien, premier indice qui n'est pas déjà occupé. Il place tous les éléments plus petits que notre pivot à l'avant du tableau. Enfin, nous échangerons ARR de I plus un avec notre pivot. Parce que c'est la bonne place dans le tableau. C'est là qu'il serait faux que le tableau soit trié, nous retournerons simplement cet index, c'est-à-dire son index correct. Maintenant, vous pouvez voir nous avons compris comment fonctionne la fonction de partition. Et nous avons également compris qu'après le froid, nous avons également appelé récursivement cette fonction de partition sur la sous-raison gauche et droite de pivoter. De cette façon, triez la baie. Maintenant, comme vous pouvez le constater, nous avons un tableau d' éléments, puis 789, Un et cinq. Quand on l'exécute. La fonction PrintArray doit imprimer notre tableau. Vous pouvez ainsi voir ces données de tri. Parlons maintenant un peu de ces algorithmes. respects de stabilité ne sont pas en place. Propriété. Tout d'abord, Quicksort est-il stable ? L'implémentation par défaut n' est pas stable. Cependant, n'importe quel algorithme de tri peut être rendu stable en considérant les index comme paramètre de comparaison. Deuxièmement, expert, la définition large de l'algorithme en place. Quicksort est considéré comme un algorithme de tri des employés. C2c est un espace supplémentaire uniquement pour stocker des appels de fonctions récursifs, mais pas pour manipuler l'entrée. On peut dire qu'il présente une complexité spatiale linéaire. Parlons de la complexité temporelle pour voir à quel point cet algorithme est efficace. Eh bien, même si c'est mieux que le tri par bulles, ce qui, dans le meilleur temps, la complexité serait linéaire. Mais dans la moyenne et le pire des cas serait quadratique, serait grand O of n à la puissance de deux. Modèle Quicksort dans la complexité temporelle moyenne, divers n log n. La complexité du masque est toujours n log n, mais la pire complexité reste quadratique. N à la puissance de deux. Dans les entretiens, le nom vous demande quelque chose d'environ des semaines. Si ce n'est pas la mise en œuvre complète. Vous pouvez vous demander si vous savez quelle est sa complexité temporelle, si vous savez comment la fonction de partition fonctionne et quelle est sa complexité temporelle. Ce qui est d'ailleurs linéaire. Comme nous l'avons déjà vu. Nous n'effectuons qu'une itération dans le tableau. Et il pourrait même sq les appels récursifs dans la fonction de tri rapide où c'est un très bon algorithme de tri dans une interview. Et c'est un outil très utile que vous pouvez utiliser pour trier les éléments d'un tableau que vous possédez. Lorsque vous n'avez pas la fonction de tri STL, le tri des bulles, le tri des bulles. Si vous voulez quelque chose de plus efficace , cet algorithme conviendrait parfaitement. 17. Arbres: Bonjour les gars et bienvenue à la section 6 de ce cours. Dans cette section, nous allons parler la nouvelle structure de données appelée trois. Contrairement aux tableaux, listes liées, piles et files d'attente, qui sont des structures de données linéaires, les arbres sont des structures de données hiérarchiques. Le nœud supérieur est appelé racine de l'arbre. Les éléments qui se trouvent directement sous un élément sont appelés enfants. L'élément D directement au-dessus de quelque chose s'appelle son parent. Par exemple, a est l'enfant de f et f est parent d'une dette dans cet arbre que nous avons dessinée à l'écran, n'est-ce pas ? Enfin, les éléments sans enfants sont appelés feuilles. Parlons maintenant de pourquoi utiliser des arbres ? Eh bien, une des raisons serait que vous êtes allé stocker des informations qui sont naturellement héritées de la pharmacie. Pensez à la façon dont vos fichiers sont organisés sur votre PC ou votre livre Mac, quoi que vous ayez, commencez par le dossier racine puis vous les parcourez dans un ordre d'article. Système rapide sur l'ordinateur. Ils sont probablement implémentés à l'aide d'arbres. De plus, les arbres fournissent un axe et une recherche modérés. C'est une liste liée aux rideaux, mais plus lente que les tableaux. L'arbre fournit également une insertion et une suppression modérées. Plus rapide que les tableaux, mais les listes liées sont plus lentes, plus minces et non ordonnées. Liste également probable. Et contrairement aux tableaux, les arbres n' ont pas de limite supérieure sur le nombre de nœuds. Les nœuds sont liés à l'aide de pointeurs. Il y a donc un avantage lorsque nous regardons cette page qu'un arbre et que vous pouvez stocker. Les principales applications des arborescences incluent la manipulation des données TO de la hiérarchie, ce qui facilite la recherche des informations. Nous verrons qu'il traverse, lors de l'une des conférences suivantes. Manipulez les données des listes triées. Ils peuvent être utilisés comme flux de travail pour la composition d'images numériques, pour des effets visuels, des algorithmes de routeur. Et aussi la prise de décision en plusieurs étapes de l'agriculteur, par exemple, les échecs d'affaires. Du point de vue de l'implémentation, l'arborescence est représentée par un pointeur vers le nœud le plus haut de l'arborescence. L'arborescence est vide, puis la valeur de ce nœud le plus haut appelé racine est connue. Un nœud d'arborescence contient les parties suivantes. Tout d'abord, il contient des données dans, puis il contient des pointeurs vers ses enfants. Nous pouvons représenter trois nœuds à l'aide de structures. Par exemple, je suis attaché ici. Vous pouvez voir exactement de quoi je parle. Mais nous allons passer à la mise en œuvre dans C plus, plus un peu plus tard. moment, parlons un peu plus des types d' arbres qu' il y a dans la programmation. Comme je l'ai dit, trois en informatique c'est comme dans le monde réel. La seule différence est qu'en informatique, il est visualisé à l' envers avec la racine sur le dessus et empêche les maladies provenant de la racine jusqu'aux feuilles de l'arbre. La structure de données arborescente est une structure de données non linéaire. Un arbre peut être représenté à l'aide différents types de données primitifs ou définis par l'utilisateur. Comme nous l'avons vu avec le déchargeur tout à l'heure. Mis en œuvre trois, nous pouvons également utiliser des tableaux, listes liées, des lunettes ou d' autres types de structures de données. Il s'agit d'un ensemble de nœuds liés les uns aux autres pour montrer que les nœuds de relation sont connectés à des arêtes. Mais en pratique, plus comme des pointeurs lourds les uns vers les autres. Types d'arborescences dans les structures de données. Tout d'abord, il existe l'arbre général, dont il n'y a aucune contrainte, qui lui est imposé, sur l' air gardé de l'arbre. En général, chaque nœud peut avoir un nombre infini d'enfants. Ces trois arbres sont le superensemble de tous les autres types d'arbres. Maintenant, nous allons passer à des arbres binaires beaucoup plus utiles en mars, plus sur les questions d'entrevue simplement parce qu'ils ont structure plus simple et élégante une structure plus simple et élégante et qu'ils sont plus faciles à poser. Les arbres binaires sont le type d'arbre dans lequel chaque parent peut avoir au plus deux enfants. Les enfants sont appelés « carte f » ou « enfant droit ». Ntc est l'un des arbres les plus couramment utilisés dans certaines contraintes et des propriétés sont imposées aux arbres binaires. Il en résulte un certain nombre d' autres arborescences de recherche binaire G AVL largement utilisées. Et ainsi de suite. Nous allons parler de ces types d'arbres en ce moment. arbre de recherche binaire est donc une extension de l'arbre binaire dont nous venons de parler, mais il comporte d'autres contraintes d' édition. Par exemple, la valeur des enfants gauche d' un nœud doit être inférieure ou égale à la valeur de son parent. Et la valeur du canal droit est toujours supérieure ou égale à la valeur de son parent. Cette propriété des arborescences de recherche binaires la rend adaptée aux opérations de recherche. Intense. Comme chaque nœud, nous pouvons décider avec précision si la valeur sera dans la sortie de vos droits. Par conséquent, il s'appelle l'arbre de recherche. arbre AVL est un type d'arbre plus complexe. Qu'il s'agit d'un arbre de recherche binaire auto-équilibré. Le nom AVL figure sur le nom de ses inventaires. fils adulte se sentait timide. Il s'agit alors du premier arbre équilibré dynamiquement avoir été implémenté dans l'arborescence APR. Chaque nœud se voit attribuer un facteur d'équilibrage basé sur lequel il est calculé que l'arbre soit équilibré ou non. Si vous avez un arbre, la hauteur des enfants du nœud diffère d'au plus un. Le facteur d'équilibrage valide si les artères sont de 10 n moins un. Lorsque le nouveau nœud est de 80 à l'arborescence AVL, entrée devient déséquilibrée, puis rotation est effectuée pour s'assurer que l'arbre reste équilibré. Les opérations courantes telles que intuition par insertion de recherche ne prennent que beaucoup de temps logarithmique dans cet arborescence AVL et elles sont largement utilisées pour les opérations de recherche. Il existe également des arbres appelés arbres NRV. Le nombre maximum d'enfants qu'ils peuvent avoir ici est limité à cette variable n. L'arbre binaire est un arbre, comme vous le notez dans la structure de données binaire des deux enfants d' aujourd'hui, vous trouvez que le plus couramment utilisé dans la présentation de n. Mais les arbres NRA complets, dont les enfants d'un nœud soit 0, soit une retraite complète est l'arbre dans lequel toutes les valeurs par défaut sont au même niveau. Pour certaines propriétés des arbres binaires. Quelques autres propriétés mathématiques. On peut dire que le nombre maximum de nœuds au niveau l d'un arbre binaire est de deux à la puissance de l. Ensuite, à partir de sa construction, le nombre maximal de nœuds dans l'arbre binaire de hauteur h plus deux à la puissance de h moins un. Dans l'arborescence binaire avec n nœuds, hauteur minimale possible ou nombre minimum de logarithme Cs de base deux de n plus un. Faisons un arbre binaire avec LDF a au moins deux l plus une variable. Dans l'arborescence binaire où chaque nœud a deux enfants, le nombre de nœuds feuilles est toujours d' un de plus que de nœuds avec deux enfants. Il s'agit d'une vue d'ensemble générale de la structure de données arborescente. Ceux-ci sont très utiles pour les questions d'entrevue. Est-ce que l'on aborde un sujet plus complexe à discuter ici. Beaucoup de gens que je connais m' incluant dans le meilleur n'étaient pas si courts d'arbres. Mais dans ce cours, nous examinerons quelques exercices avec eux, des traversées, etc. pour vous permettre de vous sentir plus prêt pour votre entretien de codage. Surtout sur ces structures de données. Ensuite, deux problèmes concernent les gens, ceux qui ont été interviewés dans le passé. Passons donc à la prochaine conférence maintenant. 18. Les voyages : DFS, BFS: Bonjour les gars. Dans cette deuxième conférence, nous parlerons des traversées d' arbres, plus précisément des traversées d'arbres binaires. Comme vous l'avez déjà vu. Contrairement aux structures de données linéaires qui sont des tableaux, des listes liées, des files d'attente, piles, etc., qui n'ont qu'un seul moyen logique de les parcourir. Les arbres peuvent être traversés de différentes manières. Voici ce qui est généralement utilisé pour traverser les arbres. Nous parlerons de profondeur d'abord traversée, de cette conférence, qui sont en ordre, signifie que nous allons d'abord vers la gauche, la note, puis la racine, puis vers le nœud droit. Précommandez, c'est-à-dire que nous visitons d' abord la racine, puis l'enfant gauche et l'enfant droit. Disons que nous avons postorder, ce qui signifie que nous allons d'abord à gauche, puis à droite, puis nous allons enfin à la racine. Il existe également une traversée ESA, traversée de la largeur première ou l'ordre des niveaux, qui prend essentiellement, imprime la note dans l'ordre de leurs niveaux, de leurs couches. L'algorithme de traversée dans l'ordre consiste à traverser d'abord le sous-arbre gauche, puis à appeler dans l'ordre pour le sous-arbre gauche. Visitez ensuite le tendon racinaire, traversez le sous-arbre droit, puis appelez pour trouver le sous-arbre droit. Dans l'ordre premier, nous avons d'abord rendu visite à l'enfant gauche et à l'enfant droit. Utilisations de l'ordre. Dans le cas d'arbres de recherche binaires. Dans l'ordre, la traversée donne des nœuds dans un ordre non décroissant. Pour obtenir les nœuds d'une arborescence de recherche binaire quart non croissant de variation de la traversée inordonnée. La traversée dans l'ordre peut facilement être utilisée. La traversée en précommande est assez similaire à celle en ordre, sauf la façon dont nous faisons les choses. Nous allons donc d'abord visiter l'extrémité de la racine vers le sous-arbre gauche et appelé préordre des lèvres. Leslie, nous allons traverser le sous-arbre droit. Précommande. La traversée de Postorder traverserait d'abord le sous-arbre gauche, appelait postorder du sous-arbre gauche, puis inverser le sous-arbre droit et appeler le postorder de celui-ci. Et ainsi, nous visiterions la racine. Vous voyez qu'une traversée de précommande consisterait à créer une copie de l'arborescence. Il est également utilisé pour obtenir expression de préfixe sur une arborescence d'expressions. traversée post-ordre serait utilisée pour supprimer une arborescence, elle serait également utilisée pour obtenir l'expression postfix d' un traitement d'expression. Si nous devions maintenant examiner le code qui effectuerait cette traversée en profondeur. Tout d'abord, la fonction principale, nous allons déclarer la racine, noter cela en utilisant une structure appelée nœud, et nous l'avons déclarée vers le haut. Nous avons un hôte intégré les données , puis deux pointeurs vers la note de type qui sont les enfants de gauche et de droite. Et aussi un constructeur qui prend une donnée de test intégrale, puis initialise les enfants de ces nœuds pour les connaître. On dirait donc qu'il a fui ou pas définitivement, mais juste pour le noter, pas d'enfants. Nous déclarons d'abord une racine, puis nous la donnons à gauche. Et vous savez, si deux bitrates indiquent trois, ce ne sont que des échecs, ce qui signifie qu'il n'y a pas deux échecs. Et puis à gauche, à gauche, nous avons un nœud avec la valeur fluor bien qu'ils aient essayé d'être noté la valeur de cinq. Voici à quoi ressemblerait notre arbre. Ensuite, nous appelons la précommande , l'ordre et le post-ordre de ces fonctions prend un argument, c' est-à-dire le nœud racine, par exemple, avec le post-ordre. Notez que je ne sais pas, évidemment, nous appellerons récursivement les enfants de gauche, puis les bons enfants, puis nous imprimerons les données. Ce que cela ferait, c' est qu'il sera appelé récursivement à gauche jusqu'à ce qu'il arrive à la feuille. Ensuite, il reviendra de récursion et l'emmènera bien. Puis enfin une valeur racine. Ensuite, vous avez également en commande, en précommande déjà réglée. Juste la différence, seule une différence entre ces instructions existe. Dans l'ordre. Encore une fois, vérifiez si le nœud n' est pas nul, car si cela signifie que vous avez déjà terminé l'arborescence ou qu'il n'y a pas d'enfants. Nous appelons ensuite récursivement la fonction du nœud gauche. Ensuite, nous imprimerons , puis nous appellerons récursivement le droit. La précommande. Évidemment. Nous vérifions encore, il faut connaître ces nano. Nous imprimons d'abord, puis appelons récursivement à l'extrême gauche. Et ensuite, pour parler de la complexité de ces algorithmes , venez sur scène. Pour tous les problèmes sont en fait une volt agréable côté serveur car essentiellement itérater. Remarque. Et l'espace auxiliaire, si vous ne tenez pas compte de la taille d'un état pour les appels de fonction, alors c'est constant, nous allons en faire un. Sinon, ce serait linéaire gros O de n. Parlons maintenant de la traversée de l'arbre binaire alter niveau, qui est une traversée de largeur en premier. Il existe donc différentes méthodes. Nous parlerons la méthode qui utilise une fonction pour imprimer un niveau donné. Encore une fois, il est largement essayé de faire ici est d'imprimer le nombre de nœuds dans l'ordre de niveau de gauche à droite sur les niveaux. Par exemple, pour le dernier arbre que nous avons vu, la traversée de l'ordre de niveau correspondrait à 12345. L'algorithme ici consisterait à implémenter deux fonctions. La première consiste à imprimer tous les nœuds à un niveau donné, donc nous leur donnons une pomme. L'autre fonction consiste à imprimer la traversée de l'ordre de niveau de l'arbre. L' ordre des niveaux vous permet de conserver les niveaux d'impression pour imprimer notes à tous les niveaux un par un à partir de la racine, nous ferions le premier ordre de niveau d'impression de trois. Passez d'une hauteur de l' arbre et imprimez ce niveau. Parcourez tous les niveaux et appelez le niveau d'impression donné. Laissez-vous prendre deux arguments, l'arbre et ce niveau, et l'imprimer. La fonction d'impression, impression au niveau donné. Nous vérifions si l'arbre est connu, puis il reviendrait. Si le niveau était un, alors il apporterait au monde entier. Et il appellerait récursivement niveau de l' arbre droit et gauche avec le niveau moins un. Comme vous pouvez le voir ici, nous avons créé la fonction pour créer une nouvelle fonction noeud qui retournerait la hauteur de l'arborescence. Les deux fonctions dont nous avons parlé. Comme je l'ai dit, la fonction d'ordre du niveau d'impression prend l'argument, la racine. Ensuite, nous calculerons avec la méthode de la hauteur la hauteur de l'arbre. Itérez tout au long de la hauteur et faites face au niveau de racine I, qui est le numéro du niveau auquel nous sommes actuellement. Et le niveau donné rose est une fonction qui prend le niveau et la note vérifie si la racine est nulle. Si c'est le cas, il reviendra. Si le niveau est égal à un, il imprimera le nœud racine. Parce que si nous sommes au premier niveau, cela signifie que nous sommes à la racine, nous l' imprimerions simplement de manière récursive en appelant n'importe quoi. Mais si nous sommes à un niveau inférieur, je ne suis pas le niveau racine, mais les téléchargements, nous appellerons récursivement cette fonction pour la gauche et la droite. Notez avec le niveau moins un. D'où le deuxième paramètre. Je pense donc que c'est assez simple. Encore une fois, vous pouvez voir pour l'arbre que nous avons montré à l'écran, la traversée de l'ordre de niveau est 12345 si nous l'avons déjà compris. Ici encore. La complexité de cet algorithme est linéaire. En ce qui concerne la complexité temporelle big O of n, comme nous parcourons tous les nœuds une fois récursivement, DC est à peu près la façon dont vous pouvez parcourir l'arbre de recherche binaire. Et ils sont très utiles à savoir car ils vous donneront plus de morbidité dans un arbre. Et ils s'assureront de vos ventes lorsqu'ils traiteront trois questions lors d'un entretien de codage. Passons maintenant au vecteur suivant. 19. Vérifiez la propriété de la somme pour les enfants: Bonjour les gars et bienvenue à ce cours. Dans cette conférence, nous parlerons des trois problèmes qui peuvent parfois apparaître dans une question d' entretien. C'est pour vérifier pour les enfants une propriété dans l'arborescence binaire. Cela signifie que, compte tenu d'un arbre binaire, vous devez écrire une fonction qui renvoie true si l'arborescence satisfait la propriété que pour chaque nœud, valeur de données doit être égale à la somme de thêta utilisée à gauche. et les bons enfants. Considérez que la valeur des données est 0. Pour l'instant, les enfants. Par exemple. Si nous avions un arbre qui aurait la racine, alors les enfants de gauche auraient huit ans et les bons enfants seraient deux. Ce serait un arbre valide. Et ainsi de suite, si cet enfant ayant besoin d' avoir deux enfants, main gauche essaie au moins que leurs données dans certains devraient être égales à huit, et ainsi de suite pour l'arbre entier. L'algorithme que nous sommes, nous allons aborder ici est de parcourir l'arbre binaire donné. Et pour chaque nœud, nous devrions vérifier récursivement si le nœud alors ces deux enfants ont dit est par la propriété children some. Si c'est le cas, alors vrai sinon renvoie false. C'est assez simple. Ne passons pas dans le code et voyons comment le faire à un niveau technique plus spécifique. Très bien, nous avons déjà déclaré des choses qui nous aideraient à implémenter l'arbre. Nous avons donc déclaré une structure noeud. Et puis nous avons déclaré qu'un arbre entier est une propriété de la racine deux. Ensuite, nous imprimerons que la condition est satisfaite, sinon fausse. Nous allons donc implémenter une fonction appelée East certaines propriétés. Il prend le paramètre le nœud racine et renvoie un entier, qui pourrait aussi bien être booléen, est la même chose car si vous renvoyez 0 ou un, puis sautez dans cette fonction, nous déclarons deux variables auxiliaires qui nous aideront à mémoriser les valeurs droite et gauche des enfants du nœud que nous sommes actuellement avec l'itération. Ensuite, si le noeud que nous sommes honnêtes ou ses enfants ou non, alors nous en retournerons un. Parce que cela signifie que nous avons atteint la fin et que c'est normal parce que tout était vrai jusqu'à ce moment-là. Sinon, vous verrez également que la majorité de ces algorithmes commencent par le cas de base de cet algorithme d' arborescence. Tout d'abord, notre récursif et deuxièmement, commencez par le cas de base, c'est-à-dire le cas final. Eh bien, nous avons plusieurs scénarios ici. Si le nœud gauche n'est pas nul, alors les données qu'il contient, sorte que le numéro qu'il contient sera donné à l'intégrale bêta gauche que nous avons déclarée ici. Encore une fois pour le bon nœud, nous ferons la même chose. Ensuite, nous vérifierons si les données du nœud, sorte que le nombre que nous sommes actuellement avec l'itération est égal à la somme des enfants gauche et droit. Et aussi appelé récursivement la même fonction pour le nœud gauche et le nœud droit. Nous allons vérifier récursivement la même chose pour les deux enfants du nœud. Ensuite, nous allons en retourner un, ce qui signifie que c'est vrai. Et nos trois années, avec cette condition que nous vérifions, sinon nous retournerons 0. Ce que cela fait, c'est appeler récursivement en utilisant la pile de coûts. Et quand il reviendra de la pile d'appels, il frappera celui-ci. Si toutes les propriétés ECM retournent true, comme vous pouvez le voir ici avec les instructions finales, toutes doivent être vraies pour que cette instruction if puisse en extraire et en renvoyer une. C'est ainsi que nous allons vérifier cette condition dans l'ensemble de l'arbre avec une fonction récursive. Parlons maintenant de la complexité de cet algorithme, comme vous allez le voir dans presque tous les algorithmes d'arborescence. Linéaire du point de vue temporel et constant de ce point de vue de base nous n'avons déclaré que deux intégrales. Mais du point de vue, parcourez tout l'arbre. Donc c'est linéaire gros O of n. Merci d'être restés jusqu'au bout avec moi sur ce tutoriel et je vous verrai dans le prochain. 20. Les nœuds de tous les nœuds: Bonjour les gars et bienvenue à ce cours. Dans cette conférence, nous parlerons d'un autre problème d'arbre. Donnons-les parfois dans le calcul de la somme de tous les nœuds d'un arbre binaire. Je pense que le titre est assez explicite. Ce que vous devez faire lorsque vous rencontrez ce problème est de fournir un algorithme permettant de trouver la somme de tous les éléments de l'arborescence binaire. En gros, vous devez résumer toutes les intégrales détenues par tous les nœuds d'une arborescence binaire qui vous est donnée. Comme d'habitude, nous aborderons cet algorithme avec récursion comme nous le faisons habituellement dans trois problèmes. Examinons le code pour voir comment nous ferions ce problème. Nous avons déclaré une structure. Notez que le maintient inducteur est la clé et aussi la gauche et la droite du nœud qui sont conservées. En leur donnant un pointeur sur la structure des nœuds. Nous avons dessiné un arbre ici. Ensuite, nous avons déclaré par une partie intégrale et nous lui avons attribué notre appel de fonction qui est censé renvoyer l'intégrale. Cette intégrale étant la somme de tous les nœuds de l'arbre donné, seul paramètre T que cette fonction prend est le noeud racine de notre arbre. Pointeur sur le nœud. Évidemment. C'est comme si root est nul, alors nous devrions renvoyer 0. Comme d'habitude dans trois algorithmes et méthodes de récursion, nous commençons par le scénario de base, ce qui signifie que se passe-t-il lorsque le bas appelle cette chaleur ? Quand root est non, nous avons atteint la fin. n'y a donc plus de note car nous appelons cette fonction de manière récursive jusqu'à ce que nous manquions de nœuds. Si ce n'est pas le cas. Donc, si nous n'avons pas atteint un itinéraire, nous devrions renvoyer la clé racine, ce qui signifie la valeur que la racine conserve à l'intérieur de la car vous pouvez voir la structure, la clé est celle que contient le nœud intégré. Nous ajoutons également le cours récursif de cette fonction pour l'enfant gauche et droit de la racine, c' est-à-dire la note que nous y sommes. L'appel actuel, bien sûr, le plat récursif sera appelé pour les enfants de gauche. Et là encore, l'exécution a commencé sans retour. 0 IS renvoie sa valeur , puis appelle à nouveau récursivement chacun d'entre eux. Je pense que vous avez compris comment ça se passe. Nous parlons maintenant de la complexité de cette rangée capturée. Eh bien, la complexité temporelle est linéaire, car nous parcourons tout l'arbre est assez intuitif que nous devons parcourir chaque nœud afin savoir quelle valeur elle est fidèle à nous-mêmes. Et puis la complexité de l'espace est constante car nous ne déclarons aucun autre élément que les standards de Carsten vendus, mais c'est un gros O of one. Merci les gars, et nous nous verrons lors de la prochaine conférence. 21. Vérifiez que toutes les feuilles sont de même niveau: Bonjour les gars et bienvenue à ce cours. Dans cette conférence, nous parlerons de trois autres problèmes qui pourraient être abordés dans un environnement d' entrevue. C'est pour vérifier si toutes les feuilles sont au même niveau dans un arbre. Dans ce problème, nous vous demanderons faire un arbre binaire, vous suffit de vérifier si tous les nœuds quittent, est-à-dire les nœuds qui n'ont pas d'enfants. Ainsi, ceux qui sont au niveau inférieur, au même niveau ou non, imaginent essentiellement que la racine soit au premier niveau, que les enfants immédiats soient au niveau deux, etc. Jusqu'à ce que vous trouviez le niveau des feuilles, c'est normal, nous aborderons cet algorithme en utilisant la récursion. Maintenant, l'idée est de trouver d'abord niveau de la feuille la plus à gauche et de la stocker dans une variable. Et nous utiliserons cette variable. Comparez ensuite le niveau de tous les autres congés avec le niveau d'endettement. Si c'est la même chose, nous reviendrons à la fin sinon fausse. Nous parcourons l' arbre binaire donné en précommande. Le niveau que nous gardons à l'esprit, nous serons les meilleurs pour tous les appels en guise d'argument. La valeur de cet argument est initialisée avec 0 dans une autre fonction pour indiquer que, abord, s'il n'est pas encore vu, la valeur est au plan. abord, trouver une feuille ou un niveau de feuilles ultérieures en préordre est comparé à cet argument de niveau. Jetons maintenant un coup d' œil au code. Nous avons déclaré la structure du nœud et le constructeur correspondant. Et dans la fonction principale, a construit trois pour nous. Ensuite, nous avons une fonction appelée check qui prend la racine de notre arbre. Et ce qu'il fait, c'est qu' il initialise le niveau en feuille avec 0 et renvoie le code à cette vérification, une fonction qui prend comme paramètres la racine de notre arbre, puis le niveau et le niveau feuille. qui sont tous les deux initialisés avec 0. Comme vous pouvez le voir dans cette vérification jusqu'à la fonction. Le cas de base est quand nous avons une racine, c'est maintenant. Et ensuite, nous devrions revenir vrai. Ensuite, les enfants du nœud que nous sommes actuellement sont tous les deux nuls. Cela signifie que nous sommes arrivés à un nœud foliaire. Ensuite, nous vérifions si c'est la première fois que nous arrivons au nœud de la feuille. Pour ce faire, nous vérifions si le niveau de feuille est 0, comme vous pouvez le voir ici, il est passé par référence, sorte que la valeur de celui-ci reste. Celui lorsque nous appelons le niveau de feuille est 0. Cela signifie que c'est la première fois que nous rencontrons une feuille, nous assignons à ce niveau de feuille, le niveau auquel nous sommes actuellement. De plus, si nous ne saisissons pas cette instruction if, nous renvoyons le niveau égal au niveau feuille. Ce que cela signifie, c'est que nous sommes à la tête. Ce qui est maintenant le premier, si nous avons raison, nous devrions revenir si le niveau est égal au niveau des feuilles. Le niveau des feuilles est le niveau réel de la première feuille à laquelle nous sommes arrivés. Toutes nos feuilles doivent être au même niveau. C'est pourquoi nous gardons à l'esprit cette variable ici. Ensuite, en quittant cette instruction if, signifie que si ce n'est pas une feuille sur laquelle nous sommes, moment, nous retournons des appels récursifs de cette fonction pour les nœuds gauche et droit. Parce que nous sommes actuellement au nœud qui n'est pas une feuille et Xist, ce qui signifie que nous sommes à un nœud parent. Nous devons appeler cette fonction de manière récursive pour ces deux enfants et augmenter le niveau. De plus, tout en gardant à l' esprit le niveau des feuilles, c'est le niveau le plus bas de la première feuille que nous ayons jamais rencontrée. Comme je l'ai déjà dit, je vais insister sur ce point. Une fois encore. Nous nous souvenons de cette dette au niveau des feuilles, le niveau de la première feuille que nous avons rencontrée. Et c'est la référence que nous allons vérifier. De plus, l'inode des feuilles que nous rencontrerons pour la complexité de cet algorithme. Encore une fois, la complexité de l'espace est constante. Nous n'utilisons pas d'espace supplémentaire plus grand qu'un. Ensuite, la complexité temporelle est linéaire. Lorsque nous traversons l' arbre entier pour trouver d'abord le niveau de la première feuille, puis vérifier que toutes les autres feuilles ont le même niveau à la première feuille que nous rencontrons. Merci d'avoir regardé ce tutoriel et je vous verrai dans la section suivante. 22. Le problème des parenthèses: Bonjour les gars et bienvenue à ce cours. Dans cette conférence, nous parlerons du problème que l'on pose très souvent dans une question d' entretien. Il s'agit de vérifier la présence de crochets équilibrés dans une expression à l'aide d'une pile. Eh bien, c'est fait à l'aide d'une pile, mais l'intervieweur pourrait ne pas traiter. Vous avez fait ce problème en utilisant cette prise ce soir, je l'ai compris par vous-même. Le problème vous donne une chaîne. C'est une expression, et vous devez écrire un programme pour vérifier si les paires et les ordres des crochets, corrects dans cette expression, les parenthèses peuvent être actuellement normaux ou carrés. Par exemple, je vais maintenant mettre à l'écran deux entrées différentes. Vous pouvez donc voir que le premier est équilibré et que le second ne l'est pas. Vous ne pouvez pas fermer le crochet carré avant de fermer le support normal car il n'y a pas l'ordre naturel. Quel serait l'algorithme de nous déclarer un deck qui contient caractères, puis de parcourir l'expression à laquelle vous avez reçu cette chaîne, fait une itération à travers elle. En dendrite, deux scénarios. Tout d'abord, si le caractère actuel que vous parcourez à ce moment est le crochet de démarrage, le crochet de démarrage normal, crochet bouclé de démarrage ou le crochet carré de départ, vous pouvez le pousser sur ce deck. Le deuxième scénario est si le crochet actuel sur lequel vous êtes actuellement avec itération est un crochet de fermeture. Encore une fois, une fermeture des crochets normaux, fermeture du support carré, la fermeture du support bouclé. Puis sortez de ce deck. ce moment, vous pompez l'élément supérieur et vous allez voir quel est le dernier support ouvert. Et si le personnage pop, donc le dernier crochet ouvert est le crochet de départ correspondant, alors tout va bien. Les supports ne sont pas équilibrés. Donc, après une traversée complète, s'il y a un support de départ qui laisse ce deck, alors il n'est pas équilibré car dans notre chaîne il y a crochets ouverts que je n'ai pas été près de la fin du expression. Examinons rapidement les codes. Nous avons une fonction principale et la lecture exercent une expression qui va comme commencer une accolade bouclée, commencer une accolade bouclée, commencer une accolade normale, terminer l'accolade normale et l'accolade bouclée. Donc, c'est bon. Puis démarrez le support carré, terminant le support carré. doit s'agir d'une expression équilibrée car il n'y a pas de crochets laissés , ouverts ou fermés dans le mauvais ordre. Maintenant que nous avons une fonction appelée, nous déclarons que la fonction appelée nos crochets est équilibrée que nous allons voir qu'elle a un paramètre, cette chaîne. Nous déclarons une pile, comme nous l'avons déjà expliqué pourquoi elle contient le type de données char. Ensuite, nous déclarons un graphique auxiliaire appelé X. Pour int i de 0 à la longueur de l'expression. Nous parcourons essentiellement avec cette boucle chaque caractère de l' expression donnée. Nous prenons chaque personnage un par un et vérifions quel type de crochets ces personnages. abord, nous devons voir si ce support est actuellement carré, est normal et qu'il commence dans le type 1. Si c'est le cas, nous pouvons le pousser dans notre pile et continuer car nous n' avons pas besoin d'aller avant avec le reste de l'exécution de la boucle. Sinon, s'il ne s'agit pas d'un support de démarrage, nous pouvons vérifier si la pile est vide. Et si la pile est vide, nous devrions renvoyer false. Parce que cela signifie qu'il s'agit d'un support de fermeture. Est-ce qu'il ne peut pas être un crochet de départ parce que si c'était le cas, l'exécution ne serait pas ici, en ce moment. Il s'agit d'un support de fermeture et la pile est vide. Qu'est-ce que cela signifie ? Cela signifie que nous sommes arrivés à un support de fermeture qui n'a pas de support de départ correspondant avant lui. Il ne s'agit donc pas d'une expression valide des parenthèses. Si ce n'est pas le cas, nous avons une instruction switch basée sur le caractère que nous sommes actuellement dans notre expression. Nous avons donc des cas différents. Le cas où notre personnage est un crochet normal de fermeture, nous allons le faire. Dans notre personnage auxiliaire x, le haut de la pile. Et ensuite, nous sauterons en haut de la pile car nous n'en avons plus besoin. Ensuite, nous allons vérifier la valeur qui s'y trouvait. Si la valeur a été vue, il s'agissait d'un crochet bouclé départ ou d'un crochet carré de départ. Ensuite, nous devrions renvoyer false lorsque nous arrivons à un crochet normal de fin et en énumérer un qui était ouvert, de sorte que le crochet correspondant n'était pas du même type que les EDS. Ensuite, nous devrions rompre. Dans les autres cas, s'il s'agit d'un crochet bouclé qui se termine, le crochet correspondant de départ est OK. Les deux autres types, ça ne va pas, donc nous devrions retourner faux. Encore une fois, s'il s'agit d'une parenthèse quadrillée terminale et que sa parenthèse correspondante est normale ou bouclée. Encore une fois, ce n'est pas une expression valide, donc nous devrions renvoyer false puis casser. La même procédure s'applique également, où nous mettons dans notre personnage auxiliaire le haut de la pile, puis nous la faisons apparaître. Lorsque nous avons terminé l' itération, notre pile doit être vide. ne devrait donc pas y avoir de parenthèse ouverte, car cela signifie qu'elles n'ont aucune parenthèse finale correspondante. Si la pile est vidée signifie que tous les marchés ont correspondu. Et l'expression est valide. Si la chaîne n'est pas vide à la fin de l'exécution, cela signifie qu'il y a des éléments. Et comme vous l'avez déjà vu, nous n'y poussons que des types de supports de départ. Et cela signifie qu' il y a des crochets de départ laissés qui n'ont pas de crochets de fin correspondants. Cela signifie que ce n'est pas une expression valide. Cette fonction est donc appelée dans une instruction if. Donc, si cette fonction ici, ce qui signifie que cette fonction retourne vraie, nous pouvons revenir que l'expression qui nous est donnée est une expression équilibrée. Sinon, ce n'est pas équilibré. Ainsi, comme vous pouvez le voir, exemple de connaissances, si nous exécutons le code, vous pouvez voir qu' il est équilibré, donc c'est une expression équilibrée. Parlons maintenant de la complexité de cet algorithme. La complexité de cet algorithme d'un point de vue temporel, c'est linéaire alors que nous parcourons notre expression une fois. C'est donc le gros O de n. Maintenant, la complexité de l'espace est également linéaire car nous avons déclaré une pile pouvant contenir autant que toute la chaîne. Dans le pire des cas où la chaîne contient des crochets de départ. Vous pouvez le faire de manière plus efficace lorsque vous ne vous souvenez même pas de ce deck. Et au lieu de ce deck, vous pouvez vous souvenir de quelques chiffres. Par exemple, certaines variables que vous incrémentez lorsque vous rencontrez une parenthèse de départ et que vous décrémentez lorsque vous rencontrez une parenthèse de fin. Il s'agit d'une solution plus avancée. Vous pouvez l'essayer chez vous ou le chercher. Mais la solution de base pour ces problèmes, celui-ci et celui-ci, vous devriez vraiment comprendre et connaître par cœur. Mais merci de vous en tenir à ce tutoriel jusqu'à la fin. voit la prochaine fois.