Domine a entrevista de JavaScript | Parte 2: cordas e matrizes avançadas

1. Introdução: Meu nome é Sarnoff, e eu sou um engenheiro de software completo e instrutor de engenharia. Eu disse a engenharia de software em um campo de treinamento de codificação, e algo que eu notei repetidamente foi que os estudantes estão se formando, embora extremamente brilhantes e capazes de construirsites poderosos e dinâmicos, sites poderosos e dinâmicos, não estavam prontos para o tipos de perguntas que viram em suas entrevistas. Depois de assistir esses alunos lutarem com perguntas típicas da entrevista, decidi criar e coletar perguntas que os alunos pudessem ver em suas entrevistas. E eu entreguei-os. Foi prática extra para os alunos tentarem. Eles repetidamente me disseram o quanto os problemas os ajudaram a ver os buracos em seu conhecimento e os derrubaram com as habilidades que precisavam. Este curso é o culminar dessas perguntas. Quase todos estes problemas são variações de perguntas que eu próprio me fizeram, ou que outros que eu conheço foram questionados em entrevistas. Bem, você não verá essas perguntas exatas em suas entrevistas. As estratégias que você aprende resolvendo-as nosso público são aplicáveis em quase todos os problemas que você receberá. Aqui está a estrutura geral do curso normalmente vai começar criando um algoritmo de força bruta que resolve bem o problema, em seguida, refiná-lo até que possamos otimizar o tempo ou a complexidade do espaço ou ambos. No final do curso, você terá dominado várias estratégias algorítmicas que você pode aplicar em uma ampla gama de problemas. Aprenderemos maneiras de analisar criticamente os algoritmos que criamos e descobrir, transformá-los para reduzir a quantidade de tempo que levam. Isso é exatamente o que um entrevistador está procurando. Existem alguns requisitos para este curso. , Primeiro, você deve ter um conhecimento básico de JavaScript e a capacidade de escrever código significativo com ele. Você também deve estar familiarizado com conceitos básicos ES 2015, tais funções zero e as palavras-chave Let e Const. Você deve ter alguma idéia do que os termos, tempo e complexidade do espaço significam. Tudo bem se você não sabe exatamente o que eles são, já que nós vamos procurar em detalhes para cada solução. O editor de código que uso nos meus vídeos é Ripple. Uh, você pode chegar lá indo para Rebelder dot i t slash linguagens slash javascript, e a razão pela qual eu uso isso é porque é simples e funcional, e vamos você focar no seu código, mas você é claro, livre para usar qualquer editor de código que você gosta. O projeto para este curso é escolher qualquer um dos problemas abordados na aula. Há um total de cinco listados aqui e compartilhar sua própria solução. Existem 1000 maneiras de resolver qualquer um desses problemas e a classe se beneficiará de ver sua versão. Bem-vindo ao curso. Estou animada para te ensinar o que sei e para te ajudar a superar as entrevistas. Quando estiver pronto, te vejo no primeiro problema. 2. Array.: O próximo problema é um subconjunto de raios para esse problema. Nossa função vai receber dois argumentos que serão ambos um raise, e essas matrizes só conterão números e strings. Nosso objetivo é descobrir se o segundo array é um subconjunto do primeiro são um e o que isso significa é que queremos retornar. Verdadeiro. Se cada item no segundo array também é encontrado no 1º 3, temos algumas dicas aqui. Como de costume, Este problema tem algumas soluções diferentes com diferentes complexidades de tempo, e vamos em frente e cobrir todos eles. E uma das chaves para este problema é como lidar com as repetições quando um item está presente duas ou três vezes. Aqui estão alguns exemplos para este 1º 1 Os mesmos itens estão presentes em ambos um raise, os mesmos itens exatos apenas em uma ordem diferente. Então sabemos que o segundo é um subconjunto do primeiro na próxima Tese e Array tem 12 e três, e o primeiro Array tem um extra, então ele ainda satisfaz nossas condições no próximo. A segunda matriz tem um três que a primeira matriz não tem. Então, queremos isto. Queremos que nossa função retorne False. Para este caso e para o próximo, temos dois extras. Então novamente falso e, em seguida, o terceiro 1 Embora os itens, o número de itens é o mesmo, thes três itens não aparecem na primeira taxa. Só um dos que o faz. Então, de novo, queremos um falso retorno. Tente o problema e vá em frente e pressione play quando pelo menos tentar. Vamos começar. Então, como de costume, vamos precisar de um loop. Mas para que lado queremos? Um loop sobre. Bem, queremos ter certeza de que cada item na segunda matriz está presente no primeiro. Então, tudo o que nos importa é cada item no secundário. O 1º 1 pode ter alguns extras que não nos importam. Por exemplo, este aqui. Então, parece que seria uma ideia melhor percorrer a 2ª 1 E o que queremos fazer aqui? Bem, seja qual for o item que estamos atualmente, queremos procurá-lo na primeira matriz do super set. Então, aqui estamos apenas usando o índice de método para encontrar onde no super conjunto este item existe. Se existir doente. Se isso não acontecer, então Super Index será igual a um negativo e nós podemos imediatamente retornar false. O que isso significa é que há um item no segundo array, não no 1º 1, então sabemos que ele não pode. O 2º 1 não pode ser um subconjunto, então podemos retornar imediatamente false e no final da função. E se tudo correr bem, queremos voltar a ser verdade. Vamos em frente e testar esta função fora e nós não obtemos exatamente o que esperamos que estes funcionem. Este funciona. Chegamos a trégua de falso e depois duas verdades. Então essas duas condições estão falhando. Vamos dar uma olhada neste. Bem, uma condição fácil que podemos descobrir imediatamente é que um subconjunto tem que ser menor ou igual ao tamanho do seu super conjunto. Então, se os subsídios forem cada vez maiores, então sabemos que não pode ser um verdadeiro subconjunto. Então vamos em frente e sobre isso. Está a correr outra vez e isto estava a passar. Teremos uma falsa aqui, mas ainda precisamos fazer essa peça passar aqui, e não há maneira fácil de contornar isso. Então nossa função aqui está quase completa. Mas há uma coisa importante que precisamos fazer, que é. Acompanhe o número de cada item que aparece, e faremos isso na próxima lição. 3. Algoritmos de dupla matriz - Mergulho profundo: Bem-vindo de volta ao subconjunto da matriz. Estamos quase terminando nossa função. Tudo o que precisamos fazer é fazer com que este caso falhe no momento. Ele passa no teste e ficamos verdadeiros voltando de nossa função. O que precisamos é falso voltando porque esta matriz não é um subconjunto desta matriz. Como podemos fazer isso? Bem, no momento, o que estão fazendo é que ele está passando por este segundo array e seu processamento cada item na primeira vez que ele vê este. Ele procura por ele nesta matriz e diz que está lá. Ele acha ótimo. Ele continua no loop e chega ao próximo novamente. Ele olha para a frente no primeiro Array e ele encontra e encontra exatamente o mesmo. E ele diz, OK, estamos prontos para ir e ele faz isso mais uma vez. Precisamos dizer a ele que ele não pode olhar para este item duas vezes e não pode olhar para o mesmo item várias vezes. Se um item aparecer mais de uma vez no subconjunto, ele tem que aparecer pelo menos esse número de vezes no super set Bem, uma coisa que podemos digerir, é simplesmente excluir os itens que encontramos no super set que resolveriam o problema. Por exemplo, o que é a função procura por esta e a encontra aqui ao encontrá-la. Podemos apagá-lo da matriz. Da próxima vez que olhar dele, ele procura por aquele que ele não vai encontrá-lo lá e vai retornar falso. Então vamos em frente e código que em primeiro lugar nós não queremos modificar diretamente este array foram dadas, Então vamos fazer uma cópia dele. Desculpe, Super cópia. E com o operador de propagação, isso é tudo o que precisamos fazer para fazer uma cópia deste primeiro array. E vamos tentar executar isso novamente e todos os nossos testes passam neste trabalho funcional. Vamos em frente e olhar para as complexidades do tempo e do espaço. Então, por tempo, vamos chamar isso de M, e para este fim, nós realmente temos duas variáveis diferentes. Portanto, precisamos manter nossa complexidade de tempo em termos de ambas as variáveis. Aqui temos e todos eles. Ah, nós temos um não de processo em copiar uma matriz leva o que temos que fazer é ter toe loop através da matriz e copiar cada item individual. Então esta é uma operação linear aqui neste loop, começamos com mais N para secundário e aqui estamos na verdade temos outro loop mencionado em um problema anterior. Índice de é um loop e nós estamos looping sobre super, que no nosso caso, é M Então nós não temos o de m aqui porque eles estão em um loop. Nós os multiplicamos juntos e obtemos todos em vezes n e porque O de m vezes n é um fator maior do que este que podemos depois. Vá em frente e ignore isso porque é inconsequente para a complexidade do espaço. Criamos uma nova matriz copiando o original. Então vai ser o de M. Há uma maneira diferente de resolver isso, e na verdade vai melhorar nossa complexidade de tempo um pouco. Vamos trabalhar nisso. Então, em vez de operar assim, onde nós estamos looping através do subconjunto e, em seguida, tentando encontrá-lo do que o super conjunto estavam indo toe loop através de cada um separadamente e manter a contagem para que possamos manter este top, nós não vamos precisar de qualquer um dos isso mais e manterá o retorno verdadeiro na parte inferior. Então nós empregamos essa estratégia anteriormente, mas o que nós vamos fazer é criar um objeto para manter o controle desses números. Vou rotular este gado. Então o que estamos fazendo é primeiro percorrer o super set e construindo esse objeto no momento em que terminamos, o que queremos que esse objeto tenha é uma representação de cada item que está aqui, significando contagens corretas. - Então este é o caso. A declaração CIF é o caso em que estavam se deparando com uma string ou número pela primeira vez. Então, se é a primeira vez, queremos dar-lhe um valor de um. Se já vimos antes, só queremos incrementá-lo, está bem? E isso é tudo o que queremos para lidar com este ciclo. Este loop conterá uma contagem correta de todos os itens aqui. E vamos apenas bloquear isso para ter certeza, e vamos tentar com apenas dois. Este último item aqui. Então estamos executando este exemplo aqui, e estamos fazendo loop através desta matriz e isso parece correto. Vemos um aparecendo para aparecer uma vez e três aparecendo uma vez e apenas para ter certeza absoluta. Vamos adicionar mais três. Em seguida, rode novamente e vemos três duas vezes. Então parece que está funcionando. Tudo bem. Vamos em frente e percorrer a segunda matriz. - Então aqui estamos processando um item em nosso subconjunto, e estamos tentando garantir que ele seja encontrado em nosso objeto de conta. Se não o vimos antes, significa que isto é indefinido. Sabemos que temos algo presidente, o subconjunto que não temos no super set. Porque se o fizéssemos, ele teria sido armazenado neste objeto por este loop. Então, se este for o caso aqui, podemos ir em frente e retornar falso. No entanto, se não for indefinido, só queremos diminuir seu valor em um. Então isso diminuirá nossa conta. O que acontece? Um. O número chega a zero. O que estamos fazendo aqui é se o Conde chegar a zero, estamos excluindo o item totalmente do nosso objeto da contagem. Dessa forma, se processarmos esse item novamente, passaremos por esse loop e entraremos nesse caso. O que isso significa é que encontramos este item mais vezes no subconjunto do que no super set,o super set, que significa que não é uma trégua chateada, e podemos retornar falso. Tente enrolar sua cabeça em torno disso. Vamos em frente e contagem de registros novamente apenas para ter certeza de que ele está funcionando bem no final do segundo loop. Então nós esperamos ver, vamos ver, uh, uh, nós vemos falso porque ele está retornando falso. Ok, vamos mudar isso um pouco e torná-lo 123 Então o que devemos ver é um objeto vazio. E é exatamente o que fazemos. Veja, porque esse loop processou desordem e esse loop processou desordem, eles essencialmente cancelaram um ao outro. Itens foram adicionados e conta e, em seguida, removidos por este loop aqui. Então não devemos ver nada saindo, e parece que está funcionando da maneira que esperamos. Vamos seguir em frente e executar estes e ver se nossa função está funcionando corretamente e ainda temos um verdadeiro aqui. Por que é isso? Não mudei isso de volta e está funcionando exatamente como esperamos. Vejamos a complexidade do tempo para este. Então nós temos um O de neste caso nós vamos para os super sets, todos eles. E nada aqui é um loop. E aqui temos um O de N. Então nada aqui é um loop. Então, desta vez, porque esses loops estão atrás um do outro e nós não temos um dentro de outro em vez de multiplicar. O que vamos fazer é adicionar estes dois juntos, para obtermos O de M mais n para a complexidade do espaço. Estamos armazenando cada item no super conjunto neste objeto de contagem. Então isso vai ficar longe de M. Então esta solução funciona perfeitamente bem. E o próximo vídeo vamos em frente e descobrir como resolver este problema se não nos é dado apenas cordas e números em nossas matrizes aqui. Mas vamos fazer isso funcionar para cada tipo de entrada vendo a próxima lição. 4. Array: a solução ideal: bem-vindo de volta no último vídeo, conseguimos resolver o problema do subconjunto da matriz. nossa solução está aqui em baixo e não funciona para todos os exemplos aqui. E funcionará para cada exemplo em que usamos números. Este é um tipo de Peço desculpas, devo dizer, ou funcionará para qualquer entrada em que lhe damos números ou strings. Neste caso, são todos números aqui em baixo. Mas funcionaria se os substituíssemos por cordas iguais. E esta é a chave. Nossa solução só funcionará para números e cordas. Se tentarmos usar objetos, um raise ou funções são a nossa função aqui vai quebrar e vamos passar por cima. Por que notar que armazenamos todas as nossas informações em um objeto aqui? Os objetos são ótimos, mas eles têm uma pequena deficiência. E vamos falar sobre o que é isso. - Então tudo o que eu fiz aqui foi criar um objeto e depois tentar criar 33 pares de valor chave, um com um objeto, um com uma string e um com um número. E quando nos contestamos, isto é o que temos aqui. Isso não é o mais útil Então vamos realmente registrar cada item individualmente e vemos estes aqui, então isso está funcionando corretamente. Vamos também registrar em vez do vale aqui. Vamos em frente e registrar o tipo de chave e notei que cada vez que temos corda , esta é a mosca estava falando. Sempre que usamos colchetes com um objeto para qualquer conjunto de variável ou acessar algo, o que acontece internamente é que este item, seja qual for o primeiro, convertido em uma string. Então este objeto aqui é convertido no objeto objeto string. E acontece que é assim que esta plataforma de ondulação decide usá-la. Outros poderiam simplesmente chamá-lo de uma string com a palavra objeto nele. Ou pode ser outra coisa. Poderia ser mesmo este colchete de cadeia, mas aqui é objeto objeto, e é de fato uma string 25 também é convertido em uma string. Então, ao invés de realmente ser o número 25, o que entra aqui é a corda 25. Agora, se tivermos vários objetos e tentarmos usar os dois, vamos ver o que acontece. O problema é que estes dois, embora seus objetos distintos. Como podemos ver aqui, claramente fizemos dois objetos separados. Ambos são coagidos no mesmo objeto de string aqui. E isso significa que um deles simplesmente não é inserido. Em vez disso, inserimos isso e, em seguida, isso o substitui completamente. Só para mostrar que isso está acontecendo, nós também temos um objeto. Então isso foi essencialmente removido do nosso objeto. Certo, acabamos com isso. Vamos em frente e discutir como realmente corrigir isso. Então, em vez de um objeto aqui, vamos usar algo diferente. Vamos usar uma construção E S 2015 chamada mapa. Agora, um mapa é basicamente a mesma coisa que um objeto, exceto ele. Em vez de cordas desafiando suas chaves, ele irá mantê-las como estão. Então, é um objeto que contém pares de valor de chave, e qualquer valor pode ser usado como uma chave, não apenas para string o uso de apenas bastante simples. Você pode ir em frente e ler a documentação para aprender os métodos, mas este exemplo aqui lhe dará tudo o que você precisa saber sobre ele. E à medida que usamos os métodos estarão falando sobre eles de qualquer maneira. Então vamos em frente e mergulhar na direita. Então, em vez de um objeto para criar um mapa, usamos nova matemática para procurar um item em vez de verificar. Se for indefinido, usamos um método chamado tem e não precisamos disso. Se o item estiver presente em nosso mapa, isso retornará verdadeiro. Se não , será falso. Em vez de definir em vez de definir um par de valores-chave dessa maneira, fazemos isso de forma diferente. Usamos conjunto, e o primeiro item que damos será o que queremos definir, que será. Desculpe, vai ser a chave que gostaríamos de definir. Então esse vai ser o item atual. E, em seguida, o número de nós queremos dar-lhe neste caso um. Teríamos que mudar isso também. E o que colocamos um segundo valor? Bem, nós queremos definir. Queremos configurá-lo para qualquer que seja o valor atual mais um. Acabei de perceber que isto tem de ter um ponto de exclamação porque o que estamos a tentar fazer aqui é verificar e ver. Estamos tentando garantir que o nosso mapa ainda não tenha este item. Se ele não tiver o item, queremos definir seu valor como um. E se ele tem o item, queremos aumentá-lo em um. Então, isso está correto. Passando para o nosso segundo ciclo para isso, podemos realmente substituí-lo com isso exatamente como ele é porque estamos tentando verificar exatamente a mesma coisa. Isto aqui pode ser substituído por isto com uma pequena mudança. Então, em vez de adicionar um, como estamos fazendo aqui, queremos subtrair um. Então, para diminuir essa contagem de itens, estamos recebendo seu valor atual subtraindo um e definindo seu novo valor para esse número aqui, aqui, Em vez de acessar isso como faríamos com um objeto, vamos apenas usar o método adequado de montanha. E aqui estamos usando o mapa de método, Doc excluir e nós simplesmente queremos passar, oops, item atual e isso deve funcionar. Obtemos exatamente os mesmos valores que esperamos, então parece que está funcionando. Eu encorajo você a alterá-los e experimentá-los com objetos, matrizes, funções, strings e números todos no mesmo exemplo. Esta nova função que temos aqui deve funcionar para qualquer coisa que você der. As complexidades do tempo e do espaço permanecem as mesmas. Um mapa é basicamente equivalente a um objeto, apenas com este novo recurso adicionado onde as teclas não precisam ser strings. É isso. Vejo você no próximo vídeo. 5. Máximo lucros através de Brute Force: Bem-vindos ao próximo problema. Lucros máximos para este problema. Vamos receber uma série de números que representa os preços de uma ação desde o início do dia até o fim do dia. Por exemplo, dado este array aqui, o estoque começou a um preço de 10 e terminou em um dia a um preço de nove. E passou por estes em ordem durante aquele dia e passou por estes preços. Nosso objetivo é encontrar o máximo de lucro possível comprando uma vez e vendendo uma vez em um único dia. Então, a partir desta matriz, queremos encontrar o lucro máximo que podemos fazer. Não há curto-circuito, que significa que você deve comprar antes de vender e se nenhum lucro pode ser feito. Por exemplo, se o preço das ações caiu o dia todo e isso parecia 10 98765 Então, em vez de retornar um número negativo, nós só queremos retornar zero para indicar que nenhum lucro pode ser feito. Vamos em frente e começar como de costume. Vamos precisar do nosso ciclo de quatro e do que queremos fazer. Começaremos com a estratégia de força bruta, o que significa calcular todos os lucros possíveis que conseguirmos e devolver o maior que encontrarmos. E vamos pensar em como fazer isso. Então, se nós compramos 10 e vendemos a sete, nós somos lucro será negativo três. E queremos guardar isso em algum lugar. Se víssemos se comprássemos 10 e vendíamos a 5, nosso lucro seria negativo. Cinco compraram 10 e venderam oito. E sobre e sobre e sobre. Não ganharíamos muito dinheiro comprando aos 10. Destruir sete. Então, por sete, vender às cinco. Nosso profeta é negativo para comprar às sete. Célula às oito. Lucros um por sete Vender 11 lucros para começar a parecer bom. Vamos passar por isso de vez em quando até conseguirmos todos os lucros possíveis e então devolveremos o mais alto. Então, para fazer isso notou que quando começamos aos 10 nós, então, tivemos que processar cada um desses. Quando começamos às sete, tivemos que lucrar cada um desses. Então vamos precisar de um loop dentro deste loop. Eu estou esquecendo o que este loop vai ter aqui eu acho a mesma coisa. Preços comprimento inicial para cima. Vejo que isso tem que ser igual a um I mais um porque queremos começar após a posição de e armazenar cada um dos possíveis lucros. Queremos criar uma matriz. E aqui, tudo o que precisamos fazer é calcular o lucro e colocá-lo na matriz no final, queremos retornar o máximo. Então o que podemos fazer é usar a função matemática dot max e matemática. Não Max leva em vários números, como muitos como você quer dar-lhe, e ele vai apenas retornar o número máximo. Então aqui podemos espalhar nossa matriz de lucros. Esqueci de uma coisa aqui que queremos começar com zero. Então, se novamente, se os preços do ar apenas caindo, indo de , digamos, 928642 homens, não importa onde compramos o não importa onde vendemos nosso lucro vai ser negativo. Tendo isto aqui, as seguradoras que Math Dot Max vão, pelo menos, obter zero a cada vez. Então isso resolve a condição que mencionamos anteriormente. Onde, se nenhum lucro pode ser feito, queremos voltar. Zero. Vamos em frente e testar isso. Vamos usar o Serie aqui mesmo e esperamos ver seis parecendo bem. Ok, vamos falar sobre a complexidade do tempo na complexidade do espaço deste problema. Então temos um loop que passa pela nossa direita e temos outro loop que passa não pelo todo já, mas parte da teoria. Isso definitivamente vai ser Oh, of End. E este também vai ser oh, de n mesmo que ele não está passando por toda a matriz. Em média, esse loop está passando pela metade da teoria. Por exemplo, começando em 10 J vai passar por cinco números começando em sete. Vai passar por quatro, começando às cinco. Vai para lá três e depois dois e depois um. A média desses números é metade do comprimento deste array, então isso é tecnicamente e mais de dois. Mas deixamos cair constantes para que ambos 1/2 final se torne, oh, evento. E porque esses loops estão dentro um do outro, nós nos multiplicamos. Então obtemos O de n ao quadrado para a complexidade do espaço. Na verdade, estamos empurrando esse número de preços para nossa matriz de lucros. Então isso tem que armazenar cada coisa que este Lou produz. Então, isso é realmente também vai ser o de M ao quadrado. Eles vão ser os mesmos. Nós não conversamos sobre este. E isso é realmente também vai ser, oh de e quadrado porque matemática em Max como um loop em si mesmo, ele tem que procurar através de todo o array e nos dar o maior número em achados. E o tamanho da matriz como mencionado, é longo e quadrado. Ou é proporcional thio do fim ao quadrado. Então isso em si vai ser o n ao quadrado. E nós adicionaríamos isso ao valor que obtivemos do loop e isso nos leva oh, de dois e ao quadrado. E sempre deixamos Constance. Então isso poderia simplesmente ir embora, deixando-nos com O de n ao quadrado, que era o que tínhamos inicialmente. De qualquer forma, começamos com mais e quadrado e acabamos lá, então isso essencialmente não muda nada para nós. Essa foi a solução da força bruta. E no próximo vídeo, vamos passar por um muito mais rápido 6. Máximo lucros: processamento inteligente: no último vídeo, resolvemos esse problema usando uma solução de força bruta. Estamos calculando cada lucro possível que pode ser feito e apenas devolvendo o máximo . Vamos tentar de uma maneira diferente. Então vamos pensar sobre o que poderíamos fazer para fazer isso em uma única passagem. Vamos tentar tirar isso para O, e atualmente é e ao quadrado, e nós conseguimos levá-la para cima e algumas vezes antes. Vamos ver se podemos fazer isso desta vez. Bem, como você calcula um lucro? Você pega um número e desculpe, você pega um número e subtrai um número antes dele. Como você fica assim usando oito. Como podemos obter o máximo de lucro possível de vender em oito? Bem, olhamos para os da esquerda, e encontraríamos o número mais baixo que pudermos. Não são 10. Não são sete. É cinco. Então, o lucro máximo que podemos fazer aqui é três. Olhando para 11. Como descobrimos o melhor lucro possível que podemos obter com a venda a 11? Bem, isso seria encontrar o grande número aqui. Desculpe. O menor número aqui e vendendo. Vendendo às cinco, podemos transformar isso em código se mantivermos o menor número que vimos até agora, podemos. Então, à medida que avançamos, subtraia o número que encontrarmos desse número. Deixa-me mostrar-te o que quero dizer. Então estamos usando apenas duas variáveis aqui para manter o controle desses dois valores ao longo de nossos homens de loop. O preço que vamos assumir é infinito e vamos atualizá-lo assim que começamos. Loop e Max Lucro assumirão zero e atualizaremos sempre que for preciso. - nos certificamos Só nos certificamosde que isso funciona. Ele faz. Esta é, na verdade, toda a nossa solução. Vamos ver o que estamos fazendo de novo. Presumimos que o preço mínimo começa no infinito. Então estamos dizendo apenas basicamente, insira um infinito aqui neste loop. Vamos atualizar isso sempre que precisarmos do Teoh. Então, enquanto estamos passando por isso, vamos atualizá-lo. Infinity não está aqui, então vamos começar às 10. E estamos dizendo que o preço mínimo que encontramos até agora é o menor preço dos homens ou o preço atual. Então, a parte inferior do infinito ou 10 será obviamente 10. Então os preços dos homens agora igualaram. Tentativa Max, o lucro será o número atual que estamos processando menos o preço mínimo que vimos até agora. Isso é o que segue a nossa regra. Nós apenas manter o controle desses dois em todo o nosso ciclo e nós atualizá-los sempre que precisamos . No final, temos lucro Max já armazenado em nossa variável e enfraquecer. Basta retornar que é realmente o tempo e o espaço simples. Transformamos um loop duplo em um único loop. E nenhuma dessas operações ocupa uma quantidade significativa de tempo. Eles não são lineares ou nada mais alto lá, apenas operações de tempo constante. Então eles não vão mudar isso. E nós vamos CEO de um O de N complexidade do tempo Primeiro espaço. Vamos ver o que estamos guardando. Estamos armazenando duas variáveis aqui. E não importa o quão grande isso seja, não precisamos armazenar mais dados do que essas duas variáveis. Então isso é depois de cair de N ao quadrado para um. Esta é a solução que conquistaria o entrevistador. É difícil e mostra a capacidade de lidar logicamente com números e tempo. É elegante, curto e doce, e tem as melhores complexidades de tempo e espaço imagináveis para um problema como este novamente, Apenas mantendo o controle de alguns números através de sua função e um pouco de inteligência, podemos trazer para baixo tanto o nosso espaço e tempo complexidades consideravelmente eu vou ver no próximo vídeo. 7. Mutação única: O problema vai ser uma única mutação. Vamos escrever uma função que levará em duas cordas, e precisamos determinar se as duas cordas são idênticas, exceto por possivelmente uma mutação. Existem três tipos de mutações, e esses são inserções de relações e entradas de substituição. Uma exclusão é apenas a dilatação de um único caractere e inserções. A inserção de um único caractere e uma substituição é uma mudança de caractere, com as strings sendo o mesmo comprimento. No final, vá em frente e experimente sozinho e volte quando estiver pronto. Vamos em frente e começar esse problema, então queremos começar escrevendo loop. Mas o que isso parece bom? Parece? Bem, a cada passo, basicamente queremos comparar exatamente o mesmo item e ambas as cordas. Então, à medida que passamos por esta string, queremos comparar o primeiro caractere aqui com o primeiro caractere aqui, o segundo caractere aqui para o segundo caractere aqui e assim por diante. Vamos ver como faríamos isso. A chave está usando um tipo diferente de loop do que vimos até agora. Bem, ainda é um loop for, mas vai ser estruturado um pouco diferente. Vamos em frente e anote as condições. Coma. Isso pode parecer um loop estranho, mas é perfeitamente legal. Vamos ver o que está acontecendo aqui. Estamos declarando duas variáveis, e nossa condição é que é praticamente uma condição padrão. Acabamos de colocar o seu depoimento lá dentro. Então, se qualquer uma dessas verdadeiras, se qualquer uma delas for verdadeira, nosso loop continuará e no final foram implementando duas variáveis diferentes. Os dois que declaramos no início. Mas vamos discutir por que estamos fazendo isso enquanto passamos por isso. Portanto, queremos também criar uma variável para acompanhar o número de mutações que temos até agora . E vamos começar zero e aqui, basicamente, basicamente, quando queremos passar com cordas um por 11 caracteres de cada vez e olhar para o número de mutações. Então, como sabemos se há uma mutação? Bem, vamos verificar se os caracteres são iguais. Se os caracteres são exatamente os mesmos, queremos fazer nada e queremos com o loop continuar. Mas se forem diferentes, queremos fazer alguma coisa. Então, se eles não são iguais, sabemos que temos uma mutação para que possamos estudar e incrementar isso. E agora precisamos determinar que tipo de mutação é. É uma exclusão e inserção, ou é uma substituição? Então nós aumentamos as mutações e há outra verificação que realmente queremos dilatar. Então nós implementamos mutações, e se nós já sabemos, nós temos que, nós podemos imediatamente retornar falso se não em si mesmo. É a primeira mutação. Então aqui está o que queremos fazer. Então aqui estamos dizendo que o comprimento do primeiro item é maior que o comprimento do segundo item. Então este pode ser um exemplo para este ou este. Então, se eles são iguais, nós realmente queremos encaixar Ament a segunda variável. E vamos explicar por que a IHS toma isso como um exemplo. Então estamos comparando A e A em nosso loop e eles são idênticos. Estamos comparando B e C, e estes são personagens diferentes. Então nós vamos entrar neste loop mutações vai se tornar um. Vamos pular isso porque a mutação é igual a um, e vamos entrar aqui. Então vamos diminuir o J. E esse é o índice aqui. Então estamos no próximo em ambos, e vamos diminuir o índice para a segunda string e trazê-lo de volta para aqui . Então, novamente, para a primeira corda, onde em B para a segunda corda, onde em um Vamos para o próximo para a próxima iteração do loop e este sonho nós seguimos em frente para ver. E nesta string, nós também queremos ver Então essencialmente, nós temos a segunda cadeia de volta no caminho certo realizando esta operação aqui nós comparamos C dois c mesmo que eles estão em índices diferentes e então nós continuamos indo. Como eles são idênticos, então nós incrementamos ambos os índices novamente. E o mesmo é profundo. Então, estamos prontos para ir. Sabemos que só tivemos uma única mutação e agora podemos retornar a verdade e estamos quase terminando aqui. Mas o que queremos fazer se houver uma inserção em vez disso? Bem, nesse caso, então a corda um vai ser mais curta do que uma corda para, e estamos fazendo neste caso, por exemplo, para este, nós realmente queremos um deck Ament, a outra variável, e isso nos colocará novamente no caminho certo. Você pode ir em frente e passar por isso sozinho e descobrir essa lógica. Mas funciona. Esta é a função inteira. Vamos em frente e testá-lo. Vamos em frente e usar isso. Então aqui esperamos ver a verdade. Bem, isso é tentar um de cada um desses correndo novamente. Verdadeiro. E vamos tentar isso, uh, cometeu um erro lá, e é verdade. E para ter certeza que está funcionando, vamos também tentar algo que não funciona. Não devia funcionar. Então aqui temos duas adições, então isso deve ser falso, e vemos que é falso. Vamos tentar. Substituição é, em vez disso, para que um BCD se torne um x x d. E novamente obtemos falso. E vamos tentar excluir falsas novamente. Então isso funciona. Vamos seguir em frente e passar pelas complexidades de tempo e espaço para esta função. Então, no para o estavam indo de I é igual a zero para o comprimento da corda. As cordas I e J, estamos usando apenas um loop aqui e neste loop, nenhuma dessas operações são lineares thes air, todas as operações de tempo constante, então eles não vão mudar o tempo de complexidade do nosso loop. Nós só temos que descobrir qual é a complexidade do tempo deste único loop, e ele vai ser linear. Então, geralmente as cordas. Vamos ter um comprimento semelhante, bastante semelhante. E assim podemos dizer N é apenas o comprimento de qualquer corda. Nesse caso aqui, a complexidade do tempo vai ser apenas, oh de N. Você pode argumentar que nós passamos por duas vezes mais porque nós estamos lidando com ambas as variáveis, eu e J. a complexidade do tempo vai ser apenas, oh de N. Você pode argumentar que nós passamos por duas vezes mais porque nós estamos lidando com ambas as variáveis, eu e J. multiplicar isso por dois, e nós nos livramos da constante de qualquer maneira, Então isso nos deixaria com uma complexidade de tempo de o de n e qual é a complexidade do espaço? Bem, não importa quanto tempo essas cordas sejam, nós só armazenamos três variáveis I J e Mutações. Então isso realmente vai ser uma esperança que ajudou. E eu espero que isso faça sentido e eu vou ver no próximo vídeo 8. Detectando anagramas: Todos vocês anagramas. As instruções aqui são para tomar em uma matriz de cordas e retornar. Verdadeiro se todas essas cordas são anagramas um do outro, anagramas significa que eles têm os mesmos caracteres na string, mas eles podem estar em uma ordem diferente. Aqui estão alguns exemplos estes três são todos anagramas um do outro. Todos eles contêm a, B, C e D, e eles estão em uma ordem diferente. No próximo exemplo, temos um X aqui, que significa que eles não são todos anagramas, então queremos que a função retorne False e os próximos dois são bastante semelhantes a esses. Vá em frente e experimente você mesmo e vamos começar com a solução aqui. Então, como mencionado um anagrama ou melhor, anagramas, nossas cordas que têm os mesmos caracteres, mas talvez em uma ordem diferente. Então, qual é uma maneira de descobrir se duas cordas são anagramas? Nós poderíamos manter a conta de cada personagem, e nós poderíamos verificar essas contagens no final uma vez que nós processamos as cordas. Mas há uma maneira que é um pouco mais simples, e vamos continuar assim. Primeiro, podemos realmente classificar esses caracteres. Então, por exemplo, se nós classificar um B c D, ele vai ficar exatamente do jeito que está. Se dividirmos o próximo anel, ele se transformará em um B C D e fará a mesma coisa para este, e também se tornará um BCD. As cordas, depois de classificar todas, tornam-se exatamente a mesma corda. Então, se classificar anagramas um do outro, todos eles devem se tornar exatamente a mesma corda, e podemos usar isso a nosso favor. Vamos em frente e começar. Então, onde vai classificar cada corda em nosso raio usando a função de mapa? Então nós temos uma string e queremos primeiro dividi-la em uma matriz. Então agora temos uma matriz de caracteres. Em seguida, usamos a função de classificação, e então juntamos esses caracteres de volta em uma matriz, e isso irá conter as cordas, todos os tipos de juntos. Vamos nos certificar de que acertamos, e isso é testado com este. Oops, isso parece certo. Então, não, temos que fazer. Vamos passar por essas cordas e um loop, e precisamos ter certeza de que eles são todos iguais, como dissemos antes, e nós temos que querer começar isso em zero. Lamentamos um. Esta é toda a nossa solução. E para ter certeza que ainda funciona, nós nos tornamos realidade. Vamos tentar todos estes. Então, fazendo-os um de cada vez aqui, esperamos falso aqui, esperamos verdadeiro. E aqui esperamos falso novamente e isso funciona. E quanto às complexidades do tempo e do espaço? Por tempo vamos ter que considerar isso em termos de duas variáveis diferentes. Normalmente, usamos n e dizemos mais e ou no quadrado ou o que seja. Mas aqui, vamos dizer s é o comprimento das cordas e A vai ser o número de cordas na corrida ou apenas o comprimento da matriz. Isso ocorre porque as complexidades de tempo e espaço são extremamente dependentes de ambas as variáveis. Faz sentido usar os dois. Quando estamos falando sobre essas complexidades temporais, as complexidades tempo e do espaço. Então, a complexidade do tempo. Vamos passar por este aqui. Temos cordas, não divididas. Então, novamente, um mapa é um loop. Então isso já vai ser oh de um, já que estamos nos movendo sobre a matriz e, em seguida, o que fizermos aqui vai ser multiplicado por isso porque está dentro do loop. Então, classificar uma única string vai ser s vezes Log of s uma espécie Operação é geralmente tomado para ser n vezes longo de fim e aqui vai ser o comprimento de nossa string. Juntando-se a eles novamente vai ser Vai ser Oh, de S que é o comprimento da corda novamente Então nós podemos realmente adicionar estes juntos. Então dividir eu acho que esqueci completamente a parte dividida Isso também vai ser apenas s assim s para dividir s vezes Log de s para ordenar e s novamente para juntar como mais s mais longo mais s E podemos realmente simplificar isso e para um vezes para s mais termos Log de este e todo este termo pode realmente desaparecer porque s vezes log de s é maior ordem do que sim. Uma vez que estas duas são variáveis diferentes e nós, temos que mantê-las ambas. Isso produz um log vezes s vezes de s para o nosso tempo, complexidade. E quanto ao espaço? Bem, nós armazenamos toda uma série de itens e essa matriz vai ter o mesmo comprimento da nossa Valerie inicial. Então isso vai ser oh, de um comprimento da matriz. E cada uma dessas cordas é realmente vai ter o mesmo comprimento que as cordas originais. Então vai ser uma hora. É porque estamos armazenando as mesmas cordas numéricas, depois as cordas. Vamos ser a mesma ligação. Então esse é o nosso tempo em complexidades espaciais para a solução. No próximo vídeo, vamos rever outra solução e tentar melhorar ambos um pouco. Vejo você lá. 9. Processamento rápido de Anagrama: Bem-vindos de volta a todos os anagramas. No último vídeo, escrevemos uma solução que em uma espécie, cada uma das cordas e, em seguida, determinar se as cordas eram todas iguais entre si. Aqui, vamos trabalhar em nossa solução um pouco e derrubar as complexidades de tempo e espaço que pareciam um pouco difíceis no último vídeo. Então, em vez de classificar, vamos tentar outra estratégia, e essa estratégia vai estar contando as ocorrências de cada personagem individual. Então, por exemplo, tomando a Serie nós vamos querer criar um objeto que nos diga quantos de cada caractere estão nesta string. Nós vamos querer fazer a mesma coisa para a próxima string e ter certeza que esses dois objetos são os mesmos ou que eles parecem exatamente iguais e fazer a mesma coisa para esta terceira string e sobre e sobre e sobre. E nós só temos que ter certeza de que esses objetos mantendo o controle de nossos personagens olhar exatamente o mesmo para cada string na matriz foram dadas. Vamos em frente e começar. Então vamos precisar de um lupas de sempre. E o que queremos fazer aqui? Bem, queremos criar um objeto com as contagens de caracteres da string. E como fazemos isso? Bem, e nós já fizemos isso algumas vezes antes, quando precisamos de dio começar criando um objeto e então vamos agir. Você vai precisar de outro loop. Este loop vai ficar assim. - Tão simples. Já fizemos isso várias vezes até agora. Este é apenas um loop que vai preencher este objeto com as contagens de caracteres de qualquer string que passamos. Se é a primeira vez que estamos processando o personagem, então não vai estar em nosso objeto ainda. E quando a procurarmos, ficaremos indefinidos. Então queríamos definir seu valor como um. Se já tem um número que significa que já existe em nosso objeto. Só queremos aumentar esse número em um. Podemos limpar isso um pouco só para facilitar a leitura. E só para ter certeza que fizemos isso certo, vamos fazer o registro do Cônsul. Então, executá-lo com apenas estas três cordas e parece que está funcionando exatamente da maneira que queremos saber. Então temos esse objeto e o que queremos fazer com ele? Bem, queremos compará-lo com outro objeto para outra string. E como conseguiremos esse objeto? Bem, enfraquecer, apenas faça isso antes do loop quatro. Então, aqui em nosso loop, podemos realmente começar com o item um, o que significa que vamos começar com essa string. E antes de começarmos o loop, podemos ir em frente e criar o objeto para esta primeira string. Então, essencialmente, queremos criar um objeto para a primeira string. E isso na verdade vai seguir apenas toda essa lógica exceto em vez de então em vez da string isso vai ser strings é zero. Não, o que temos aqui é que temos essencialmente o mesmo código escrito duas vezes. Uma coisa boa a fazer seria extrair isso em outra função para que possamos ir em frente e fazer isso. Ele vai nos ajudar e limpá-lo para citar um pouco. - E isso deve funcionar para que possamos ir em frente e nos livrar deles e usar nossa nova função. Eu não consigo me livrar de tudo isso e função do usuário novamente. Não, estamos comparando. O objeto seria gerado aqui com o objeto gerado aparecer que vai ser para a primeira string. Precisamos ter certeza de que cada propriedade nesses objetos é equivalente. E nós realmente precisamos fazer isso com outro loop. - Quase lá. Agora, isto deve funcionar. Vamos em frente. E estamos nisso só para nos certificarmos de que saímos da verdade. Vamos tentar que este seja verdadeiro e falso. Parece que funciona. Então vimos que nossa função funciona para esses quatro. Mas deixe-me mostrar-lhe um exemplo em que nossa função realmente retorna o resultado errado. Então, se tivéssemos um joelho aqui e nós executá-lo, Eu preciso de um comentário estes fora. Esperamos quedas porque isso tem um extra e significando que estes três não são anagramas, mas nós voltamos verdadeiro. E isso porque o que estamos fazendo aqui é criar primeiro um objeto para o primeiro personagem. Conte a primeira corda que tivermos. Desculpe-me. Então esse objeto vai ficar assim. Tem um através e e cada um tem um. Isso é o que queremos agora aqui. Como você pode ver, estamos faltando o então nós temos o e na primeira corda, mas não na 2ª 2 cordas, e nós podemos ver que tudo aqui. Agora, o problema é que neste loop, tudo o que estamos fazendo é retornantes verificando os caracteres que vemos nesses dois objetos. Então nós estamos verificando para ver se um em pêlos igual dedo do pé um e é B é igual a um. C é igual a um, e D é igual a um. Não verificamos para ter certeza de que não há extras. Então isso realmente passa é checar um que não deveria. E há algumas coisas que podemos fazer para contornar isso. O que vamos fazer é provavelmente um dos mais fáceis e um dos menos tempo intensivo. Então vamos em frente e fazer isso. E o que queremos fazer é criar outro loop para percorrer a string. Desculpe. Vá através da matriz e apenas certifique-se de que todas as cordas têm o mesmo comprimento. Simples o suficiente, nós começamos em um e vamos para o fim e apenas certifique-se de todos os comprimentos artigo Então novamente , nós sabemos que isso para retornar falso, e nós obter falso de volta. Então consertamos nosso código. É isto. Esta é toda a nossa função. Vamos passar pelas complexidades do tempo e do espaço. Então, para o tempo começaria com o top ao vivo que temos aqui. Nós temos um monte de um Estamos looping através de toda a matriz e certificando-se de que as cordas são do mesmo comprimento. Então isso é apenas um loop através da matriz aqui em baixo. Vamos descobrir a complexidade do tempo. Esqueça a contagem de carros. Estamos passando por um loop e processando cada caractere da string. Então, haverá um loop padrão que leva um link que leva tempo proporcional ao comprimento da string. Então vai haver Oh, de s, de s, isso significa que esta coisa toda é Oh, de s, isso aqui vai ser sobre um desde que é um loop sobre toda a matriz e, em seguida, isso e aqui vai ser sobre s então isso se transforma em de um vezes s Este aqui também é de s Então é o de oito vezes dois s, mas a constante é descartada. Então, só temos um de S. E essa é a nossa última vez. Complexidade para o espaço. Não, importa o quão grande as cordas são A é tudo o que fazemos é criar apenas algumas variáveis que criamos. Criamos o primeiro conselho de carros. Isto é um objecto. Deixa-me livrar-me disto. É para eu não nos confundir. Então aqui eu Este loop inteiro vai apenas declarar um muito eu então podemos ignorar que este aqui vai ser Oh, de s porque nós temos um objeto preenchido com as contagens de caracteres de uma string e esse tamanho de objeto vai ser proporcional ao comprimento dessa string. Então vai haver um Nove S bem aqui. Podemos criar uma variável I, que tem sido significativa. E aqui nós criamos outra variável, Oh, da qual também vai ser sobre s. É um objeto que é proporcional em tamanho ao comprimento desta string. E nesse loop de quatro, não fazemos nada o comoespaço. Nós realmente não criar nenhum objeto aqui ou quaisquer variáveis em tudo. Então nós temos um não de s e outro o de s. E estes vão ser adicionados juntos porque isso permanece para o comprimento da função para o comprimento da função restante. E este objeto aqui é gerado quando iniciamos o loop e, em seguida, excluído uma vez que o loop termina. Então este loop Onley gera um dos objetos de cada vez, então no máximo ao mesmo tempo, estavam usando O de s mais s espaço, que nos dá para s, que simplifica até O de s. E essa é a final complexidade de espaço para esta função. Ver a próxima lição. 10. Rotação de uma matriz quadrada: problema. Girar, matriz, matriz e script Java podem ser representados como uma matriz de um raise. E aqui está um exemplo. Temos uma única matriz externa que é denotada por este colchete neste colchete aqui e aqui. Temos três matrizes, cada uma com três elementos neles, e isso constitui uma matriz de três por três. Nosso objetivo aqui é escrever uma função que levará essa entrada. Então a entrada vai ser esta matriz de matrizes e saídas de uma nova matriz. Então queremos que a função retorne uma matriz de um raise e que a nova matriz que é retornada deve ser a mesma que esta girada 90 graus. Isso deve funcionar para matrizes quadradas e retangulares. Então, basicamente, maior vê de quaisquer dimensões para o exemplo dado esta matriz como entrada e podemos ignorar esses índices de ar apenas para ver onde esses números estão localizados. Dada esta matriz como entrada com esta matriz de três matrizes, queremos que a nossa função produza esta matriz. Como você pode ver, tudo é apenas girado 90 graus no sentido horário. Um é movido para a direita, três vai para baixo, o nove vai para a esquerda e o sete sobe e tudo o resto se move com os quatro. Desculpe, os dois movimentos para a direita e para baixo os seis movimentos para baixo e para a esquerda e para cima e para cima. Então, essencialmente, precisamos girar esta matriz 90 graus no sentido horário. Vá em frente e experimente a salada por conta própria. É muito divertido, e não é muito difícil, mas volte quando estiver pronto. Quando você tentar o problema, vamos em frente e começar a resolvê-lo. Assim, o problema afirma que a Matrix original deve permanecer inalterada. E o que isso significa é que queremos criar uma nova matriz para retornar. Não queremos apenas mudar as coisas no original, mas queremos fazer uma nova. Então vamos criar isso. Então vamos começar com uma matriz e como preenchemos essa matriz? Bem, vamos começar com uma matriz quadrada por agora. Então vamos examinar este três por três que já temos. Então, se temos um três por três é entrada. Sabemos que nossas saídas também serão três por três. Se tivermos um quatro por quatro. São saídas vai ser um quatro por quatro. Então o número de um aumento aqui e nossa nova matriz será o mesmo que o número de um aumento na antiga Matrix. E podemos descobrir que usando a propriedade length, esta matriz externa tem um comprimento de três porque tem três itens dentro dela. Então podemos usar isso para criar o mesmo número de linhas para esta nova matriz. E essa é a nossa nova Matrix terá o número correto de uma corrida. E vamos nos certificar de que estamos fazendo isso direito enquanto avançamos e vamos dar um exemplo. Vá e roube isto. Ok, lá. Então temos uma série de três corridas como pretendido. Agora também sabemos que, no final, precisamos devolver isso para que possamos apenas escrever essa declaração. E agora, Agora, o que fazemos no meio? Só temos que preencher a Matrix com os números corretos, e vamos fazer isso fazendo um loop através da Matrix que foram dadas. Então nós estamos passando por aqui e nós realmente vamos ter que loop dentro de cada pressa interior . Então agora estamos fazendo loop através deste array externo e o papel atual onde on vai ser este? E então os loops vão passar para este. E neste, precisamos também olhar através de cada um desses para chegar a esses números individualmente. Aqui estamos usando o comprimento do ponto zero mate. Na verdade, isso só pode ser alterado para matemática que link. Isso é a mesma coisa, porque agora estamos focados em matrizes quadradas, e o número de itens aqui vai ser o mesmo que o número total de um aumento. Então isso vai funcionar para nós muito bem. E agora, para a parte difícil, temos que realmente descobrir como mover esses itens para o lugar correto. 11. Rotação de uma solução de matriz quadrada: Bem-vinda de volta. Vamos continuar trabalhando nesse problema. Até agora, nós temos a base definida, e agora nós só precisamos de um algoritmo para realmente mover essas peças para o local correto. E vamos em frente e trabalhar nisso e para exemplos. Por exemplo, vamos começar com uma simples matriz de dois por dois, então eu vou seguir em frente e usar um, também. Isso precisa de outro suporte e 34 e isso precisa se transformar em 31 quatro para, e isso é uma rotação de 90 graus. Então vamos em frente e mapear as mudanças reais de posição que acontecem. E o que quer dizer com isso? É assim que um aqui está na posição 00 É na linha no Índice zero nessa linha. Está na coluna zero, então podemos dizer 00 movimentos para ainda na subiu zero. Então isso permanece o mesmo, e é conhecido Coluna 1. Então isso vai passar para 01 E vamos fazer isso para os outros três também. Então pegamos um item em 01 se move para 11 e temos um item em 10 Movendo-se para onde está passando? Mova-se 200 e temos 11 indo para 10 e isso parece certo. Então, a partir daqui, podemos realmente ir em frente e criar um algoritmo. Se fizermos isso para três por três ou quatro por quatro, ou qualquer matriz quadrada, teremos os mesmos resultados. E esses resultados serão regidos por uma regra matemática simples, que será esta. Perdoe-me pelo tipo de vida e só para ter certeza de que estamos fazendo isso direito, vou prolongar isso. Então 741 852 963 Isso é exatamente o que queremos. E vamos mostrar-vos como isto está realmente a funcionar. Vamos ligar alguns números. Então, ligando 00 aqui para o lado direito, temos New Matrix, então Jay está posicionado. Zero. Então, são dias. Adicione zero. Então, isso está correto. O primeiro item vai ser zero, e o segundo item vai ser o comprimento do ponto mate. Então o comprimento desta matriz é, uh, comprimento dois. Há três itens, mas seu comprimento para dois menos um é um menos I, que é zero desde que estamos começando em 00 Então 00 conectado aqui leva 20 vírgula um no lado esquerdo. Então nós realmente virou 00 e 201 Nós mudamos o item de 00 para 01 Nós podemos fazer isso para o resto deles. Podemos ligar 11 aqui, e o que temos é um na posição da mão esquerda e Matt no comprimento para menos um menos um . Nós temos zero aqui, então nós fizemos 11 em 210 Vá em frente e conecte esses dois. Ou tente o que quiser. Vai funcionar toda vez que resolvemos este problema para matrizes quadradas e na próxima lição irá em frente e tentar aplicar isso a todos os maitresse. Facilidade. Veja lá. 12. Rotação de matriz: dois problemas bônus: Bem-vindos de volta na última lição. Nós realmente terminamos este problema. Mas eu quero ir em frente e dar a vocês um pequeno bônus. Então o primeiro problema de bônus vai ser certo. Uma função que todos rotador matriz 180 graus. E o próximo estará certo. Um que gira 270 graus. Você também pode pensar neste como 90 negativos. Já temos este. Eu só desmoronei. Teoh, abre espaço para os outros. Esta é exatamente a mesma função que tínhamos antes e nada é diferente. Só estou desmoronando. E estes são os resultados esperados para esta matriz. Então rodou 90. Queremos este 1880. Quer aqueles 270? Queremos isto. Tudo o que temos que fazer é escrever duas funções. Existem algumas maneiras diferentes de fazê-las. Vá em frente e tente se quiser. Se você quiser ir em frente e apenas assistir o vídeo, você pode fazer isso também. Já que isso é só um bônus, vou deixar passar. Então é assim que vou resolver este problema. E isso é um feito. E isso também é feito e está certificando-se que estes alinham-se durante 14 para 4321 2413 E estamos bem. Acha que isso é trapaça? Eu meio que sei, também. Mas a questão é, isso realmente não importa. Essas funções funcionam e funcionam perfeitamente bem. E há realmente razões para você preferir estes em vez de outra grande função como esta. Seu recurso mais valioso como desenvolvedor é seu próprio tempo. Não é o tempo que a máquina leva para executar seu código. Estes resultados são muito rápidos. Eu tinha fugido e antes eu posso pensar que os resultados estão lá, e isso vai acontecer em quase todas as funções que você escrever em toda a sua carreira. Computadores ar rápido As pessoas são lentas, então você quer gastar seu tempo escrevendo o menor código possível. Escrevemos uma função que funciona perfeitamente, e sabemos que funciona. Nós testamos um pouco. Por que não reutilizá-lo? Se pudermos, reutilizamo-lo. Chamamos duas vezes, e ele gira nossa função 180 graus. Nós chamamos isso mais uma vez, e ele vai fazê-lo 270 graus em vez de escrever o mesmo essencialmente o mesmo código com algumas diferenças novamente e potencialmente introduzir bugs. Quando tentamos fazer isso, podemos usar a única função que conhecemos, funciona e economizar uma tonelada de tempo fazendo isso da maneira fácil em vez da maneira difícil, as complexidades de tempo das funções serão as mesmas que as originais. Então, lembra-se disso para o tempo? Oh, de n e este vai ser Nós só estamos fazendo isso duas vezes. Então, duas vezes e nós caímos constante, então ele vai ser dentro. De qualquer forma, este ia ser três vezes dentro, que vai voltar a transformar-se em oh, então o espaço vai ser a mesma coisa. Então a complexidade do espaço para este aqui acabou, porque onde criar uma matriz inteiramente nova com os mesmos itens aqui, ele vai ser também de dentro novamente. Fomos multiplicados por dois. Uma vez que a função é chamada duas vezes, temos dois desses e memória ao mesmo tempo, e a complexidade do espaço também vai acabar sendo de qualquer coisa para este. É isso. Espero que tenha sido divertido. E eu vou ver vocês no próximo vídeo onde nós realmente aprendemos como girar uma matriz no lugar . E o que isso significa é que não podemos criar qualquer aumento ou quaisquer estruturas de dados adicionais em nossa função. É um problema muito mais difícil, e vamos ter de reescrever tudo, por isso vemo-nos lá. 13. Rotação de matriz em lugar - Estratégia: Bem-vindos ao próximo problema. Gire a matriz no lugar. É exatamente a mesma coisa, é o último problema. Exceto que neste caso, sabemos que sempre teremos uma matriz quadrada, significando três por 3555 10 por 10 qualquer coisa. E nosso objetivo é girá-lo 90 graus no sentido horário. Mas desta vez precisamos fazer isso no lugar. E a chave para o que no lugar significa é que você não pode criar matrizes extras ou um aumento em sua função ou qualquer outra estrutura de dados. Realmente. Tudo o que você pode armazenar são variáveis. Vá em frente e experimente isso sozinho, se quiser. Vou avisá-lo. Este é muito difícil. E mesmo uma vez que você descobre como fazê-lo, o código é muito difícil de escrever. Então eu vou resolver isso em dois problemas. Primeiro vamos discutir a estratégia que vamos empregar, e depois mostraremos algum código. Então eu tenho um pequeno bloco de esboços aqui. Oops. E vamos tomar esta matriz como entrada e apenas discutir a estratégia que vamos usar. Então aqui temos uma matriz de cinco por cinco e vamos usar isso como exemplo. Agora vou em frente e derrubar o perímetro da Matrix. Então vamos fingir que o interior nem existe. Só nos importamos com a Thea linhas e colunas externas. E o que queremos dialogar é isto. Queremos pegar o número superior esquerdo e movê-lo para cá. Então, queremos mudar isso para cá. Mas antes de fazermos isso, temos de descobrir o que fazer com este número. Não podemos simplesmente anular porque este número tem de se mudar para cá e este tem de ir para cá. E, finalmente, este precisa ir até aqui para completar o nosso pequeno círculo. Então, quando fizemos este aqui se mudou para cá, o Fives mudou-se para cá, 20 cincos aqui e 20 aqui em cima. Fizemos uma rotação total de 90 graus dos cantos, então esses cantos foram girados completamente. Agora o que vamos querer fazer é continuar. Começa aqui e vamos ter de mudar este tipo para cá e os 10 vão para o local de 24. 24 vai ir para 16 e o 16 vai substituir onde os dois originalmente saíram. Então agora temos a frente, e nós giramos 2/5 de todo este perímetro externo, e nós precisamos realmente metade dele. Desculpe, porque só nos importamos quando ele precisa fazer isso quatro vezes. Então, quando você faz isso para os cantos e, em seguida, este item neste item e, em seguida, os quatro aqui , nós já fizemos os cinco que já foram tratados. Então só precisávamos fazer isso quatro vezes. Isto é o que vamos precisar para codificar assim que formos capazes de replicar isto e eu não vou desenhar as setas novamente porque isso vai tornar isto desnecessariamente confuso. Mas uma vez que percebemos que assim que fizermos isso, podemos seguir em frente para a próxima fila. Não somos a próxima fila. Desculpe. Próximo perímetro. Então eu vou ir em frente e pegar isso daqui, e eu vou tentar movê-lo um pouco mais baixo e voltar para o lápis. Assim que terminarmos o perímetro externo, que significa que está totalmente girado, podemos passar para o próximo perímetro interno, e queremos fazer exatamente a mesma coisa. Mova esse cara aqui. Mova esse cara aqui e em frente e em frente. E uma vez que possamos fazer isso, podemos passar para o próximo. Neste caso, vez que só tínhamos um 555 o último perímetro será o número 13 por si só. E nós podemos deixar isso, como é, então nós realmente precisamos fazer isso duas vezes. Neste caso, se for sete por sete terá de fazê-lo mais uma vez se for um nove por nove e depois outra vez. Mas esta é a estratégia que precisamos codificar. Vá em frente e experimente sozinho. E na próxima lição, mostraremos a solução e mostraremos como ela funciona. 14. Rotação de matriz em lugar - Solução: Bem-vindos de volta para girar a matriz no lugar. Em vez de resolver este problema. Viva como temos feito para o passado vários problemas, eu pensei que seria melhor apenas mostrar a solução e falar sobre isso. Este problema é talvez o problema tecnicamente mais desafiador em todo este curso. Então, ao invés de mexer no meu casaco, meu código enquanto tentava explicar para você, achei que seria mais fácil escrever e explicar depois só para ter certeza que funcionaria. Vamos em frente e executá-lo. Então, para esta matriz aqui, esperamos isso como saída. E se eu tivesse fugido mais uma vez, temos a mesma coisa e é exatamente o que esperamos, que é bom. Vamos em frente e mostrar-lhe o código e falar sobre o que cada linha está fazendo. Então mentir 21 Isso é variável. As camadas totais vão conter um número que nos diz quantas camadas precisamos passar . E o que quero dizer com uma camada é cada um destes. Então aqui, esse perímetro é uma camada que queremos passar. Queremos girar cada item neste perímetro e depois passar para a próxima camada, que será este círculo interno bem aqui. Então, se temos uma matriz que é um cinco por cinco. Só precisamos passar por duas camadas. E esta fórmula aqui vai nos dizer que o loop interno para, vamos de zero para o número de camadas, como acabamos de mencionar. E isso faz sentido. E esta linha aqui está determinando a condição de parada para o nosso loop interno para. E a maneira como isso funciona é que vamos começar na camada mais um. Então o que isso significa é que estamos começando. Então, quando começamos com estas camadas Matrix essencialmente está inicialmente indo para igual a zero. Então estamos dizendo que queremos começar no índice um, que significa que no 02 aqui a condição de parada, que vai ser a camada de comprimento de ponto mate menos, significa que queremos parar em cinco menos zero. Então, queremos parar aqui mesmo. Então, quando passamos por este exercício, começamos em 01 e acabamos Oh, pois nosso loop é em vez de começar em 02 e terminando em 05 que funcionará da mesma forma. Então nós movemos os dois para as dezenas, colocamos que 10 para 24 24 para 16 e 16 para 2, e então passamos para o três e giramos e, em seguida, o quarto e, em seguida, o último de todos nós fazemos as curvas. Este código aqui está fazendo todo o trabalho pesado. Então, quando estamos movendo os dois para o 10, vamos precisar armazenar o 10 em uma variável antes de podermos substituí-lo por dois. Se o substituirmos, perderemos 10. Então precisamos armazenar isso e, em seguida, atualizar seu valor. Então precisamos armazenar o 24 bem aqui, e precisamos substituí-lo com o 10. Então nós vamos realmente precisar de duas variáveis diferentes. Tempel um e tentativa de temporário um vai estar armazenando o 10 inicialmente e temperamento para será armazenar 24 irá girar seu uso Então o 10 vai se mover aqui, e nós vamos bater isso em uma variável. Então 24 vai passar para 16 que vamos armazenar em uma variável e, em seguida, 16 vai se mover para onde é feliz. É provável que você precise passar por uma rotação de matriz manualmente para observar como isso funciona. Acompanhe cada uma das variáveis e acompanhe o que está acontecendo literalmente. Tente desenhar uma matriz em um pedaço de papel e passar por este código. Uma vez que cada um deles é trocado e toda a camada é girada, este loop interno vai ser concluído, e este loop externo vai ser incrementado. Então vamos nos mover para esta camada, e vamos fazer exatamente a mesma coisa. Então nosso loop vai começar no oito e terminar no nove que vai girar o A para movê-lo para o 14 mover o 14 para frente e para frente e para frente, e então ele vai fazer as curvas depois disso. Então ele vai mover o nove para o 19 e sobre e sobre e sobre e sobre o final. Acabamos de devolver a mesma matriz que nos foi dada. Seja qual for a complexidade do tempo e do espaço, só processamos cada item uma vez que giramos uma camada, e então passamos para a próxima camada, a complexidade do tempo será fora do espaço. Complexidade. Bem, nós não estamos criando uma única estrutura de dados em nenhum lugar aqui. Tudo o que estamos fazendo é usar variáveis. Não importa o quão grande é a Matrix. Usamos o mesmo número de variáveis, então isso vai se mover para O de um. Este é duro. Se perguntado em uma entrevista, você provavelmente será solicitado a apenas dar a estratégia geral que você usaria e talvez falar sobre a eficiência um pouco. Corrigir pode levar um bom programador horas, o que seria muito longo para uma entrevista. Esse problema é ótimo em nos fazer pensar sobre como transformar dados espacialmente. A capacidade de entender a solução mostra poderosas habilidades de raciocínio e excelente raciocínio espacial também. Se isso for muito complexo, tente voltar a ele outra hora. Tente caminhar através da função usando uma matriz simples, como um dois por dois ou três por três. Acompanhe cada uma das variáveis e o que está acontecendo com a Matrix. Vá em frente e experimente você mesmo para qualquer matriz quadrada que você gosta. Vejo-te no próximo vídeo