Maîtriser l'entretien JavaScript Partie 2 : Chaînes et tableaux avancés

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. Sous-ensembles de tableau: Le problème suivant est un sous-ensemble de rayons pour ce problème. Notre fonction va recevoir deux arguments qui vont tous deux être une augmentation, et ces tableaux ne contiendront que des nombres et des chaînes. Notre objectif est de savoir si le deuxième tableau est un sous-ensemble du premier sont un et ce que cela signifie est que nous voulons retourner. Vrai. Si chaque élément du deuxième tableau se trouve également dans le 1er 3, nous avons quelques indices ici. Comme d'habitude, Ce problème a quelques solutions différentes avec différentes complexités temporelles, et nous allons aller de l'avant et couvrir tous d'entre eux. Et l'une des clés de ce problème est de savoir comment faire face aux répétitions lorsqu'un élément est présent deux ou trois fois. Voici quelques exemples pour ce 1er 1 Les mêmes éléments sont présents à la fois dans une augmentation, les mêmes éléments exacts juste dans un ordre différent. Donc, nous savons que le second est un sous-ensemble du premier dans la prochaine Thèse et Array a 12 et trois, et le premier Array a un autre, donc il est toujours conforme à nos conditions dans le prochain. Le deuxième tableau a trois que le premier tableau n'a pas. Donc on veut ça. Nous voulons que notre fonction retourne False. Pour cette affaire et la suivante, nous en avons deux. Donc encore une fois faux et puis le 3e 1 Bien que les éléments, le nombre d'éléments est le même, les trois éléments n'apparaissent pas dans le premier taux. Seul un de ceux le fait. Encore une fois, nous voulons un faux retour. Essayez le problème et allez-y et appuyez sur Play lorsque vous avez au moins essayé. Commençons. Donc, comme d'habitude, nous allons avoir besoin d'une boucle. Mais de quelle façon voulons-nous ? Une boucle sur. Eh bien, nous voulons nous assurer que chaque élément du deuxième tableau est présent dans le premier. Donc, tout ce qui nous intéresse vraiment, c'est chaque élément du secondaire. Le 1er 1 pourrait avoir quelques extras dont nous ne nous soucions pas. Par exemple, celui-ci. Donc, il semble que ce serait une meilleure idée de faire une boucle sur le 2ème 1 Et que veut-on faire ici ? Eh bien, quel que soit l'élément auquel nous sommes actuellement, nous voulons le chercher dans le premier tableau du super ensemble. Donc, ici, nous utilisons juste l'index de la méthode pour trouver où dans le super ensemble cet élément existe. Si elle existe malade. Si ce n'est pas le cas, alors Super Index sera égal à négatif et nous pouvons immédiatement retourner false. Ce que cela signifie, c'est qu'il y a un élément dans le deuxième tableau, pas dans le 1er 1 donc nous savons qu'il ne peut pas. Le 2nd 1 ne peut pas être un sous-ensemble, donc nous pouvons immédiatement retourner false et à la fin de la fonction. Et si tout se passe bien, nous voulons retourner vrai. Allons de l'avant et testons cette fonction et nous n'obtenons pas tout à fait ce que nous attendons à ce que ceux-ci fonctionnent. Celui-ci travaille à. Nous arrivons à la trêve de fausses, puis de deux vérités. Donc ces deux conditions échouent. Jetons un coup d'oeil à celui-ci. Eh bien, une condition facile que nous pouvons comprendre tout de suite est qu'un sous-ensemble doit être plus petit ou égal à la taille de son super ensemble. Donc, si les subventions sont toujours plus grandes, alors nous savons que ce ne peut pas être un vrai sous-ensemble. Alors allons de l'avant et à ce sujet. Ça marche à nouveau et ça passait. On aura un faux ici, mais on doit toujours faire passer cette pièce ici, et il n'y a pas de moyen facile de contourner ça. Donc notre fonction ici est presque complète. Mais il y a une chose importante que nous devons faire, et c'est. Gardez une trace du numéro de chaque élément qui apparaît, et nous le ferons dans la leçon suivante. 3. Algorithmes à double rangs - Plen profondde: Bienvenue dans le sous-ensemble de tableaux. On en a presque fini avec notre fonction. Tout ce qu'il faut faire, c'est faire échouer cette affaire ici. Il passe le test et nous retrouvons vrai en revenant de notre fonction. Ce dont nous avons besoin est faux revenir parce que ce tableau n'est pas un sous-ensemble de ce tableau. Comment pouvons-nous faire ça ? Eh bien, moment, ce que la boucle fait, c'est qu'elle passe par ce deuxième tableau et qu'elle traite chaque élément la première fois qu'elle voit celui-ci. Il le cherche dans ce tableau et il dit qu'il est là. Il trouve ça génial. Il continue dans la boucle et arrive à nouveau à la suivante. Il regarde vers l'avant dans le premier tableau et il le trouve et trouve exactement le même. Et ça dit, OK, on est bon d'y aller et ça le fait encore une fois. Nous devons lui dire qu'il ne peut pas regarder cet article deux fois et ne peut pas regarder le même objet plusieurs fois. Si un article apparaît plus d'une fois dans le sous-ensemble, il doit apparaître au moins ce nombre de fois dans le super ensemble Eh bien, une chose que nous pouvons dio, c'est simplement supprimer les éléments que nous trouvons dans le super ensemble qui résoudrait le problème. Par exemple, quelle est la fonction recherche pour celle-ci et elle la trouve ici en le trouvant. Nous pouvons simplement le supprimer du tableau. La prochaine fois qu'il en regarde, il cherche celui qu'il ne le trouvera pas et retournera faux. Donc, allons de l'avant et coder que dans le premier, nous ne voulons pas modifier directement ce tableau ont été donnés, Alors faisons une copie de celui-ci. Désolé, Super copie. Et avec l'opérateur spread, c'est tout ce que nous devons faire pour faire une copie de ce premier tableau. Et essayons de le faire à nouveau et tous nos tests réussissent ce travail fonctionnel. Allons de l'avant et regardons les complexités temporelles et spatiales. Donc pour le temps, nous allons appeler ce M, et à cette fin, nous avons en fait deux variables différentes. Nous devons donc garder notre complexité temporelle en termes de ces deux variables. Ici, nous avons et tous. Ah, nous avons un pas de processus em en copiant un tableau prend ce que nous devons faire est d'avoir une boucle orteil à travers le tableau et de copier chaque élément individuel. Donc, c'est une opération linéaire ici dans cette boucle, nous commençons par plus de N pour secondaire et ici nous sommes en fait nous avons une autre boucle a mentionné dans un problème précédent. Index of est une boucle et nous sommes en boucle sur super, ce qui dans notre cas, est M Donc nous n'avons pas de m ici parce qu'ils sont dans une boucle. Nous les multiplions ensemble et nous obtenons tous em fois n et parce que O de m fois n est un facteur plus grand que celui-ci que nous pouvons après. Allez-y et ignorez cela parce que cela n'a aucune incidence sur la complexité de l'espace. Nous créons un nouveau tableau en copiant l'original. Donc ça va être o de M. Il y a une autre façon de résoudre cela, et cela améliorera réellement notre complexité temporelle un peu. Allons-y et travaillons là-dessus. Donc, au lieu d'opérer comme ça, où nous sommes en boucle à travers le sous-ensemble et ensuite essayer de le trouver que le super ensemble étaient restés en boucle à travers chacun séparément et garder le compte pour que nous puissions garder ce top, nous n'aurons pas besoin de cela plus et gardera le retour vrai en bas. Donc nous avons utilisé cette stratégie auparavant, mais ce que nous allons faire est de créer un objet pour garder une trace de ces chiffres. Je vais juste étiqueter ce bétail. Donc, ce que nous faisons, c'est que nous sommes d'abord en boucle à travers le super ensemble et construisons cet objet au moment où nous avons terminé, ce que nous voulons que cet objet ait est une représentation de chaque élément qui est ici, signifie des comptes corrects. - Donc c'est le cas. L' instruction CIF est le cas dans lequel se trouvaient une chaîne ou un nombre pour la première fois. Donc, si c'est la première fois, nous voulons lui donner une valeur de 1. Si on l'a déjà vu, on veut juste l'incrémenter, accord ? Et c'est tout ce que nous voulons faire face à cette boucle. Cette boucle contiendra un nombre correct de tous les éléments ici. Et verrouillons ça pour en être sûr, et nous allons l'essayer avec seulement deux. Ce dernier article ici. Donc, nous exécutons cet exemple ici, et nous sommes en boucle à travers ce tableau et cela semble correct. Nous voyons un apparaissant une fois et trois apparaissant une fois et juste pour nous en assurer absolument. Ajoutons trois autres. Ensuite, exécutez à nouveau et nous en voyons trois deux fois. Donc, on dirait que ça marche. Très bien. Allons de l'avant et passons à travers le deuxième tableau. - Donc ici, nous traitons un élément dans notre sous-ensemble, et nous essayons de nous assurer qu'il est trouvé dans notre objet de compte. Si nous ne l'avons pas vu auparavant, ce qui signifie que c'est indéfini. Nous savons que nous avons quelque chose de président, le sous-ensemble que nous n'avons pas dans le super set. Parce que si nous l'avions fait, il aurait été stocké dans cet objet par cette boucle. Donc, si c'est le cas ici, nous pouvons aller de l'avant et retourner faux. Cependant, si ce n'est pas indéfini, nous voulons juste diminuer sa valeur d'un. Donc, cela va diminuer notre compte. Que se passe-t-il ? Un. Le nombre atteint zéro. Ce que nous faisons ici, c'est que si le compte atteint zéro, nous supprimons entièrement l'élément de notre objet du nombre. De cette façon, si nous traitons à nouveau cet élément, nous passerons à travers cette boucle et entrerons dans ce cas. Ce que cela signifie, c'est que nous avons rencontré cet objet plus de fois dans le sous-ensemble que dans le super ensemble, qui signifie que ce n'est pas une trêve bouleversée, et nous pouvons retourner faux. Essayez d'essayer d'envelopper votre tête autour de ça. Allons de l'avant et comptons à nouveau juste pour nous assurer qu'il fonctionne bien à la fin de la deuxième boucle. Donc nous nous attendons à voir, voyons, euh, nous voyons faux parce que ça revient faux. Ok, changeons un peu ça et faisons-le 123 Donc ce qu'on devrait voir c'est un objet vide. Et c'est exactement ce que nous faisons. Voyez, parce que cette boucle traitait le désarroi et que cette boucle traitait le désarroi, ils se annulaient essentiellement. Les éléments ont été ajoutés et compte, puis supprimés par cette boucle ici. Donc on ne devrait rien voir sortir, et on dirait que ça marche comme on l'attend. Allons de l'avant et exécutons ces et voyons si notre fonction fonctionne correctement et nous obtenons toujours un vrai ici. Pourquoi c'est ça ? Uh, n'a pas changé ça en arrière et ça marche exactement comme on s'y attendait. Regardons la complexité temporelle pour celui-ci. Donc on a un O de dans ce cas, on va aux super sets, tous. Et rien ici n'est une boucle. Et ici, nous avons un O de N , alors rien ici n'est une boucle. Donc cette fois, parce que les boucles sont les unes après les autres et nous n'avons pas une à l'intérieur d'une autre au lieu de se multiplier. Ce que nous allons faire est d'ajouter ces deux ensemble, donc nous obtenons O de M plus n pour la complexité de l'espace. Nous stockons tous les éléments du super ensemble dans cet objet de comptage. Donc, cela va juste rester o de M. Donc, cette solution fonctionne parfaitement bien. Et la prochaine vidéo, nous allons aller de l'avant et comprendre comment résoudre ce problème si nous ne sommes pas donnés juste des chaînes et des nombres dans nos tableaux ici. Mais nous allons faire en sorte que cela fonctionne pour chaque type d'entrée en voyant la leçon suivante. 4. Sous-ensemble de Array : La solution optimale: bienvenue dans la dernière vidéo, nous avons réussi à résoudre le problème du sous-ensemble de la baie. Notre solution est ici et elle ne fonctionne pas pour tous les exemples ici. Et cela fonctionnera pour chaque exemple dans lequel nous utilisons l'un ou l'autre des nombres. C' est un type de je m'excuse, je devrais dire, ou cela fonctionnera pour toute entrée dans laquelle nous lui donnons des nombres ou des chaînes. Dans ce cas, sont tous des chiffres ici. Mais cela fonctionnerait si nous les remplacons par des chaînes tout de même. Et c'est la clé. Notre solution ne fonctionnera que pour les nombres et les chaînes. Si nous essayons d'utiliser des objets, une augmentation ou des fonctions sont notre fonction ici va se décomposer et passons. Pourquoi remarquer que nous stockons toutes nos informations dans un objet ici ? Les objets sont grands, mais ils ont un petit défaut. Et parlons de ce que c'est. - Donc tout ce que j'ai fait ici est de créer un objet, puis essayer de créer 33 paires de valeurs clés, une avec un objet, une avec une chaîne et une avec un nombre. Et quand nous nous opposons longtemps, c'est ce que nous obtenons ici. Ce n'est pas le plus utile Donc nous allons réellement enregistrer chaque élément individuellement et nous les voyons ici, donc cela fonctionne correctement. Nous allons aussi nous connecter à la place de la vallée ici. Allons de l'avant et connectons le type de la clé et remarqué que chaque fois que nous obtenons chaîne , c'est la mouche qui parlait. Chaque fois que nous utilisons des parenthèses avec un objet pour un ensemble de variable ou accéder à quelque chose, ce qui se passe en interne est que cet élément, quoi qu'il arrive d'être le premier, converti en une chaîne. Donc, cet objet ici est converti en objet chaîne. Et c'est comme ça que cette plateforme décide de l'utiliser. D' autres pourraient simplement l'appeler une chaîne avec le mot objet dedans. Ou ça pourrait être autre chose. Il pourrait être même ce support de chaîne, mais ici c'est un objet, et c'est en effet une chaîne 25 est également convertie en une chaîne. Donc, plutôt que d'être le nombre 25 ce qui se passe ici est la chaîne 25. Maintenant, si nous avons plusieurs objets et que nous essayons de les utiliser tous les deux, voyons ce qui se passe. Le problème est que ces deux, bien que leurs objets distincts. Comme nous pouvons le voir ici, nous avons clairement fait deux objets distincts. Ils sont tous les deux forcés dans le même objet de chaîne ici. Et cela signifie que l'un d'eux n'est tout simplement pas inséré. Au contraire, nous insérons ceci et puis cela le remplace complètement. Juste pour vous montrer que cela se passe, nous obtenons aussi un objet. Donc, cela a été essentiellement retiré de notre objet. Ok, on en a fini avec. Allons de l'avant et discutons de la façon de résoudre ce problème. Donc, au lieu d'un objet ici, nous allons utiliser quelque chose de différent. Nous allons utiliser une construction E S 2015 appelée une carte. Maintenant, une carte est fondamentalement la même chose qu'un objet sauf lui. Au lieu de la chaîne défiant ses clés, il les gardera telles qu'elles sont. C' est donc un objet qui contient des paires de valeurs de clé, et n'importe quelle valeur peut être utilisée comme une clé, pas seulement pour chaîne l'utilisation de juste assez simple. Vous pouvez aller de l'avant et lire la documentation pour apprendre les méthodes, mais cet exemple ici vous donnera tout ce que vous devez savoir à ce sujet. Et comme nous utilisons les méthodes sera en parler de toute façon. Alors allons de l'avant et plongons directement dans. Donc, au lieu d'un objet pour créer une carte, nous utilisons de nouveaux calculs pour rechercher un élément au lieu de vérifier. Si ce n'est pas défini, nous utilisons une méthode appelée has et nous n'avons pas besoin de cela. Si l'élément est présent dans notre carte, cela retournera true. Si ce n'est pas le cas, ce sera faux. Au lieu de définir une paire de valeur clé de cette façon, nous le faisons différemment. Nous utilisons set, et le premier élément que nous lui donnons va être ce que nous voulons définir, qui sera. Désolé, ça va être la clé que nous aimerions mettre. Donc, ça va être l'élément actuel. Et puis le numéro de nous voulons le donner dans ce cas un. Nous devrons changer cela aussi. Et qu'est-ce qu'on met une seconde valeur ? Eh bien, nous voulons mettre. Nous voulons le définir à quelle que soit la valeur actuelle plus un. Je viens de réaliser que ça doit avoir un point d'exclamation parce que ce que nous essayons de faire ici c'est vérifier et voir. Nous essayons de nous assurer que notre carte ne contient pas encore cet élément. S' il n'a pas l'élément, nous voulons définir sa valeur sur un. Et s'il a l'article, nous voulons l'augmenter d'un. Donc, c'est correct. Passant à notre deuxième boucle pour cela, nous pouvons réellement le remplacer par ceci exactement comme c'est parce que nous essayons de vérifier exactement la même chose. Ceci ici peut être remplacé par cela par un petit changement. Donc, au lieu d'en ajouter un, comme nous le faisons ici, nous voulons en soustraire un. Donc, pour diminuer ce nombre d'éléments, nous obtenons sa valeur actuelle en soustrayant un et en définissant sa nouvelle valeur à ce nombre ici, Au lieu d'accéder à cela comme nous le ferions avec un objet, nous allons simplement utiliser le méthode de montagne appropriée. Et ici, nous utilisons la carte de méthode, Doc delete et nous voulons simplement passer, oops, élément actuel et cela devrait fonctionner avec plaisir. Nous obtenons exactement les mêmes valeurs que nous nous attendons, donc il semble que ça marche. Je vous encourage à les changer et à les essayer avec des objets, des tableaux, fonctions, des chaînes et des nombres dans le même exemple. Cette nouvelle fonction que nous avons ici devrait fonctionner pour tout ce que vous lui donnez. Les complexités temporelles et spatiales restent les mêmes. Une carte est fondamentalement équivalente à un objet, juste avec cette nouvelle fonctionnalité ajoutée où les clés ne doivent pas être des chaînes. C' est ça. se voit dans la vidéo suivante. 5. Maximum de bénéfices grâce à la force Brute: bienvenue au prochain problème. Maximum des profits pour ce problème. Nous allons recevoir un tableau de chiffres représentant les prix d'une action du début de la journée à la fin de la journée. Par exemple, étant donné ce tableau ici, le stock a commencé à un prix de 10 et s'est terminé à un jour à un prix de neuf. Et il a traversé ces choses dans l'ordre pendant ce jour-là et a traversé ces prix. Notre objectif est de trouver le maximum de profit possible en achetant une fois et en vendant une fois par jour. Donc, à partir de ce tableau, nous voulons trouver le maximum de profit que nous pouvons faire. n'y a pas de court-circuit, ce qui signifie que vous devez acheter avant de vendre et si aucun profit ne peut être réalisé. Par exemple, si le prix de l'action a baissé toute la journée et que cela ressemblait à 10 98765 Alors, au lieu de retourner un nombre négatif, nous voulons juste retourner zéro pour indiquer qu'aucun profit ne peut être réalisé. Allons-y et commençons comme d'habitude. Nous allons avoir besoin de nos quatre boucles et de ce que nous voulons faire. Nous commencerons par la stratégie de force brute, ce qui signifie calculer tous les profits possibles que nous pouvons réaliser et retourner ensuite le plus grand que nous trouvons. Et réfléchissons à la façon de le faire. Donc, si nous l'avons acheté 10 et vendu à sept, nous sommes le profit sera négatif trois. Et nous voulons stocker ça quelque part. Si nous voyions si nous l'achetons 10 et vendions à cinq ans, notre profit serait négatif. Cinq en ont acheté 10 et en ont vendu huit. Et sur et sur et sur. On ne ferait pas beaucoup d'argent en achetant à 10 heures. Détruisez sept. Donc par ses sept vendre à cinq. Notre prophète est négatif à acheter à sept ans. Cellule à huit heures. Bénéfices un par ses sept Vendre 11 bénéfices pour commencer à bien paraître. Nous allons juste passer par ça et encore et encore jusqu'à ce que nous obtenions tous les profits possibles et ensuite nous rendrons le plus élevé. Donc, pour ce faire, nous avons remarqué que lorsque nous avons commencé à 10 ans, nous avons ensuite dû traiter chacun de ces. Quand nous avons commencé à sept ans, nous avons dû profiter chacun de ces bénéfices. On va avoir besoin d'une boucle à l'intérieur de cette boucle. J' oublie ce que cette boucle va avoir ici, je pense la même chose. Les prix commencent la longueur vers le haut. Je vois que cela doit être égal à un I plus un parce que nous voulons commencer après la position de et stocker chacun des bénéfices possibles. Nous voulons créer un tableau. Et ici, tout ce que nous devons faire est de calculer le profit et de le mettre dans le tableau à la fin, nous voulons retourner le maximum. Donc, ce que nous pouvons faire est d'utiliser la fonction maths dot max et maths. Pas Max prend plusieurs nombres, autant que vous voulez lui donner, et il va juste retourner le nombre maximum. Donc ici, nous pouvons répartir notre gamme de profits. Une chose que j'ai oubliée ici, on veut commencer par zéro. Donc, si encore une fois, si les prix vont juste baisser, passant de, disons, 928642 hommes, peu importe où nous achetons le peu importe où nous vendons notre profit va être négatif. Ayant cela ici, les assureurs que maths dot max obtiendra au moins zéro à chaque fois. Cela résout donc la condition que nous avons mentionnée plus tôt. Si aucun profit ne peut être fait, nous voulons revenir. Zéro. Allons de l'avant et testons ça. Nous allons juste utiliser la Serie juste ici et nous nous attendons à voir six belles choses. Ok, parlons de la complexité temporelle dans la complexité spatiale de ce problème. Donc, nous avons une boucle qui passe par notre droite et nous avons une autre boucle qui passe par non pas le tout déjà mais une partie de la théorie. Ça va certainement être Oh, de End. Et celui-ci va aussi être oh, de n même si elle ne traverse pas tout le tableau. En moyenne, cette boucle passe en fait par la demi-théorie. Par exemple, à partir de 10 J va passer par cinq numéros à partir de sept. Ça va passer par quatre, à partir de cinq. Il va y aller trois, puis deux, puis un. La moyenne de ces nombres est la moitié de la longueur de ce tableau, donc cela est techniquement et plus de deux. Mais nous laissons tomber les constantes de sorte que les deux extrémités 1/2 deviennent, oh, événement. Et parce que ces boucles sont les unes à l'intérieur des autres, nous nous multiplions. Donc, nous obtenons O de n carré pour la complexité de l'espace. En fait, nous poussons ce nombre de prix dans notre gamme de bénéfices. Donc ça doit stocker toutes les choses que ce Lou produit. Donc, cela va également être o de M carré. Ils vont être les mêmes. On n'a pas parlé de celui-là. Et cela va également être, oh de et carré parce que les mathématiques sur Max comme une boucle en soi, il doit chercher à travers le tableau entier et nous donner le plus grand nombre à trouvailles. Et la taille du tableau comme mentionné, est terminée et au carré. Ou c'est proportionnel thio de fin au carré. Donc cela lui-même va être o n carré. Et nous ajouterions cela à la valeur que nous avons obtenue de la boucle et cela nous donne oh, de deux et carrés. Et on abandonne toujours Constance. Donc, cela pourrait simplement disparaître, nous laissant avec O de n carré, qui est ce que nous avions initialement. Quoi qu'il en soit, on a commencé avec plus et au carré et on a fini là-bas, donc ça ne change rien pour nous. C' était la solution de la force brute. Et dans la vidéo suivante, nous irons sur une vidéo beaucoup plus rapide 6. Profits maximums : Traitement intelligent: dans la dernière vidéo, nous avons résolu ce problème en utilisant une solution de force brute. Nous calculons tous les bénéfices possibles qui peuvent être réalisés et nous rendons juste le maximum . Allons de l'avant et essayons ceci d'une manière différente. Alors réfléchissons à ce que nous pourrions faire pour le faire en un seul passage. Essayons d'obtenir ça à O off, et actuellement c'est et au carré, et nous avons réussi à la faire revenir et quelques fois avant. Voyons si on peut le faire cette fois. Eh bien, comment calculez-vous un profit ? Vous prenez un numéro et désolé, vous prenez un numéro et puis soustrayez un nombre avant. Comment obtenez-vous ainsi en utilisant huit. Comment tirer le maximum de profit possible de la vente à huit ans ? Eh bien, nous regardons à gauche, et nous trouverons le nombre le plus bas possible. Ce n'est pas 10. Ce n'est pas sept. Il est cinq. Donc, le maximum de profit que nous pouvons faire ici est de trois. En regardant 11. Comment trouver le meilleur profit possible que nous pouvons obtenir en vendant à 11 ans ? Eh bien, ce serait de trouver le grand nombre ici. Désolé. Le plus petit nombre ici et la vente. Donc vendre à cinq ans, nous pouvons transformer ça en code si nous gardons juste une trace du plus petit nombre que nous avons vu jusqu'à présent, nous pouvons le faire. Alors, alors que nous avançons, soustrayez le nombre que nous trouvons de ce nombre. Laissez-moi vous montrer ce que je veux dire. Donc nous utilisons juste deux variables ici pour garder une trace de ces deux valeurs tout au long de nos hommes de boucle. Le prix que nous allons supposer est l'infini et nous le mettrons à jour dès que nous avons commencé. Loop et Max bénéfice supposeront zéro et nous le mettrons à jour chaque fois que nous le devrons. - On s'assure que ça marche. C' est le cas. C' est en fait notre solution entière. Repassons à travers ce qu'on fait à nouveau. Nous supposons que le prix minimum commence à l'infini. Donc, nous disons juste fondamentalement, insérer une infinité juste ici dans cette boucle. On va le mettre à jour chaque fois qu'on aura besoin de Teoh. Alors que nous passons à travers cela, nous allons le mettre à jour. Infinity n'est pas là, donc on commence à 10 ans. Et nous disons que le prix minimum que nous avons rencontré jusqu'à présent est le prix le plus bas des hommes ou le prix actuel. Donc le plus bas de l'infini ou 10 ça va évidemment être 10. Donc les prix des hommes sont maintenant égaux. Tentative Max, le profit sera le nombre actuel que nous traitons moins le prix minimum que nous avons vu jusqu'à présent. C' est ce qui suit notre règle. Nous gardons juste une trace de ces deux tout au long de notre boucle et nous les mettons à jour chaque fois que nous en avons besoin . À la fin, nous avons Max bénéfice déjà stocké dans notre variable et affaiblir. suffit de revenir que c'est vraiment le temps et l'espace simple. Nous avons transformé une boucle double pour en une seule boucle. Et aucune de ces opérations ne prend beaucoup de temps. Ils ne sont pas linéaires ou rien de plus haut, juste des opérations à temps constant. Donc ils ne vont pas le changer. Et nous allons PDG d'une complexité temporelle O of N First space. Voyons ce que nous stockons. Nous stockons deux variables ici. Et quelle que soit la taille de ce désolé, nous n'avons pas besoin de stocker plus de données que ces deux variables. Donc c'est après que ça va passer de N carré à un. C' est la solution qui gagnerait l'intervieweur. C' est difficile et montre la capacité de gérer logiquement les nombres et le temps. Il est élégant, court et doux, et a les meilleures complexités de temps et d'espace imaginables pour un problème comme celui-ci à nouveau, Juste en gardant une trace de quelques chiffres à travers sa fonction et un peu d'intelligence, nous pouvons apporter à la fois nos complexités spatiales et temporelles considérablement je vais voir dans la prochaine vidéo. 7. Mutation unique: le problème va être une mutation unique. Nous allons écrire une fonction qui prendra deux chaînes, et nous devons déterminer si les deux chaînes sont identiques, sauf peut-être une mutation. Il existe trois types de mutations, et ce sont des insertions de relations et des ins de substitution. Une suppression est juste la dilatation d'un seul caractère et d'insertions. L' insertion d'un caractère unique et d'une substitution est un changement de caractère, les chaînes étant de la même longueur. À la fin, allez-y et essayez-le par vous-même et revenez quand vous serez prêt. Allons de l'avant et commençons ce problème, donc nous voulons commencer par écrire boucle. Mais qu'est-ce que cela a l'air bien ? On dirait ? Eh bien, à chaque étape, nous voulons essentiellement comparer exactement le même élément et les deux chaînes. Alors que nous traversons cette chaîne, nous voulons comparer le premier caractère ici au premier caractère ici, le second caractère ici au second caractère ici et ainsi de suite. Voyons comment on ferait ça. La clé utilise en fait un type de boucle différent de ce que nous avons vu jusqu'à présent. Eh bien, c'est toujours une boucle for, mais ça va être structuré un peu différemment. Allons de l'avant et écrivons les conditions. Coma. Cela peut sembler une boucle étrange, mais c'est parfaitement légal. Passons à travers ce qui se passe ici. Nous déclarons deux variables, et notre condition est que c'est plutôt une condition standard. On vient de mettre votre déposition là-dedans. Donc, si l'un de ces vrais, si l'un d'eux est vrai, notre boucle continuera et à la fin implémentait deux variables différentes. Les deux que nous avons déclarées au début. Mais nous allons discuter de la raison pour laquelle nous faisons ça pendant que nous le traversons. Nous voulons donc également créer une variable pour garder une trace du nombre de mutations que nous avons jusqu' présent. Et nous allons commencer zéro et ici, fondamentalement, quand nous voulons passer par des cordes un par 11 caractère à la fois et regarder le nombre de mutations. Alors, comment peut-on dire s'il y a une mutation ? Eh bien, nous devons vérifier si les caractères sont juste égaux. Si les caractères sont exactement les mêmes, nous ne voulons rien faire et nous voulons avec la boucle continuer. Mais s'ils sont différents, nous voulons faire quelque chose. Donc s'ils ne sont pas égaux, on sait qu'on a une mutation pour pouvoir aller à l'école et augmenter ça. Et maintenant, nous devons déterminer quel type de mutation il s'agit. S' agit-il d'une suppression et d'une insertion, ou s'agit-il d'une substitution ? Donc nous avons augmenté les mutations et il y a un autre chèque que nous voulons vraiment dio. Donc, nous avons mis en place des mutations, et si nous le savons déjà , nous devons, nous pouvons immédiatement retourner faux sinon lui-même. C' est la première mutation. Alors voici ce que nous voulons faire. Donc, ici, nous disons que la longueur du premier élément est supérieure à la longueur du deuxième élément. Donc cela pourrait être un exemple pour celui-ci ou celui-ci. Donc, s'ils sont égaux, nous voulons réellement poncer Ament la deuxième variable. Et expliquons pourquoi IHS prend cela comme un exemple. Donc nous comparons A et A dans notre boucle et ils sont identiques. Nous comparons B et C, et ce sont en fait des caractères différents. Donc nous allons entrer dans cette boucle mutations va devenir une. On va sauter ça parce que la mutation est égale à un, et on va y aller. Donc on va diminuer J. et c'est l'indice juste ici. Donc nous sommes à la prochaine dans ces deux, et nous allons diminuer l'index de la deuxième chaîne et le ramener ici. Donc encore une fois, pour la première chaîne, où à B pour la deuxième chaîne, où à un Allons à la prochaine itération de la boucle et ce rêve nous passons à voir. Et dans cette chaîne, nous voulons aussi voir Donc essentiellement, nous avons récupéré la deuxième chaîne en effectuant cette opération ici, nous comparons C deux c même si elles sont à des indices différents et ensuite nous continuons. Puisqu' ils sont identiques, nous incrémentons à nouveau les deux indices. Et de comme le même est profond. Donc nous sommes prêts à y aller. Nous savons que nous n'avons eu qu'une seule mutation et maintenant nous pouvons retourner vrai et nous avons presque fini ici. Mais que voulons-nous faire s'il y a une insertion à la place ? Eh bien, dans ce cas, alors la chaîne 1 va être plus courte qu'une chaîne à, et nous faisons dans ce cas, par exemple, pour celui-ci, nous voulons réellement un pont Ament, l' autre variable, et cela nous mettra à nouveau sur la bonne voie. Vous pouvez aller de l'avant et passer par cela par vous-même et élaborer cette logique. Mais ça marche. C' est toute la fonction. Allons-y et testons ça. On va aller de l'avant et l'utiliser. Donc, ici, nous nous attendons à voir vrai. Eh bien, c'est essayer un de chacun de ces courir à nouveau. Vrai. Et essayons ça, euh, a fait une erreur là-bas, et c'est vrai. Et pour nous assurer que cela fonctionne, essayons aussi quelque chose qui ne fonctionne pas. Ça ne devrait pas marcher. Donc, ici, nous avons deux ajouts, donc cela devrait être faux, et nous voyons que c'est faux. Essayons de le faire. La substitution est à la place donc un BCD devient un x x x d. Et encore une fois nous obtenons faux. Et essayons à nouveau de supprimer false. Donc, cela fonctionne. Allons de l'avant et passons en revue les complexités temporelles et spatiales de cette fonction. Donc, dans le pour les allaient de I égal à zéro à la longueur de la chaîne. Les cordes I et J, nous n'utilisons qu'une seule boucle ici et dans cette boucle, aucune de ces opérations n'est linéaire l'air, toutes les opérations à temps constant, donc elles ne vont pas changer le temps de complexité de notre boucle. Nous devons juste comprendre quelle est la complexité temporelle de cette seule boucle, et ça va être linéaire. Donc généralement les cordes. Nous allons avoir une longueur similaire tout à fait similaire. Et donc nous pouvons dire que N est juste la longueur de l'une ou l'autre chaîne. Dans ce cas, la complexité temporelle va être juste, oh de N. Vous pouvez soutenir que nous en traversons deux fois plus parce que nous avons affaire aux deux variables, moi et J. Mais ce serait juste multiplier cela par deux, et nous nous débarrassons de la constante de toute façon, Donc cela nous laisserait avec une complexité temporelle de o de n et quelle est la complexité de l'espace ? Eh bien, peu importe la durée de ces chaînes, nous ne stockons que trois variables I J et Mutations. Donc ça va vraiment être un espoir qui a aidé. Et j'espère que cela a du sens et je verrai dans la prochaine vidéo 8. Détecter les anagrams: vous tous les anagrammes. Les instructions ici sont de prendre un tableau de chaînes et de retourner. True si toutes ces chaînes sont des anagrammes les uns des autres, anagrammes signifient qu'elles ont les mêmes caractères dans la chaîne, mais qu'elles peuvent être dans un ordre différent. Voici quelques exemples, ces trois sont tous des anagrammes les uns des autres. Ils contiennent tous un, B, C et D, et ils sont dans un ordre différent. Dans l'exemple suivant, nous avons un X ici, ce qui signifie qu'ils ne sont pas tous des anagrammes, donc nous voudrions que la fonction retourne False et les deux suivants sont assez similaires à ceux-ci. Allez-y et essayez-le vous-même et commençons à utiliser la solution ici. Donc, comme mentionné un anagramme ou plutôt, anagrammes, nos chaînes qui ont les mêmes caractères, mais peut-être dans un ordre différent. Alors, quelle est une façon de comprendre si deux cordes sont des anagrammes ? Nous pourrions tenir compte de chaque caractère, et nous pourrions vérifier ces comptes à la fin une fois que nous aurons traité les chaînes. Mais il y a un moyen un peu plus simple, et on va y aller. Tout d'abord, nous pouvons vraiment trier ces caractères. Donc, par exemple, si nous trions un B c D, il restera exactement comme il est. Si nous trions cette prochaine bague, elle se transformera en B C et fera la même chose pour celle-ci, et elle deviendra aussi un BCD. Les chaînes, après les avoir toutes triées, deviennent exactement la même chaîne. Donc, si nous trions les anagrammes les uns des autres, ils devraient tous devenir exactement la même chaîne, et nous pouvons l'utiliser à notre avantage. Allons-y et commençons. Où va trier chaque chaîne de notre rayon en utilisant la fonction de carte ? Donc, nous avons une chaîne et nous voulons d'abord la diviser en un tableau. Donc maintenant, nous avons un tableau de caractères. Ensuite, nous utilisons la fonction de tri, puis nous joignons ces caractères dans un tableau, et cela contiendra les chaînes, toutes sortes de ensemble. Faisons en sorte qu'on ait bien compris, et c'est testé avec celui-ci. Oups, ça a l'air juste. Donc, non, nous devons le faire. Passons à travers ces cordes et une boucle, et nous devons nous assurer qu'elles sont toutes égales, comme nous l'avons dit précédemment, et nous devons vouloir commencer à zéro. Nous sommes désolés un. C' est toute notre solution. Et pour s'assurer que cela fonctionne encore, nous devions vrai. Essayons tout ça. Donc, en les faisant un à la fois ici, on s'attend à faux ici, on s'attend à vrai. Et ici, nous attendons à nouveau faux et cela fonctionne. Et qu'en est-il des complexités temporelles et spatiales ? Pour le temps, nous allons devoir considérer cela en termes de deux variables différentes. Normalement, nous utilisons juste n et nous disons plus et ou au carré ou autre. Mais ici, nous allons dire que s est la longueur des chaînes et A sera le nombre de chaînes dans la course ou juste la longueur du tableau. En effet, les complexités temporelles et spatiales sont extrêmement dépendantes de ces deux variables. Il est juste logique de les utiliser tous les deux. Quand on parle de ces complexités temporelles, du temps et de l'espace. Donc la complexité du temps. Passons à travers celui-ci ici. Nous avons une chaîne, pas divisée. Encore une fois, une carte est une boucle. Donc, cela va déjà être oh puisque nous passons sur le tableau et alors tout ce que nous faisons ici sera multiplié par cela parce que c'est à l'intérieur de la boucle. Donc, trier une seule chaîne va être s fois Log of s une opération de tri est généralement considéré comme n fois long de fin et ici va être la longueur de notre chaîne. rejoindre à nouveau va être Il va être Oh, de S qui est la longueur de la chaîne à nouveau Donc nous pouvons réellement les ajouter ensemble. Donc diviser je pense que j'ai complètement oublié la partie fendue qui va aussi être juste s si s pour fractionnement s fois Log de s pour le tri et s à nouveau pour rejoindre comme plus s long autre plus s Et nous pouvons réellement simplifier cela et à un temps à s plus termes Journal de cela et tout ce terme peuvent effectivement disparaître parce que s times log of s est d'ordre supérieur à oui. Puisque ces deux variables sont différentes et nous, nous devons les garder tous les deux. Cela donne un journal fois fois s de s pour notre temps, la complexité. Et l'espace ? Eh bien, nous stockons toute une gamme d'articles et ce tableau sera de la même longueur que notre Valerie initiale. Donc ça va être oh, d'une longueur du tableau. Et chacune de ces chaînes sera en fait la même longueur que les cordes originales. Donc ça va être un moment. C' est parce que nous stockons les mêmes chaînes de nombres, puis les chaînes. On va être le même lien. C' est donc notre temps dans les complexités spatiales pour la solution. Dans la vidéo suivante, nous allons passer en revue une autre solution et essayer d'améliorer un peu les deux. On se voit là-bas. 9. Traitement rapide des Rapid d'architecture rapide: bienvenue à tous les anagrammes. Dans la dernière vidéo, nous avons écrit une solution qui, à une sorte, chacune des chaînes, puis déterminer si les chaînes étaient toutes égales les unes aux autres. Ici, nous allons travailler un peu sur notre solution et faire tomber ces complexités temporelles et spatiales qui semblaient un peu compliquées dans la dernière vidéo. Donc, au lieu de trier, nous allons essayer une autre stratégie, et cette stratégie va compter les occurrences de chaque personnage individuel. Ainsi, par exemple, en prenant la Serie, nous allons vouloir créer un objet qui nous indique combien de chaque caractère sont dans cette chaîne. Nous allons vouloir faire la même chose pour la chaîne suivante et nous assurer que ces deux objets sont les mêmes ou qu'ils ont l'air exactement le même et faire la même chose pour cette troisième chaîne et encore et encore. Et nous devons juste nous assurer que ces objets gardant une trace de nos personnages exactement les mêmes pour chaque chaîne du tableau a été donnée. Allons-y et commençons. Donc on va avoir besoin d'un lupas habituel. Et qu'est-ce qu'on veut faire ici ? Eh bien, nous voulons créer un objet avec le nombre de caractères de la chaîne. Et comment on fait ça ? Eh bien, et nous l'avons fait quelques fois avant quand nous devons commencer par créer un objet et ensuite nous agirons. Tu vas avoir besoin d'une autre boucle. Cette boucle va ressembler à ça. - C' est assez simple. Nous l'avons fait plusieurs fois jusqu'à présent. C' est juste une boucle qui va remplir cet objet avec le nombre de caractères de n'importe quelle chaîne que nous transmettons. Si c'est la première fois qu'on traite le personnage, il ne sera pas encore dans notre objet. Et quand on le cherchera, on sera indéfinis. Ensuite, nous voulions définir sa valeur à un. S' il a déjà un nombre signifiant qu'il existe déjà dans notre objet. Nous voulons simplement augmenter ce nombre d'un. On peut nettoyer ça un peu juste pour le rendre plus facile à lire. Et juste pour s'assurer que nous avons bien fait, consul objet journal. Donc, l'exécuter avec seulement ces trois cordes et il semble que cela fonctionne exactement comme nous voulons bien savoir. Donc nous avons cet objet et que voulons-nous en faire ? Eh bien, nous voulons le comparer avec un autre objet pour une autre chaîne. Et comment obtenons-nous cet objet ? Eh bien, affaiblir, juste faire ça avant la boucle quatre. Donc, ici, dans notre boucle, nous pouvons réellement commencer avec l'élément un, ce qui signifie que nous allons commencer avec cette chaîne. Et avant de commencer la boucle, nous pouvons aller de l'avant et créer l'objet pour cette toute première chaîne. Donc essentiellement, nous voulons créer un objet pour la première chaîne. Et cela va en fait suivre juste toute cette logique, sauf au lieu de cela, au lieu de la chaîne, cela va être des chaînes est zéro. Non, ce que nous avons ici, c'est que nous avons essentiellement le même code écrit deux fois. Une bonne chose à faire serait d'extraire cela dans une autre fonction afin que nous puissions aller de l'avant et le faire . Il va nous aider et le nettoyer pour citer un peu. - Et ça devrait marcher pour que nous puissions aller de l'avant et nous débarrasser de tout ça et utiliser notre nouvelle fonction. Je ne peux pas me débarrasser de tout cela et de la fonction utilisateur à nouveau. Non, nous comparons. L' objet serait généré ici avec l'objet généré apparaît qui va être pour la première chaîne. Nous devons nous assurer que chaque propriété de ces objets est équivalente. Et nous devons le faire avec une autre boucle. - Presque là. Maintenant, ça devrait marcher. Allons-y. Et on est sur le coup juste pour s'assurer qu'on sort de vrai. Essayons celui-ci tombe vrai et faux. On dirait que ça marche. Donc, nous avons vu que notre fonction fonctionne pour ces quatre. Mais laissez-moi vous montrer un exemple où notre fonction renvoie réellement le mauvais résultat. Donc, si nous avions un genou ici et nous l'exécutons, j'ai besoin d'un commentaire ceux-ci sur. Nous nous attendons à des chutes parce que cela a un e supplémentaire ce qui signifie que ces trois ne sont pas des anagrammes, mais nous revenons vrai. Et c'est parce que ce que nous faisons ici c'est que nous créons d'abord un objet pour le premier personnage. Comptez la première chaîne que nous obtenons. Excusez-moi. Donc cet objet va ressembler à ça. Il a un travers e et chacun en a un. C' est ce qu'on veut maintenant ici. Comme vous pouvez le voir, nous manquons le donc nous avons le e dans la première chaîne, mais pas sur la 2ème 2 cordes, et nous pouvons voir que tout ici. Maintenant, le problème est dans cette boucle, tout ce que nous faisons est de retour vérifiant les caractères que nous voyons dans ces deux objets. Donc, nous vérifions pour voir si un dans les poils égaux orteil un et c'est B est égal à un. C est égal à un, et D est égal à un. Nous ne vérifions pas qu'il n'y a pas d'extras. Donc, cela passe en fait sont vérifier un qu'il ne devrait pas. Et il y a quelques choses qu'on peut faire pour contourner ça. Ce que nous allons faire est probablement l'un des plus faciles et l'un des moins exigeants en temps . Donc on va aller de l'avant et faire ça. Et ce que nous voulons faire est de créer une autre boucle pour passer à travers la chaîne. Désolé. Passez par le tableau et assurez-vous juste que toutes les chaînes ont la même longueur. Assez simple, nous commençons à un et allons vers la fin et assurez-vous que tous les articles longueurs Donc encore une fois , nous savons que nous nous attendons à ce que cela retourne faux, et nous obtenons faux retour. Donc nous avons réparé notre code. C' est ça. C' est toute notre fonction. Examinons les complexités du temps et de l'espace. Donc, pour le temps commencerait avec le top live que nous avons ici. Nous avons beaucoup d'un Nous sommes en boucle à travers le tableau entier et nous assurons que les chaînes sont la même longueur. Donc c'est juste une boucle à travers le tableau ici. Voyons la complexité temporelle. Oublie le nombre de voitures Nous traversons une boucle et traitons tous les caractères de la chaîne. Donc, il va y avoir une boucle standard qui prend un lien qui prend du temps proportionnel à la longueur de la chaîne. Donc, il va y avoir Oh, de s, cela signifie que toute cette chose est Oh, de s, ce ici va être plus un puisque c'est une boucle sur tout le tableau et puis ceci et ici va être sur s donc cela se transforme en un temps s Celui-ci ici est aussi de s Donc c'est o de huit fois deux s, mais la constante est abandonnée. Donc on a juste un de s. et c'est notre dernière fois. Complexité pour l'espace. Non, peu importe la taille des chaînes A est Tout ce que nous faisons est de créer juste quelques variables que nous créons. Je crée le premier conseil de voiture. C' est un objet. Laisse-moi me débarrasser de ça. C' est pour que je ne me confond pas. Donc ici je Cette boucle entière va juste en déclarer un très I Donc nous pouvons ignorer que Ceci ici va être Oh, de s parce que nous avons un objet rempli avec les nombres de caractères d'une chaîne et que la taille de l'objet va être proportionnelle à la longueur de cette chaîne. Il va y avoir un Nove ici. Nous pouvons créer une variable I, qui a été significative. Et ici, nous créons une autre variable, Oh, qui va aussi être sur s. C'est un objet qui est proportionné en taille à la longueur de cette chaîne. Donc et dans cette boucle quatre, on ne fait rien, euh, euh, avec de l'espace. Nous ne créons pas vraiment d'objets ici ou de variables du tout. Donc, nous avons un no de s et un autre o de s. et ceux-ci vont être ajoutés ensemble parce que cela reste pour la longueur de la fonction pour la longueur de la fonction restante. Et cet objet ici est généré lorsque nous démarrons la boucle, puis supprimé une fois que la boucle se termine. Donc, cette boucle Onley génère l'un des objets à la fois, donc au plus à un moment donné, utilisaient O de s plus s espace, ce qui nous donne au large de s, ce qui simplifie jusqu'à O de s. Et c'est la finale complexité de l'espace pour cette fonction. Voir la leçon suivante. 10. Tournage d'une matrice carrée: problème. Rotate, matrice, matrice et script Java peuvent être représentés comme un tableau d'une augmentation. Et voici un exemple. Nous avons un seul tableau externe qui est désigné par ce support dans ce crochet ici et ici. Nous avons trois tableaux, chacun avec trois éléments en eux, et cela constitue une matrice trois par trois. Notre objectif ici est d'écrire une fonction qui prendra cette entrée. Donc, l'entrée va être ce tableau de tableaux et génère une nouvelle matrice. Donc, nous voulons que la fonction retourne un tableau d'une augmentation et que la nouvelle matrice qui est retournée devrait être la même que celle-ci a tourné à 90 degrés. Cela devrait fonctionner pour les matrices carrées et rectangulaires. Donc, fondamentalement, majeures de toutes les dimensions pour l'exemple donné cette matrice comme entrée et nous pouvons ignorer ces indices d'air juste orteil juste pour voir où ces nombres sont situés. Étant donné cette matrice en entrée avec ce tableau de trois tableaux, nous voulons que notre fonction produise cette matrice. Comme vous pouvez le voir, tout est juste tourné de 90 degrés dans le sens des aiguilles d'une montre. Celui est déplacé vers la droite, trois descend, le neuf va à gauche et le sept monte et tout le reste se déplace avec les quatre. Désolé, les deux mouvements vers la droite et vers le bas les six mouvements vers le bas et vers la gauche et sur et sur. Donc, essentiellement, nous devons faire pivoter cette matrice de 90 degrés dans le sens des aiguilles d'une montre. Allez-y et essayez la salade par vous-même. C' est assez amusant, et ce n'est pas terriblement difficile, mais revenez quand vous êtes prêt. Lorsque vous avez essayé le problème, allons-y et commençons à le résoudre. Donc, le problème indique que la matrice d'origine devrait rester inchangée. Et ce que cela signifie, c'est que nous voulons créer une nouvelle matrice à retourner. Nous ne voulons pas simplement déplacer les choses dans l'original, mais nous voulons en faire un nouveau. Alors créons ça. Donc, nous allons juste commencer avec un tableau et comment remplir cette matrice ? Commençons par une matrice carrée pour l'instant. Examinons ces trois par trois que nous avons déjà. Donc, si nous avons un trois par trois est entrée. Nous savons que nos sorties seront trois par trois. Si nous avons un quatre par quatre. Est-ce que les sorties vont être un quatre par quatre. Donc le nombre d'une augmentation ici et notre nouvelle matrice sera le même que le nombre d'une augmentation dans l'ancienne matrice. Et nous pouvons comprendre qu'en utilisant la propriété length, ce tableau externe a une longueur de trois car il a trois éléments à l'intérieur. Nous pouvons donc l'utiliser pour créer le même nombre de lignes pour cette nouvelle matrice. Et c'est notre nouvelle Matrix aura le bon numéro d'une course dedans. Et nous allons nous assurer que nous faisons cela correctement au fur et à mesure et nous allons donner un exemple. Va voler ça. Ok, là. Nous avons donc un tableau de trois courses comme prévu. Nous savons maintenant aussi à la fin que nous devons retourner cela afin que nous puissions simplement écrire cette déclaration. Et maintenant, qu'est-ce qu'on fait au milieu ? Nous devons juste remplir la matrice avec les bons chiffres, et nous allons le faire en boucle à travers Les Matrix ont été donnés. Donc nous sommes en boucle ici et nous allons vraiment devoir faire une boucle à l'intérieur de chaque pressé intérieur . Donc en ce moment, nous sommes en boucle à travers ce tableau externe et le rôle actuel où va être celui-ci ? Et puis les boucles vont passer à celle-là. Et dans celui-ci, nous devons également regarder à travers chacun de ces chiffres pour arriver à ces chiffres individuellement. Ici, nous utilisons la longueur de point zéro mat. En fait, cela peut juste être changé en maths ce lien. C' est la même chose, parce que pour l'instant nous sommes juste concentrés sur les matrices carrées, et le nombre d'éléments ici sera le même que le nombre total d'une augmentation. Donc ça va marcher pour nous très bien. Et maintenant, pour la partie difficile, nous devons vraiment trouver comment déplacer les objets au bon endroit. 11. Tournage d'une solution de matrice carrée: Bienvenue de retour. Continuons à travailler sur ce problème. Jusqu' à présent, nous avons établi les bases, et maintenant nous avons juste besoin d'un algorithme pour réellement déplacer ces pièces au bon endroit. Et allons de l'avant et travaillons là-dessus et pour des exemples. Par exemple, commençons par une simple matrice deux par deux, donc je vais juste aller de l'avant et en utiliser une, aussi. Cela nécessite un autre support et 34 et cela doit se transformer en 31 quatre à, et c'est une rotation de 90 degrés. Alors allons de l'avant et cartographions les changements de position réels qui se produisent. Et qu'est-ce que tu veux dire par là ? Est-ce donc un ici est à la position 00 C'est à la ligne à l'index zéro dans cette ligne. C' est à la colonne zéro donc on peut dire 00 se déplace à toujours dans la rose zéro. Donc ça reste le même, et c'est connu Colonne 1. Donc ça va passer à 01 et faisons ça pour les trois autres aussi. Donc on a un objet à 01 déménage à 11 et on obtient un objet à 10 Déménagement à où est passé ? Déplacez 200 et 11 déménageons à 10 et ça a l'air juste. Donc, à partir d'ici, nous pouvons réellement aller de l'avant et créer un algorithme. Si on fait ça pour trois par trois ou quatre par quatre, ou n'importe quelle matrice carrée, on va obtenir les mêmes résultats. Et ces résultats seront régis par une règle mathématique simple, qui va être la suivante. Pardonnez-moi pour le type de vie et juste pour être sûr que nous faisons ça correctement, je vais attendre. Donc 741 852 963 C'est exactement ce que nous voulons. Et nous allons vous montrer comment cela fonctionne réellement. Allons brancher quelques numéros. Donc, en branchant 00 ici sur le côté droit, on a une nouvelle matrice, donc Jay est positionné. Zéro. Alors, c'est des jours. Ajouter zéro. Donc c'est correct. Le tout premier élément sera zéro, et le deuxième élément sera la longueur de point mat. Donc la longueur de cette matrice est, euh, longueur deux. Il y a trois éléments, mais sa longueur à deux moins un est un moins I, ce qui est zéro puisque nous commençons à 00 Donc 00 branché ici conduit 20 virgule une sur le côté gauche. Donc, nous avons réellement tourné 00 et 201 Nous avons déplacé l'article de 00 à 01 Nous pouvons le faire pour le reste d'entre eux. Nous pouvons brancher 11 ici, et ce que nous obtenons est un dans la position gauche et Matt en longueur à moins un moins un . On a zéro ici, donc on a eu 11 ans en 210 Vas-y et branchez ces deux-là. Ou essayez tout ce que vous voulez. Cela fonctionnera chaque fois que nous avons résolu ce problème pour les matrices carrées et dans la prochaine leçon va aller de l'avant et essayer de l'appliquer à toutes les maitresses. Facilité. Voir là. 12. Tournez de matrices : Deux problèmes de bonus: bienvenue dans la dernière leçon. Nous avons effectivement fini ce problème. Mais je veux aller de l'avant et vous donner un petit bonus. Donc, le premier problème de bonus va être correct. Une fonction que tous les rotateurs matrice 180 degrés. Et le prochain aura raison. Celui qui fait pivoter 270 degrés. Vous pourriez aussi penser à celui-ci comme négatif 90. On a déjà celle-là. Je l'ai effondré. Teoh, fais de la place pour les autres. C' est exactement la même fonction que nous avions auparavant et rien n'est différent. Je suis juste en train de l'effondrer. Et ce sont les résultats attendus pour cette matrice. Donc tourné 90. Nous voulons ce 80 Vous voulez ces 2 70 ? On veut ça. Tout ce que nous avons à faire est d'écrire les deux fonctions. Il y a plusieurs façons de les faire. Allez-y et essayez si vous voulez. Si vous voulez aller de l'avant et juste regarder la vidéo, vous pouvez le faire aussi. Puisque ce n'est qu'un bonus, je vais le laisser glisser. Voici comment je vais résoudre ce problème. Et c'est un fait. Et cela est aussi fait et est de s'assurer que ces alignements au cours de 14 à 4321 2413 Et nous sommes bons. Tu crois que c'est de la triche ? Moi aussi, je le fais . Mais le fait est que ça n'a vraiment pas d'importance. Ces fonctions fonctionnent, et elles fonctionnent parfaitement bien. Et il y a en fait des raisons que vous préférez ceux-ci plutôt qu'une autre grande fonction comme celle-ci. Votre ressource la plus précieuse en tant que développeur est votre propre temps. Ce n'est pas le temps que la machine prend pour exécuter votre code. Ces résultats sont fulgurants. J' avais couru et avant de penser que les résultats sont là, et ça va arriver pour presque toutes les fonctions que vous écrivez dans toute votre carrière. Ordinateurs air rapide Les gens sont lents, donc vous voulez passer votre temps à écrire le moins de code possible. Nous avons écrit une fonction qui fonctionne parfaitement, et nous savons que cela fonctionne. On l'a un peu testé. Pourquoi ne pas le réutiliser ? Si on le peut, on le réutilise. Nous l'appelons deux fois, et il tourne notre fonction de 1 80 degrés. Nous l'appelons encore une fois, et il le fera 270 degrés plutôt que d'écrire le même code essentiellement avec quelques différences à nouveau et potentiellement introduire des bogues. Lorsque nous essayons de le faire, nous pouvons utiliser la seule fonction que nous connaissons, fonctionne et économiser une tonne de temps en faisant cela de la manière facile au lieu de la manière difficile, les complexités temporelles des fonctions vont être les mêmes que l'original. Alors tu te souviens de ce waas pour le temps ? Oh, de n et celui-ci va être, nous le faisons juste deux fois. Donc deux fois dans et nous tombons constants, donc ça va être dedans. Quoi qu'il en soit, celui-ci allait être trois fois dedans, ce qui va encore se transformer en oh, alors l'espace va être la même chose. Donc la complexité de l'espace pour celui-ci était terminée à l'époque, parce que lorsque la création d'une matrice entièrement nouvelle avec les mêmes éléments ici, il va être aussi de nouveau dans. Nous avons été multipliés par deux. Puisque la fonction est appelée deux fois, nous en avons deux et la mémoire à la fois, et la complexité de l'espace va également finir par être de la même chose pour celui-ci. C' est ça. J' espère que c'était amusant. Et je vous verrai dans la prochaine vidéo où nous apprenons comment faire pivoter une matrice en place . Et ce que cela signifie, c'est que nous ne pouvons pas créer d'augmentation ou de structures de données supplémentaires dans notre fonction. C' est un problème beaucoup plus difficile, et on va devoir tout réécrire, donc je te verrai là-bas. 13. Sur place la rotation de matrices - Stratégie: bienvenue au prochain problème. Faire pivoter la matrice en place. C' est exactement la même chose, c'est le dernier problème. Sauf dans ce cas, nous savons qu'on va toujours avoir une matrice carrée, ce qui signifie trois par 3555 10 par 10 peu importe. Et notre objectif est de le faire tourner à 90 degrés dans le sens des aiguilles d'une montre. Mais cette fois, nous devons le faire en place. Et la clé de ce qui signifie en place est que vous ne pouvez pas créer de matrices supplémentaires ou une augmentation dans votre fonction ou toute autre structure de données. Vraiment. Tout ce que vous pouvez stocker, ce sont des variables. Allez-y et essayez cela par vous-même si vous voulez. Je vais vous avertir. Celui-ci est très difficile. Et même une fois que vous comprenez comment le faire, le code est très difficile à écrire. Donc je vais résoudre ça en deux problèmes. allons d'abord passer en revue et discuter de la stratégie que nous allons employer, puis nous allons vous montrer du code. J' ai un petit carnet de croquis ici. Oups. Et prenons cette matrice comme entrée et discutons simplement de la stratégie que nous allons utiliser. Donc, ici, nous avons une matrice de cinq par cinq et nous allons juste utiliser ceci comme exemple. Maintenant, je vais aller de l'avant et enlever le périmètre essentiellement de la matrice. On va faire semblant que l'intérieur n'existe même pas. Tout ce qui nous intéresse, c'est les rangées et les colonnes extérieures de Thea. Et ce qu'on veut dio, c'est ça. Nous voulons prendre le numéro en haut à gauche et le déplacer ici. Donc on veut déplacer ça ici. Mais avant de le faire, nous devons déterminer ce qu'il faut faire de ce chiffre. On ne peut pas le remplacer parce que ce numéro doit se déplacer ici et celui-ci doit aller par ici. Et enfin, celui-ci doit aller ici pour compléter notre petit cercle. Donc, au moment où nous l'avons fait, Fives a déménagé ici, 20 5 ici et 20 ici. Nous avons fait une rotation complète de 90 degrés des coins, donc ces coins ont été complètement tournés. Maintenant, ce qu'on va vouloir faire, c'est continuer. Alors commencez ici et on va devoir déplacer ce type ici et le 10 va passer à l'endroit de 24. 24 va passer à 16 et le 16 va remplacer là où les deux étaient partis à l'origine. Donc maintenant, nous avons de l'avance, et nous avons tourné les 2/5 de tout ce périmètre extérieur, et nous avons besoin de la moitié. Désolé, parce que nous nous en soucions seulement quand il doit faire ça quatre fois. Donc, quand vous le faites pour les coins, puis cet article dans cet article et ensuite les quatre ici , nous avons déjà fait les cinq qui ont déjà été pris en charge. On avait juste besoin de ça quatre fois. C' est ce que nous allons avoir besoin de coder une fois que nous serons en mesure de répliquer cela et je ne dessinerai plus les flèches parce que cela rendra cela inutilement déroutant. Mais une fois que nous avons pensé qu'une fois que nous avons fait cela, nous pouvons passer à la rangée suivante. On n'est pas la prochaine rangée. Désolé. Prochain périmètre. Donc je vais aller de l'avant et sortir ça d'ici, et j'essaierai de le déplacer un peu plus bas et de revenir au crayon. Donc, une fois que nous avons fini avec le périmètre extérieur, ce qui signifie qu'il est entièrement tourné, nous pouvons passer au périmètre intérieur suivant, et nous voulons juste faire la même chose exactement. Déplacez ce type ici. Déplacez ce type ici et encore. Et une fois que nous pourrons le faire, nous pourrons passer à la suivante. Dans ce cas, puisque nous n'avions qu'un 555, le tout dernier périmètre sera le numéro 13 par lui-même. Et nous pouvons laisser cela, comme c'est donc nous n'avons besoin que de le faire deux fois. Dans ce cas, si c'est sept par sept, il faudra le faire une fois de plus si c'est un neuf par neuf, puis une autre fois. Mais c'est la stratégie que nous devons coder. Allez-y et essayez-le par vous-même. Et dans la leçon suivante, nous allons vous montrer la solution et montrer comment elle fonctionne. 14. Sur place la rotation de matrices - Solution: bienvenue pour faire pivoter la matrice en place. Plutôt que de résoudre ce problème. Vivre comme nous l'avons fait pour le passé plusieurs problèmes, j'ai pensé qu'il serait préférable de simplement montrer la solution et d'en parler. Ce problème est peut-être le problème le plus difficile du point de vue technique dans tout ce cours. Donc, plutôt que de fouiller sur mon manteau, mon code alors que je fouille en essayant de vous l'expliquer, j'ai pensé qu'il serait plus facile de l'écrire et de l'expliquer après juste pour m' assurer que cela fonctionne. Allons-y et courons-le. Donc, pour cette matrice ici, nous attendons cela comme sortie. Et si j'avais couru une fois de plus, on a la même chose et c'est exactement ce qu'on attend, qui est bon. Allons de l'avant et vous montrer le code et parler de ce que chaque ligne fait. Donc mensonge 21 Ceci est variable. Total layer va contenir un nombre qui nous indique le nombre de couches que nous devons traverser . Et ce que je veux dire par une couche, c'est chacun de ces éléments. Donc, ici, ce périmètre est une couche que nous voulons traverser. Nous voulons faire pivoter chaque élément de ce périmètre, puis passer à la couche suivante, qui sera ce cercle intérieur juste ici. Donc si nous avons une matrice qui est cinq par cinq. Nous avons seulement besoin de passer par deux couches. Et cette formule ici nous dira que l'intérieur pour boucle, nous allons de zéro au nombre de couches, comme nous venons de le mentionner. Et ça a du sens. Et cette ligne ici détermine la condition d'arrêt de notre boucle interne for. Et la façon dont cela fonctionne, c'est que nous allons commencer à la couche plus un. Ce que ça veut dire, c'est qu'on commence. Donc, quand commençons par cette matrice couches essentiellement va initialement à zéro. Donc nous disons que nous voulons commencer à l'index 1, ce qui signifie au 02 ici la condition d'arrêt, qui va être la longueur de point mat moins couche, signifie que nous voulons arrêter à cinq moins zéro. Donc on veut s'arrêter ici. Donc, quand nous avons traversé cet exercice, nous avons commencé à 01 et nous avons fini Oh, car notre boucle commence à 02 et se termine à 05, ce qui fonctionnera exactement de la même façon. Donc, nous avons déplacé les deux à la dizaine, placez que 10 à 24 24 à 16 et 16 à 2, puis nous passons aux trois et tourné, puis le quatrième et puis dernier de tout ce que nous faisons les coins. Ce code ici fait tout le levage lourd. Donc, quand nous déplaçons les deux vers le 10, nous allons devoir stocker le 10 dans une variable avant de pouvoir le remplacer par deux. Si on le remplace, alors on en perd 10. Nous devons donc stocker ceci et mettre à jour sa valeur. Nous devons alors stocker le 24 ici, et nous devons le remplacer par le 10. Nous allons donc avoir besoin de deux variables différentes. Tempel un et essayer de temp un va stocker le 10 initialement et le tempérament à va stocker 24 va tourner leur utilisation Donc le 10 va se déplacer ici, et nous allons frapper ça en une variable. Puis 24 va passer à 16 que nous allons stocker dans une variable et ensuite 16 va passer à l'endroit où il est heureux. Vous devez probablement passer par une rotation matricielle à la main pour observer comment cela fonctionne. Gardez une trace de chacune des variables et gardez une trace de ce qui se passe littéralement. Essayez de dessiner une matrice sur un morceau de papier et passez par ce code. Une fois chacun d'entre eux permuté et que le calque entier est tourné, cette boucle interne va être terminée, et cette boucle externe va s'incrémenter. Donc on va passer à cette couche, et on va faire exactement la même chose. Donc notre boucle va commencer au huit et se terminer au neuf qui va faire tourner le A pour le déplacer au 14 déplacer le 14 en avant et en avant, et puis il va faire les coins après ça. Alors ça va passer le neuf au 19 et encore et encore et encore à la fin. Nous venons de retourner la même matrice exacte qu'on nous a donnée. Quelles que soient les complexités temporelles et spatiales, nous ne traitons chaque élément qu'une fois que nous faisons pivoter un calque, puis nous passons à la couche suivante, la complexité temporelle va être hors de l'espace. Complexité. Eh bien, nous ne créons pas une seule structure de données nulle part ici. Tout ce que nous faisons, c'est utiliser des variables. Peu importe la taille de la Matrice. Nous utilisons le même nombre de variables, donc cela va passer à O d'un. Celle-ci est rude. Si vous le demandez dans une interview, vous serez probablement invité à simplement donner la stratégie générale que vous utiliseriez et peut-être parler un peu de l'efficacité. faire correctement pourrait prendre de bonnes heures de programmeur, ce qui serait beaucoup trop long pour une entrevue. Ce problème est grand pour nous faire réfléchir à la façon de transformer spatialement les données. La capacité à comprendre la solution montre de puissantes compétences de raisonnement et un excellent raisonnement spatial. Si c'est trop complexe, essayez d'y revenir une autre fois. Essayez de parcourir la fonction en utilisant une matrice simple comme deux par deux ou trois par trois. Gardez une trace de chacune des variables et de ce qui se passe à la matrice. Allez-y et essayez-le vous-même pour n'importe quelle matrice carrée que vous aimez. Je te verrai dans la prochaine vidéo