Transcription
1. Introduction: m'appelle Sarnoff, et je suis un ingénieur logiciel de pile complète et instructeur d'ingénierie. J' ai dit à l'ingénierie logicielle dans un camp de démarrage de codage, et quelque chose que j'ai remarqué à plusieurs reprises était que les étudiants diplômés, bien que extrêmement lumineux et capable de construire des sites Web puissants, dynamiques, n'
étaient pas prêts pour le types de questions qu'ils ont vues au cours de leurs entrevues. Après avoir vu ces élèves se battre avec des questions d'entrevue typiques, j'ai décidé de créer et de recueillir des questions que les élèves pourraient voir dans leurs entrevues. Et je les ai distribués. Était une pratique supplémentaire pour les étudiants à essayer. Ils m'ont dit à maintes reprises à quel point les problèmes les ont aidés à voir les lacunes de leurs connaissances et à les faire tomber avec les compétences dont ils avaient besoin. Ce cours est le point culminant de ces questions. Presque tous ces problèmes sont des variations sur des questions qui m'ont été posées moi-même ou que d'autres que je connais ont été posées lors d'entrevues. Eh bien, vous ne verrez pas ces questions exactes dans vos interviews. Les stratégies que vous apprendrez en les résolvant notre public sont applicables à presque tous les problèmes qui vous seront donnés. Voici la structure générale du cours généralement commence par créer un
algorithme de force brute qui résout bien le problème,
puis l' affiner jusqu'à ce que nous puissions optimiser la complexité du temps ou de l'espace ou les deux. À la fin du cours, vous aurez maîtrisé plusieurs stratégies algorithmiques que vous pouvez appliquer à un large éventail de problèmes. Nous allons apprendre des façons d'analyser de manière critique les algorithmes que nous proposons et de les trouver, de les
transformer pour réduire le temps qu'ils prennent. C' est exactement ce qu'un intervieweur cherche. Il y a quelques exigences pour ce cours. Hum, abord, vous devriez avoir une connaissance pratique de base du JavaScript et la capacité d'écrire du
code significatif avec lui. Vous devriez également être familier avec les concepts de base ES 2015, comme une fonction zéro et les mots-clés Let et Const. Vous devriez avoir une idée de ce que signifient les termes, la complexité du
temps et de l'espace. C' est bon si vous ne savez pas exactement ce qu'ils sont, puisque nous allons les trouver en détail pour chaque solution. L' éditeur de code que j'utilise dans mes vidéos est Ripple. Euh, vous pouvez y arriver en allant à rebelle dot i t slash langages slash javascript, et la raison pour laquelle je l'utilise est parce que c'est simple et fonctionnel, et nous allons vous concentrer sur votre code, mais vous êtes bien sûr, libre d'utiliser n'importe quel éditeur de code que vous aimez. Le projet de ce cours est de choisir l'un des problèmes abordés dans la classe. Il y a un total de cinq listés ici et partagez votre propre solution. Il y a 1000 façons de résoudre l'un de ces problèmes et la classe bénéficiera de voir votre version. Bienvenue au cours. Je suis excité de vous apprendre ce que je sais et de vous aider à faire vos interviews. Quand tu seras prêt, je te verrai au premier problème.
2. Personnages uniques: bienvenue à son premier problème est unique. Le but ici est d'écrire une fonction qui prendra une chaîne et de déterminer si chaque caractère de cette chaîne n'apparaît qu'une seule fois. Essentiellement, nous essayons de voir si chaque caractère de la chaîne est unique dans cette force. Nous voulions tenir compte de la casse, ce qui signifie que les versions minuscules et majuscules d'une lettre dans la même chaîne sont considérées comme uniques. Voici quelques exemples. Nous obtenons une chaîne normale A, B, C, D E f, et tout est unique, donc nous voulons que la fonction revienne. Vrai. Cet exemple suivant montre simplement que nous voulons que notre fonction soit capable d'accepter une chaîne avec n'importe quel type de caractère, pas seulement des lettres. Encore une fois. Ils sont tous uniques. Donc on devient vrai. Ce troisième exemple montre encore une fois qu'un A minuscule dans une majuscule A dans la même chaîne serait toujours que nous voulions que notre fonction retourne. True pour cette entrée, le 4ème 1 montre un huit minuscules en double et sa fonction renverrait false. Allons-y et commençons à écrire cette fonction tout de suite. Donc, pour nous assurer que chaque caractère de notre chaîne est unique, nous allons devoir traiter chaque caractère de la chaîne, donc nous savons que nous allons devoir faire une boucle. Allons-y et commençons par là. Que voulons-nous faire dans cette boucle ? Eh bien, une stratégie que nous pouvons employer est la suivante. Notre boucle ici va passer par une chaîne de gauche à droite. Donc, en prenant ceci comme exemple, nous allons commencer par un. Ce que nous pouvons faire, c'est que nous pouvons avoir une autre boucle allant de droite à gauche à la recherche du même personnage. Donc, pendant que notre boucle externe est sur un, nous pouvons avoir une boucle interne allant de droite à gauche. Aussi à la recherche d'un si il le trouve et ce n'est pas dans la même position que la boucle externe est à, nous savons que nous avons un doublon et nous pouvons immédiatement retourner false. S' il n'y a pas de doublon, cela va courir jusqu'à ce qu'il arrive à l'A ici, et nous savons que c'est unique dans la rue. Nous pouvons répéter cela allant de gauche à droite comme notre deuxième boucle va à droite orteil droit à gauche. Pour chaque cas individuel, cela peut sembler compliqué, mais il y a une petite méthode qui nous rend très simple pour nous. Écrivez-le et discutez-le juste après le dernier index. Cela fera exactement ce que je viens de décrire. Il passera par la corde orteil droit gauche, la
recherche du personnage que nous fournissons dans ce cas, quel que soit le caractère que je suis actuellement sur. Donc encore une fois, nous lui donnons un dans ce cas pour le tout premier tour, et il va passer à droite à gauche en cherchant un Donc ce que nous faisons est de nous assurer que le dernier index de A est le même que l'index actuel qui étaient sur. Cela montrera que le caractère n'est pas dupliqué dans la chaîne. Si, cependant, le dernier index de A n'est pas le même que le premier index d'un, alors nous pouvons immédiatement retourner faux Um, c'est vraiment toute la logique dont nous avons besoin à la fin de la fonction, nous pouvons retourner vrai, il n'arrive ici qu'après avoir traité chaque personnage ici et s'est assuré qu'il n'y a pas de doublons, travail
dysfonctionnel. Allons de l'avant et le code du coureur ici, et nous nous attendons à voir
vrai, vrai, vrai, faux et c'est exactement ce que nous voyons apparaître afin que notre fonction fonctionne correctement. Passons à travers la complexité temporelle de cette fonction afin que nous puissions voir que nous avons une boucle for et que cela apporte immédiatement notre complexité temporelle à O of n parce que chaque caractère
est traité ici. Nous avons en fait une autre boucle sous la forme du dernier index de Well, ce n'est pas une boucle que nous avons écrite. C' est une boucle qui traverse la chaîne de droite à gauche. Donc c'est en fait un autre o de fin. Puisque cela est imbriqué à l'intérieur de la boucle externe, nous devons multiplier ces complexités temporelles pour donner une complexité temporelle finale de O de
n fois n oh de n carré. Quelle est la complexité de l'espace ? Eh bien, réfléchissons à ça. Peu importe la durée de la chaîne, qu'il
s'agisse de trois caractères ou de 30 ou 300, nous n'utilisons jamais qu'une seule variable dans notre
fonction entière . Et c'est-à-dire que je ne stockais qu'un personnage à la fois. Peu importe la taille de l'entrée, notre fonction prend la même petite quantité d'espace. Donc, nous disons qu'il utilise un espace constant, ou O d'un. C' est tout pour cette version. La solution. Pouvons-nous améliorer un peu la complexité du temps ? Oui, on peut. Allons-y et essayons ça. Il y a quelque chose que nous pouvons faire avant de passer par notre chaîne pour le rendre un peu plus simple , nous pouvons trier notre chaîne. Allons-y et essayons ça. Donc, ce que j'ai fait jusqu'ici, c'est que je prends la chaîne et la divise en un tableau. C' est ce que fait cette méthode dot split avec une chaîne vide ici. Donc, à ce stade, voitures seraient juste égales à un tableau de caractères individuels dans la même ligne que nous l'
accordons . Les caractères seront désormais tous triés de gauche à droite. Donc, si on nous donnait quelque chose comme D B A C, on dirait qu'il aurait un tableau. Ce serait maintenant un tableau de A,
B, B, C et D. Simple est que que pouvons-nous faire maintenant que nos personnages sont triés ? Eh bien, il y a une autre logique que nous pouvons appliquer pour rendre cela beaucoup plus facile. Nous allons encore avoir besoin de la norme pour boucle. En fait, j'allais commencer par un pour celui-ci, et nous allons expliquer pourquoi dans une seconde maintenant. Mais je ne sais pas ce que les personnages sont triés individuellement. S' il y a des doublons, ils vont être placés juste à côté de l'autre à nouveau. En supposant que nous ayons D B A. C A. Cela va maintenant se transformer en B C D.
Les deux doublons apparaissent l'un à côté de l'autre. Donc, ce que nous voulons faire est pour cette chaîne, ou plutôt, ce tableau de caractères. Nous voulons commencer par le deuxième personnage, et ce que nous voulons faire est de le comparer au personnage qui l'a précédé. Si elles sont identiques, c'est un duplicata, et nous pouvons immédiatement retourner faux. Cordons ça. C' est ça. Cette fonction fonctionne parfaitement. Laissons-le juste pour être sûr à nouveau, nous attendons Vrai,
Vrai, Vrai , Faux. Et c'est exactement ce que nous obtenons. Allons nettoyer un peu ça. Et encore une fois, parlons des complexités temporelles et spatiales. Donc, dans ce cas, nous commençons par un magasin juste ici. Maintenant, différents algorithmes de tri ont des complexités temporelles différentes, mais en général, si nous parlons d'une épée, nous pouvons supposer la complexité temporelle de O des temps de fin. Journal de n Ceci est une boucle standard. Ce sera juste Oh, de N parce que ces choses se passent séquentiellement et nous n'avons pas de boucle à l'intérieur d'une boucle. Nous pouvons simplement les ajouter. On va commencer par O of M Times. Un journal de fin plus o de N, qui se transforme en oh de N plus n fois le long de End et N est un terme d'ordre inférieur à ce juste ici. Simplifions cela plus loin pour montrer exactement ce que cela signifie quand nous parlons de temps, les complexités s'affaiblissent. Éliminez simplement les termes d'ordre inférieur afin que nous puissions nous débarrasser de ce plus et notre complexité finale du temps finit par être exactement ceci. Oh, de la fin des temps longs d'entre eux et que leur complexité de temps pour cette solution. Et l'espace ? Auparavant, c'était plus d'un, mais maintenant nous prenons chaque personnage et nous le stockons à la hâte. C' est ce qui se passe ici. Nous stockons donc chaque caractère, ce qui signifie que nous prenons la même quantité d'espace que la taille de l'entrée. Donc ça va être, oh de, et nous parlerons de deux autres solutions dans la prochaine vidéo. On se voit là
3. Traitement rapide des chaînes de chaîne: bienvenue à son unique. Nous avons maintenant passé en revue deux solutions, et nous avons réussi à améliorer la complexité temporelle de O of and quadrillé Thio of End Times. Journal de fin. Nous accomplissons cela en triant la chaîne que nous obtenons comme une entrée. Nous pouvons en fait améliorer la complexité de notre temps. Et cela nécessitera une stratégie différente. Allons de l'avant et effacons tout cela et recommencez. Donc la dernière fois que nous avions trié la chaîne. Vous voulez faire quelque chose de différent Cette fois, nous allons créer un objet pour stocker les personnages au fur et à mesure que nous les rencontrons à nouveau. On va avoir besoin d'une boucle qui traverse notre chaîne et ça n'aime pas quelque chose. 04 boucle. Donc, ce que nous voulons faire est de vérifier si notre objet contient déjà une copie du
travail de caractère en cours de traitement. C' est ça. C' est en fait tout le problème est juste que. Exécutez à nouveau et assurez-vous que cela fonctionne bien. Et cela ne fonctionne pas bien. Qu' est-ce qui se passe ? Uh, a retourné False ici. Cela doit être vrai. On y va. Mes excuses. Alors passons à travers ce qui se passe ici une fois de plus en passant par chaque personnage, par
exemple, Prenons cette chaîne ici. ABC A e f. Nous allons traiter chaque élément individuellement. Donc, la toute première fois que nous traversons
cette boucle, cette voiture va être une Nous allons vérifier si notre objet le contient déjà. Et si c'est le cas, nous voulons retourner les chutes. Notre objet est vide au début. Donc ce chèque passe et nous passons à ici. Nous allons stocker un dans notre objet. Nous allons juste définir sa valeur égale à true. Donc, notre objet contiendra tous les caractères que nous avons déjà traités jusqu'à présent. Comme nous passons par la chaîne, nous allons ajouter dans un et puis B et puis voir quand nous arrivons à la prochaine a étaient à nouveau
aller vérifier si les voitures a le caractère A Et si ce aigles vrai, car il le fait, parce que nous avons déjà vu et nous l'avons déjà inséré dans notre objet. Nous savons que c'est un duplicata et nous pouvons immédiatement retourner faux. Si nous passons à travers cette boucle entière, nous savons qu'il n'y a pas de doublons et la chaîne et nous pouvons retourner true. C' est ça. Parlons de la complexité temporelle dans cette version de cette fonction. Nous n'avons qu'une boucle. Nous traversons chaque personnage et à mesure que nous traversons chaque personnage, les choses que nous faisons ici sont un temps constant. n'y a plus de boucles ou quoi que ce soit de cette nature. Donc nous avons une seule boucle qui nous donne une complexité Tom de O de N. Qu'en est-il de l'espace ? Eh bien, chaque personnage devient à travers est stocké dans notre objet. Donc, l'espace va aussi être un amour N parce qu'il est proportionnel à la taille de l'entrée. Il y a un moyen de changer un peu ça. Au lieu d'un objet, nous allons utiliser une construction E S 2015 appelée un ensemble, maintenant un ensemble similaire à un objet. Sauf que c'est plus approprié pour cette tâche exacte, soudainement comme une structure de données destinée à contenir des éléments uniques. Allons de l'avant et regardons l'ensemble de la page indienne quatre comme nous pouvons le voir, un ensemble, est un objet qui vous permet de stocker des valeurs uniques de n'importe quel type, euh, dans un ensemble. Ainsi, une valeur dans un paramètre ne peut apparaître qu'une seule fois, et elle est unique dans la collection sets. Il s'agit donc d'une structure de données spécifiquement faite. Essentiellement, pour ce problème, nous avons juste besoin de changer quelques choses. Par exemple, Au lieu de cela, nous devons utiliser une méthode intégrée et la même chose ici au lieu de définir. Au lieu de définir notre article sur true, nous allons simplement l'ajouter dans l'ensemble. On n'a pas besoin de ça. Et nous n'avons pas besoin de ça. Et encore une fois pour s'assurer que cela fonctionne. Cela nous donne en effet ce que nous voulons. Vrai, vrai, vrai, faux. Encore une fois, Ceci est très similaire à un off à la méthode que nous avions auparavant avec un objet. La seule différence est que nous avons échangé ou la structure de données. Et il y a en fait une très bonne raison pour laquelle nous avons fait ça. Cela nous permettra d'écrire notre solution d'une manière nouvelle et encore plus simple. Et nous en parlerons dans la prochaine vidéo. Tu vois, là
4. Personnages uniques : Simplicité ultime: bienvenue à son unique. Nous avons maintenant abordé trois façons différentes de résoudre ce problème. Pour la dernière méthode, nous avons montré comment le faire avec un objet et un ensemble. Vous vous demandez peut-être pourquoi je vous ai montré cet ensemble. Il fait la même chose qu'un objet, et il n'offre vraiment rien de nouveau. C' est juste une autre chose pour nous d'apprendre et de nous habituer. Eh bien, je veux vous montrer le vrai pouvoir derrière un ensemble, et je veux vous montrer comment il peut rendre notre solution beaucoup, beaucoup plus simple. Alors avant de faire quoi que ce soit, plongons dans certaines des propriétés d'un ensemble. allons juste en créer un nouveau ici et jetons quelques éléments afin que nous lui donnions un tableau avec les nombres un à cinq, et sortons cela. Donc, comme vous pouvez le voir, lorsque nous nous donnons un tableau, il prendra chaque élément individuel dans le tableau. Un ajouté dans l'ensemble. Maintenant, ce qui n'était pas intuitif, moins pour moi, était ce qui se passe quand on lui donne une chaîne à la place ? Espérons donc aller de l'avant et se débarrasser de cela et plutôt lui donner la chaîne A B C D e. Comme vous pouvez le voir, ce qui s'est passé est chaque caractère individuel de la chaîne a été inséré dans l'ensemble. Un par un, la corde a essentiellement été divisée. Pour nous, c'est très important. Il y a une autre chose que je veux souligner et c'est la propriété de taille. Donc, une chaîne a une propriété length, qui vous indique le nombre de caractères dans la chaîne. Un ensemble a une propriété size qui indique simplement le nombre d'éléments dans l'ensemble. Donc, comme prévu, c'est cinq parce que nous avons cinq objets différents dans l'ensemble. Je veux vous montrer une autre chose, qui est ce qui se passe si nous ajoutons des doublons. Laissez-moi aller de l'avant et ajouter ABC à nouveau et nous l'exécutons et nous voyons que la sortie ici est exactement la même parce que set à nouveau ne peut contenir que des éléments uniques. Et les caractères A, B et C sont déjà là. Donc, il ignore complètement les trois. Et l'ensemble contient cinq objets comme nous pouvons le voir ici. Allons de l'avant et revenons à notre problème. Je vais effacer tout ça et je vais écrire une ligne de code et on en parlera juste après. C' est en fait la solution entière. Et laissez-moi courir ça juste pour montrer que ça marche. Et c'est le cas. Allez-y et testez-le par vous-même si vous le souhaitez. Ça marchera à chaque fois. Discutons pourquoi c'est comme indiqué avant ici. Si nous sommes des doublons dans l'ensemble, ils seront complètement ignorés. C' est ce qui se passe ici. Nous insérons une chaîne dans l'ensemble, et chaque caractère individuel est inséré dans l'ensemble ont alors vérifié pour voir si la taille de l'ensemble est la même que la longueur de la chaîne d'origine. S' il n'y avait pas de doublons que la taille de l'ensemble, devrait être exactement la même que la longueur de la chaîne. Cependant, s'il y avait des doublons sur le règlement, être légèrement plus petit. En retournant cette comparaison directement, nous avons résolu l'ensemble du problème si leur unique cette égalité du vrai et du
retour fonctionnel vrai. S' il y a des caractères en double, cette égalité ne tiendra pas et la fonction retournera false à nouveau. Passons en revue la complexité du temps et de l'espace pour cette fonction. Nous prenons une chaîne et nous l'ajoutons dans le caractère défini par caractère. C' est une opération linéaire. Donc, c'est O de l'espace de fin à nouveau ajoutaient chaque caractère individuel dans l'ensemble, donc il va être proportionnel à la taille de la chaîne. Donc, une fois de plus, oh, de n nous allons rapidement finir en parlant de tout ce que nous avons couvert jusqu'à présent. La première solution que nous avons trouvée était la solution de force brute qui avait un serment et complexité temporelle au
carré, c'était simple simple. Et c'est la première solution que la plupart des gens viennent avec. Si vous pouvez identifier la complexité du temps et ensuite travailler à l'améliorer,
vous devrez faire face à cette question lors d'une entrevue. La deuxième solution consistait à trier la chaîne. abord, c'était mieux en termes de temps, complexité, mais nous avons dû augmenter la complexité de l'espace pour cette solution. Les troisième et quatrième solutions sont idéales. Nous avons la complexité temporelle la plus faible, et nous la réduisons jusqu'à la fin, ce qui est une amélioration très significative. Le 4ème 1 ici est intelligent, mais le 3ème 1 aurait été plus que suffisant. Lors d'une entrevue, ils ont tous deux atteint la meilleure complexité temporelle possible. L' idée principale est d'enlever de cela est que l'application de diverses techniques à un problème, Consignia améliore efficacement la complexité du temps ou de l'espace. tri de nos données a réduit complexité de notre temps et ensuite, en utilisant une structure de données appropriée, un objet
ou un ensemble l'a amélioré à nouveau. Nous verrons cela apparaître encore et encore dans les problèmes futurs. Essayez d'utiliser un ensemble de tableaux d'objets. Empilez notre repère ou toute autre structure de données et voyez si cela ouvre de nouvelles avenues pour votre solution. Je te verrai dans le prochain problème dans la prochaine vidéo.
5. Flattening imbriquées: bienvenue à notre deuxième problème aplatir tableau. Dans ce problème sont l'entrée va être un tableau de tableaux imbriqués, parfois profondément imbriqués tableaux. Et notre objectif est d'écrire une fonction qui prendra chaque élément individuel dans le tableau et extrait dans un nouveau tableau plat. Voici un exemple. Nous recevons un tableau qui a plusieurs ou soulever à l'intérieur, plus d'autres éléments. L' objectif est d'extraire ces éléments de leurs tableaux profondément imbriqués dans un seul tableau plat tout en préservant l'ordre. Les entrées peuvent être des nombres, ou elles peuvent être des chaînes, ou elles peuvent être des objets qui peuvent vraiment être n'importe quoi. Notre objectif est de les prendre tout ce qu'ils sont et de le mettre dans un nouveau tableau plat tout en
préservant l'ordre. Ce problème a quelques utilisations pratiques dans une carrière de développeurs. J' ai dû faire face à des sources de données imbriquées plusieurs fois, et la résolution de ce problème vous donnera un aperçu de la façon de résoudre des problèmes similaires qui se posent à l'avenir. Contrairement au dernier problème où j'ai montré des solutions et ensuite discuté, je pense que ce sera plus instructif dans ce cas de parcourir la solution. Alors allons-y et commençons. Je vous encourage à mettre la vidéo en pause et à l'essayer vous-même. Allons-y. Nous devons donc créer un nouveau tableau. D' abord, allons-y et faisons-le. D' accord ? Nous allons devoir parcourir chaque élément de notre mémoire et les traiter un par un. Donc nous allons avoir besoin d'une boucle. D' accord ? Je vais juste stocker l'élément actuel dans une nouvelle variable. Et qu'est-ce qu'on veut faire ici ? Eh bien, on va vouloir faire quelque chose. Si cet élément ici est un tableau et que nous allons vouloir faire autre chose si ce
n'est pas pressé, Si ce n'est pas un tableau, alors nous pouvons immédiatement le pousser dans notre nouveau tableau. Mais si c'est le cas, nous devons passer par chaque individu, la tête de l'école et commencer à l'enduire. Donc, d'abord, ce que nous voulons faire est de vérifier si cet élément est un tableau. Donc, si cet élément n'est pas un tableau, nous savons qu'il n'est pas imbriqué plus loin, et nous pouvons aller de l'avant et le pousser directement dans notre nouveau tableau. Cependant, s'il s'agit d'un tableau, ce que nous voulons faire est de prendre chaque élément individuel dans la batterie et de les pousser un par un
dans un nouveau tableau. Donc, nous allons réellement avoir besoin d'une autre boucle ici, et à la fin, nous voulons retourner notre nouveau tableau. Ok, donc cette fonction ici fonctionnera si nous avons un tableau imbriqué d'un niveau profond, par
exemple, disons que c'est notre entrée. Notre fonctionnement fonctionne correctement pour ce tableau, et il le transformera en un tableau qui n'est pas imbriqué. Ça ressemble à ça. Juste pour s'assurer que ça marche. Allons-y et testons ça. Et ça marche. Voyons pourquoi cela fonctionne. Donc, nous sommes à l'intérieur de la boucle, et cet élément ,
la toute première fois, va être le numéro un. Ce n'est pas un tableau donc ruine à pousser directement dans un nouveau tableau, qui en aura maintenant juste un à l'intérieur. La prochaine fois que cet article sera
aussi, aussi, et nous allons faire la même chose et encore la même chose pour trois. Finalement, nous arrivons à ce tableau, qui a cinq étrangers à l'intérieur, et nous allons aller dans cette partie de l'instruction if, nous allons passer par chaque élément ici et pousser chaque élément, qui est étranger cinq individuellement dans. Donc, il va juste aller de l'avant et les ajouter sur nouvel arrangement à nouveau avec six. On va y aller et le pousser directement. Et c'est pourquoi cette fonction fonctionne comme elle le fait maintenant. Que se passe-t-il si nous avons plus de nécessités ? Par exemple, si nous avons quelque chose comme, Excusez-moi, quelque chose comme
ça, ça ne va pas marcher parce que nous allons seulement un niveau profond. Au lieu d'entrer dans ceci et de pousser sept, il va pousser ce tableau entier dans notre nouveau tableau. Alors, comment on répare ça ? Eh bien, la clé est en fait ici, donc nous ne savons pas combien de niveaux nous allons avoir besoin d'aller. Par exemple, les sept pourraient être un autre tableau profond. Ça pourrait même aller plus loin, et ça pourrait continuer. C' est le problème que nous essayons de résoudre. Donc, nous ne savons pas vraiment combien de fois, et nous allons devoir y aller parce que nous ne savons pas à quel point ces éléments peuvent être imbriqués. acteur allait avoir besoin de transformer cela en une fonction récursive, et voici comment nous faisons ça C'est tout. Cela fonctionnera. Allons de l'avant et testons ça juste pour nous en assurer. Et cela fonctionne exactement comme nous l'attendons. Qu' est-ce qu'on a fait ici ? Eh bien, nous disons que si nous rencontrons un tableau imbriqué, nous allons juste appeler la fonction aplatie entière à nouveau sur ce nécessaire. Réfléchissons à ça. Voyons voir. Nous arrivons à cet élément, qui est un tableau imbriqué. Il ressemble à trois niveaux de profondeur. Quand ça arrivera, on le fera passer. Aplatir une fois de plus, donc aplatis la prochaine fois autour bas recevoir un tableau, imbriqué deux niveaux de profondeur. Encore une fois, on va le transmettre. Il va recevoir celui-ci, et encore une fois il va passer et recevoir celui-ci. Finalement, il atteindra seulement les sept, et cela prendra cela et il le poussera dans un nouveau tableau. Cela fonctionnera peu importe à quel point sont imbriqués. Le tableau est
6. Débat sur les tableaux de rationalisation: Bienvenue pour aplatir. Rickerson est un concept difficile, donc je vous encourage à prendre quelques entrées différentes et à parcourir la fonction plusieurs fois par vous-même. Assurez-vous que vous vous êtes convaincu que la solution fonctionne de la façon dont vous pensez qu'elle fonctionne . Parlons de la complexité temporelle de cette fonction. Nous avons une boucle quatre ici, et nous avons un appel récursif et même quatre autres boucles ici. première vue, on
dirait que la complexité du temps va être assez folle sur celui-ci, mais c'est plutôt simple. Ignorons la fonction pour l'instant, et réfléchissons simplement à ce qu'elle fait à une entrée. Encore une fois. Prenons celui-là. Au fur et à mesure que nous passons par la fonction, chaque élément est poussé un par un dans notre nouveau tableau. Donc, notre boucle va aller ici et il va traiter un et le mettre d'une autre façon, peu de processus pour et mettre dans notre nouveau tableau, et il fera la même chose avec trois. Une fois qu'il arrivera à ce tableau, il plongera à l'intérieur et il traitera quatre, cinq, puis six. Et quand il arrivera ici, il va simplement plonger au fond, traiter les sept et ensuite repartir jusqu'au bout. Comme vous pouvez le voir, chaque élément n'est traité qu'une seule fois. Nous avons toutes ces boucles et nous avons même un appel récursif. Mais à la fin, chaque élément ici est traité. Une fois ça nous donne un temps linéaire, la complexité ou oh, de fin. Et l'espace ? Eh bien, chaque élément individuel est stocké dans son nouveau tableau, donc il est proportionnel à la taille de l'entrée à nouveau, Linear. C' est vraiment ça à ce problème. Ce que vous pouvez en retirer, c'est que Rikers est un outil puissant. Chaque fois que vous pouvez voir que vous allez répéter quelque chose dans ce cas plonger dans un tableau et que vous ne savez pas combien de fois vous pourriez avoir besoin de le faire, vous aurez probablement besoin de Rickerson. Merci. Et je te verrai dans la prochaine vidéo.
7. Suppression de personnages dupliqués: bienvenue au problème numéro trois. Enlevez les dupes. Le but ici est d'écrire une fonction qui prendra dans une chaîne. La fonction doit renvoyer une nouvelle chaîne avec les mêmes caractères que la chaîne d'origine, mais avec les caractères en double supprimés. Donc, si notre fonction reçoit une chaîne avec des caractères uniques, nous voulons retourner cette chaîne exacte. S' il y a des
doublons, nous voulons les enlever tout en conservant l'ordre des caractères. C' est ce que font ces deux exemples ici. Allons-y et commençons à écrire cette fonction à nouveau. Je vous recommande de le mettre en pause et sûr de vous-même, puis de revenir à cette vidéo. Nous devons démarrer cette fonction en créant un tableau pour stocker les caractères uniques dans notre chaîne. Allons-y et faisons-le. Nous allons avoir besoin d'une boucle pour traiter chaque personnage individuel. Donc, à l'intérieur de cette boucle, nous voulons d'abord vérifier si le caractère actuel était en traitement existe déjà dans notre tableau. Si c'est déjà dans notre tableau, cela signifie que nous l'avons déjà vu et que nous ne voulons pas le réinsérer, donc nous voulons juste continuer. Si, cependant, c'est la première fois que nous le voyons, nous voulons le pousser dans notre tableau. Notre tableau de voitures unique ne contient désormais que des personnages uniques. Ce que nous voulons faire est de transformer ceci en une chaîne et de retourner cette chaîne, et c'est la solution. Lancez-le et assurez-vous que cela fonctionne. Et c'est le cas. En effet, nous voyons un B. C D apparaître trois fois exactement ce que nous voulons. Passons en revue les complexités temporelles et spatiales pour le temps que nous n'avons pas pour boucle ici. Cela nous amène immédiatement à O of N Lord linéaire parce que nous traitons chaque personnage à l'intérieur de cette boucle que nous utilisons inclut ce lui-même est une boucle parce qu'il passe par ce tableau de voitures
unique et à la recherche de cette voiture. Et pour ce faire, il doit passer individuellement par tout dans le tableau. Donc, il doit faire une boucle à travers le tableau de gauche à droite, et cela s'arrêtera quand un autre trouve l'élément ou arrive à la fin. Mais c'est en effet une boucle, et parce que nous avons une boucle dans une boucle, nous allons avoir oh de fin des temps. Puisque vous multipliez leurs complexités temporelles, ce qui nous conduit orteil de n Square et c'est notre complexité de temps. Et l'espace ? Eh bien, nous devons prendre la chaîne et insérer chaque caractère unique dans notre tableau. Donc, nous devons essentiellement stocker à nouveau la chaîne entière, presque toute la chaîne, au moins. Donc ça va être Oh, de N parce que la quantité de données que nous utilisons va être proportionnelle à la taille de l'entrée . Il y a un moyen de rendre cette complexité un peu meilleure après beaucoup mieux . Allons passer par ça. Donc, j'ajoute un objet à notre tableau ici. Chaque fois que nous poussons un personnage dans notre tableau, nous voulons également l'ajouter à notre objet. Au lieu de vérifier le tableau pour voir s'il contient notre caractère, nous voulons maintenant vérifier l'objet. Donc on va remplacer ça. ne s'agit plus d'un O d'une opération. C' est une vérification en temps constant. Si un objet contient un élément est une opération à temps constant. Cela arrive à peu près instantanément, par
opposition à un tableau qui doit être recherché du début à la fin. Puisque nous n'avons plus de boucle à l'intérieur d'une boucle, nous n'avons qu'une seule boucle qui apporte notre complexité temporelle totale. Oh, et il y a un moyen de rendre ça un peu plus simple. Cela ne fera pas grand-chose pour un temps ou des complexités d'espace, mais cela rendra le problème beaucoup plus élégant et beaucoup plus facile à comprendre. Et nous allons passer par ça dans la prochaine vidéo. On se voit là-bas.
8. Supprimer les upes : simplicité ultime: bienvenue pour supprimer les dupes. Ce que nous avons fait jusqu'à présent est résolu ce problème et ensuite réduire la complexité du temps. Nous avons commencé à plus et au carré, et en ajoutant un objet, nous avons réussi à le réduire à O de fin. Il existe une autre façon de résoudre ce problème, qui ne change pas vos complexités temporelles ou spatiales. Cela rend le problème beaucoup plus facile à penser. Je vais juste écrire la solution et ensuite on pourra en discuter après. Faisons en sorte que cela fonctionne et que ça fonctionne. Nous obtenons ce que nous attendons. C' est la solution, et expliquons ce qui se passe. On utilise un set encore une fois. Donc, lorsque nous insérons une chaîne dans un ensemble, chaque caractère individuel est inséré dans un ensemble seulement valeurs uniques air stockées. Donc, tous les doublons vont être ignorés et rejetés après la création de l'ensemble. Nous utilisons cette méthode appelée un point de rayon à partir de maintenant ce que le raid fait est qu'il prend dans une péridurale, un adorable, et JavaScript est une structure de données qui maintient notre trace de l'ordre dans lequel les données étaient inséré et un ensemble fait exactement cela. Un ensemble gardera une trace des caractères dans l'ordre où ils ont été insérés, qui est exactement ce dont nous avons besoin, car il fait que nous pouvons dire que si set est un honorable et cela fonctionnera avec cette méthode arrachée à partir de laquelle sera littéralement l'a transformé en un tableau. Donc, cette déclaration ici est égale à un tableau contenant les caractères uniques et la force avec leur ordre préservé. Tout ce que nous faisons après cela est d'utiliser join pour les transformer en une chaîne. La complexité temporelle ici est exactement la même. Nous prenons chaque caractère et inséré dans l'ensemble un par un. Alors c'est la boucle. Nous donner oh, de fin. joindre dans un tableau est notre désolé. transformer en un tableau est également vieux de temps en temps, rejoignant comme oh, de n une fois de plus. Donc, nous avons trois n et quand nous laissons tomber la constante, nous restons à O de n pour la complexité de l'espace. Nous mettons chaque personnage dans un ensemble, puis dans un tableau. Donc, nous avons oh de deux n, qui devient à nouveau O de n. Espérons que le montre à quel point un ensemble est puissant et combien la maîtrise des structures de données peut vous aider avec ces problèmes. Plus vous en savez, plus vous serez en mesure d'appliquer ces choses et les problèmes futurs. Nous avons tourné ce qui était à propos d'une fonction de 15 lignes. Si les deux lignes, c'est beaucoup plus facile à lire, comprendre et à droite, je vous verrai dans la prochaine vidéo.
9. Fréquence plus élevée: bienvenue au prochain problème. Fréquence la plus élevée. Le but ici est d'écrire une fonction qui prendra dans un tableau de chaînes et retournera. La chaîne qui se produit le plus souvent implicite dans ce problème est que la théorie que vous recevez peut avoir des chaînes en double, certaines à plusieurs reprises, et nous voulons celle qui apparaît le plus fréquemment. S' il y a plusieurs chaînes avec la même haute fréquence, nous voulons retourner celle qui apparaît en premier. Voici quelques exemples dans le 1er 1 C est la seule chaîne qui apparaît plus d'une fois, donc c'est ce que nous voulons retourner dans la prochaine. ABC apparaît trois fois et D E F deux fois, donc nous voulons voir ABC sortir dans la prochaine. Ils ne sont président qu'une fois. Tellement désolé. Et comme ABC est le premier, nous voulons que celui revienne et dans les derniers yeux GH et ils sont plus de fois que les autres. C' est ce qu'on veut revenir. Allons de l'avant et commençons sur la solution, donc nous allons devoir traiter chaque chaîne qui est dans notre tableau afin de garder une trace des fréquences. Donc nous allons avoir besoin de commencer par une boucle comme d'habitude comme nous arrivons à chaque chaîne ou d'une manière ou d'une autre
besoin de garder une trace du nombre de fois que nous l'avons vu. Allons de l'avant et utilisons un objet pour garder une trace de ces chaînes et dans la boucle. Au fur et à mesure que nous traitons chaque chaîne, nous pouvons aller de l'avant et mettre à jour notre objet. Pensons donc à la première chaîne. Allons de l'avant et nous concentrons sur cet exemple pour l'
instant, à I égal à zéro, le premier élément sera ABC. Allons de l'avant et créons une variable pour cela. Donc, cette chaîne va être A B, C et R Object est vide. Nous allons vouloir l'ajouter dans les fréquences. Objet. Ok, jusqu'à présent, si bien. Allons de l'avant et voyons ce qui se passe si nous passons à la chaîne suivante à nouveau. ABC nous allons être ici, et cette chaîne va être ABC une fois de plus. Mais maintenant cette ligne de code ne fait pas ce que nous voulons. C' est réinitialiser la valeur à une valeur qui ne fait rien pour nous. Nous allons avoir besoin d'un moyen de vérifier si c'est la première fois que notre objet voit cette chaîne. Si c'est le cas, nous devons lui donner la valeur d'un. Sinon, nous devons en quelque sorte prendre la valeur et l'augmenter d'un. Commençons donc par vérifier si c'est la première fois que nous voyons cette chaîne. Et si c'est le cas, alors il ne sera pas encore présent dans l'objet. Donc, si cela n'existe pas encore dans l'objet, alors le vérifier devrait nous donner indéfini. Et si ce n'est pas défini, nous devons lui donner une valeur de 1. Qui est la première fois qu'on voit la ficelle ? Si, cependant, il existe déjà, ce qui signifie qu'il a déjà cimenté votre valeur 123 ou tout ce dont nous avons besoin pour augmenter cela d'un . On dirait que ça a du sens pour moi. Allons de l'avant et allongons notre tableau de fréquences. Désolé objet juste pour nous assurer que nous faisons cela correctement. Et je vais aller de l'avant et me débarrasser de ces trois pour l'instant et juste travailler avec cet exemple voir ce que nous attendons. A B C est ici deux fois D E f. Trois fois et G h I quatre fois. Notre objet reflète cela correctement. Que devons-nous faire maintenant ? Eh bien, nous devons en quelque sorte savoir laquelle de ces valeurs est la plus élevée. Nous devons savoir que quatre est la valeur la plus élevée ici et que la chaîne correspondant à cela est G H I. Nous pourrions faire un traitement ici. Nous pourrions prendre chaque valeur individuelle dans l'objet, puis trouver le plus grand nombre de
suivi . Mais nous avons déjà une boucle for. Nous ne pouvons le faire qu'en, euh en mettant à jour une variable tout au long de la boucle. Allons de l'avant et créons une variable pour stocker la plus haute dissimulation libre que nous avons rencontrée jusqu' présent. Et nous allons l'initialiser à zéro. Et c'est aussi une variable créative pour la chaîne la plus fréquente, et nous allons l'initialiser au premier élément de nos chaînes sont un dans notre boucle. Allons de l'avant et mettons-les à jour chaque fois que nous passons par notre boucle. Donc ils auront seulement besoin de mise à jour si nous avons une nouvelle fréquence max. Vérifions si nous dio cette vérification ici vérifie si notre nouvelle fréquence signifie que la valeur nous venons de mettre à jour est supérieure à la fréquence Max précédente que nous avions. Si c'est le cas, nous voulons mettre à jour ce numéro de fréquence Nous voulons également mettre à jour la chaîne la plus fréquente parce que cela signifie qu'il est changé une fois que nous traversons cette boucle, ces deux variables se mettent à jour à plusieurs reprises car elles ont besoin de Teoh. En fin de compte, la variable de chaînes la plus fréquente contiendra la rue la plus fréquente. Donc, nous pouvons aller de l'avant et retourner ça. Ajoutons ceux-ci à nouveau et assurez-vous que tout fonctionne comme nous nous y attendons, Donc si c'est le cas, nous nous attendons à voir ABC, ABC et G H I. Et c'est ce que nous obtenons. Il semble fonctionner correctement. Allons de l'avant et parlons de la complexité temporelle de cette solution. Nous avons une boucle ici immédiatement. Apportez-nous 20 de fin à l'intérieur de la boucle. Tout ce que nous faisons est d'effectuer quelques vérifications et de mettre à jour quelques variables si nécessaire. Ce ne sont pas des boucles en soi, donc ils ne changeront pas notre complexité temporelle. Donc notre complexité temporelle finale va être o de tout et qu'en est-il de l'espace ? Eh bien, nous stockons chaque chaîne que nous trouvons dans notre objet de fréquences. Si notre tableau de chaînes ne contient que des chaînes uniques, alors cet objet de fréquences va les contenir toutes. Donc, il va essentiellement être proportionnel à la taille de nos cordes sont un sens. Ça va aussi être oh, de fin. Que pouvons-nous retirer de ce problème ? Eh bien, ce problème nous oblige essentiellement à stocker une mise à jour des données pendant que nous traversons notre boucle. C' est une bonne technique à garder à l'esprit. Les problèmes ne nécessitent souvent pas cela, et une solution peut être trouvée sans garder une trace. En fait, même ici, nous n'avions pas à faire ça. Nous pourrions simplement le commenter et le commenter, et nous pourrions effectuer un post-traitement signifiant ici. Nous pourrions ajouter un peu plus de code pour ensuite déterminer quelle valeur est la plus élevée et ensuite quelle chaîne qui correspond. Mais au lieu de cela, nous gardons une trace de tout pendant que nous traversons notre boucle, donc nous n'avons pas besoin de faire quoi que ce soit par la suite. En général, essayez de voir. Si le stockage de données et d'une manière créative peut rendre un algorithme plus facile, il peut être en mesure de réduire la complexité temporelle. Mais si ce n'est pas le cas, au moins cela peut rendre le code plus simple. Nous verrons dans la prochaine vidéo
10. Rotation de chaîne: bienvenue au prochain problème. Rotation de la chaîne. Le but ici est d'écrire une fonction qui prendra deux chaînes et de déterminer si leurs rotations l'une de l'autre. Maintenant, quelle est la rotation ? Ce sont des exemples de rotations, donc nous avons la chaîne 1234 Pour le faire pivoter, nous pouvons retirer un personnage du début et le placer à la fin. Cela nous donne 2341 Nous pouvons le faire à nouveau et prendre les deux et le déplacer jusqu'à la fin, et nous obtenons 3412 et le faire encore une fois. Déplacer un trois à la fin obtient son 4123 C'est une rotation ici. Quelques autres exemples. Allons de l'avant et commençons à écrire cette fonction, donc la première façon de savoir si ce ne sont certainement pas des rotations est si les chaînes ont des longueurs différentes pour deux cordes trois rotations de l'autre. Ils doivent avoir exactement la même longueur. Alors allons-y et vérifions ça. Ok, fini avec ça ? Non. Une façon de résoudre ce problème serait de prendre notre première chaîne et de créer chaque rotation
possible de celui-ci comme nous le faisons. Nous vérifierons si ces rotations sont égales à la deuxième chaîne. Si c'est le cas, nous pouvons retourner vrai. Et si nous passons à travers toutes les rotations et qu'il n'y a pas de correspondance que nous pouvons retourner false, allons de l'avant et écrire une boucle pour le faire pour nous, et pour ce faire, nous allons utiliser la méthode tranchée de points de chaîne. C' est une méthode qui va extraire le texte d'une chaîne. La façon de l'utiliser est que nous lui donnons aux paramètres l'index de début et de fin que nous aimerions découper et il va trancher entre ces deux indices. Donc, par
exemple, trancher ceci aux Indices un et huit signifie que l'Index un est juste ici et que le prochain huit est juste ici et que nous aurons tout entre ces deux. Ce qui signifie que c'est la méthode utilisera. Voyons ce que dans cette impression et allons-y et débarrassons-nous de trois d'entre eux et concentrez-vous sur celui-ci. Bon, alors que je me déplace de gauche à droite, nous obtenons des tranches légèrement plus grandes et plus grandes. Maintenant, essayons d'autres indices. Essayons de trancher. Nous l'avons fait du début à l'index, et maintenant essayons dans l'index à la longueur des chaînes. Et ce que nous voyons ici est une scission parfaitement propre. Ce que nous devons faire pour faire tourner cette chaîne, sa place, ceci au début. Et puis nous aurions une rotation avec un R à la fin. Nous continuons à faire cela et à mettre cette chaîne avant celle-ci, et nous avons généré toutes les rotations possibles. Laisse-moi te montrer ce que ça veut dire. Nous avons juste besoin de changer l'ordre de ces deux-là et nous obtenons chaque rotation une par une lettre. Enlevez-le du début et placé à la fin. C' est exactement ce que nous devons faire maintenant est de vérifier. La rotation F est égale à la deuxième chaîne. Si c'est le cas, nous pouvons sortir de la boucle et retourner true. Et si nous arrivons à la fin et qu'aucun d'entre eux ne correspond, nous retournons faux. Allons-y, débarrassez-vous de tout ça et voyons si ça marche. Donc nous nous attendons à la trêve et deux faux sont,
et c'est ce que nous obtenons. On a l'air bien. Parlons de la complexité temporelle de cette fonction. Donc nous avons déjà une boucle ici, nous
amenant à Ole of Ed cette fois n n'est pas la taille de la théorie a ou le nombre d'arguments . Il va en fait représenter la longueur des chaînes parce que c'est à peu près la seule chose qui change. En fait, c'est la seule chose qui change que nous pouvons mesurer. Donc, nous avons un no de boucle de fin ici. Examinons cette ligne un peu de près. Donc, tranche, selon les quais pour Indian, est en fait une boucle parce que chaque personnage doit être contaminé un par un. Donc croyez-le ou non, tranche est une opération O de n. Et ce que nous avons ici est une boucle dans une boucle qui nous amène à, bien que de n carré et de l'espace. Nous stockons une rotation et cette variable, donc la quantité de caractères dans la chaîne que cette variable contient sera égale à la longueur de la chaîne. Donc, en d'autres termes, la quantité d'espace utilisée par cette variable va être équivalente à la quantité d'espace utilisée par
cette chaîne. Donc ça va être linéaire. C' est tout pour la solution. Mais il y en a un de plus qui rend cela beaucoup plus simple pour nous. Je vais aller de l'avant et écrire le code et nous en discuterons immédiatement après et nous allons le lancer et nous sommes bons d'y aller maintenant Réfléchissons une minute pourquoi cela fonctionne. Prenons ces deux-là et plaçons la rotation à côté de lui-même. Donc, en d'autres termes, nous effectuons cette action ici. Str wana plus str one Et nous vérifions si cette chaîne donc le 1er 1 dupliqué a le 2ème 1 quelque part dedans. Donc nous cherchons l'existence de ceci quelque part à l'intérieur de ceci et nous pouvons le trouver. C' est juste là. Essayez-le par vous-même. Mais chaque rotation que vous pouvez trouver sera présente dans cette chaîne. C' est à peu près une loi ici. En termes de fonctionnement de ces rotations, vous mettez une chaîne à côté de elle-même et elle contient chaque rotation de la chaîne initiale. La complexité temporelle de cette solution est oh, de n. Tout ce que nous faisons est d'ajouter une chaîne à elle-même, qui est linéaire, puis de vérifier si elle inclut le 2ème 1 qui est aussi Lanier. Donc, cela s'est transformé en oh, off et l'espace est aussi de n parce que nous ajoutons ces deux et la longueur va être proportionnelle exactement. Doublez la longueur de celui-ci ici. C' est tout pour ce problème de voir le prochain.
Arnav Aggarwal, Full-Stack Engineer & Instructor
