Transcrições
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. Personagens únicos: Bem-vindo ao seu primeiro problema é único. O objetivo aqui é escrever uma função que levará em uma string e determinar se cada caractere nessa string aparece apenas uma vez. Essencialmente, estamos tentando ver se cada caractere na string é único nessa força. Queríamos diferenciar maiúsculas e minúsculas, significando que ambas as versões minúsculas e maiúsculas de uma letra na mesma string são consideradas únicas. Aqui estão alguns exemplos. Obtemos uma string normal A, B, C, D E f, e tudo é único, então queremos que a função retorne. Verdadeiro. Este próximo exemplo apenas mostra que queremos que nossa função seja capaz de aceitar uma string com qualquer tipo de caractere, não apenas letras. Novamente. São todos únicos. Então nos tornamos verdadeiros. Este terceiro exemplo mostra novamente que um A minúsculo em um A maiúsculo na mesma string ainda desejaria que nossa função retornasse. Verdadeiro para essa entrada, o 4º 1 mostra um oito minúsculas duplicado e sua função retornaria false. Vamos apenas ir em frente e começar a escrever esta função imediatamente. Então, para ter certeza que cada caractere em nossa string é único, vamos precisar processar cada caractere na string, então sabemos que vamos precisar fazer loop. Vamos em frente e começar por aí. O que queremos fazer neste ciclo? Bem, uma estratégia que podemos empregar é a seguinte. Nosso loop aqui vai passar por uma corda da esquerda para a direita. Então, tomando isso como exemplo, vamos começar em um. O que podemos fazer é que podemos ter outro loop indo da direita para a esquerda procurando esse mesmo personagem. Então, enquanto nosso loop externo está em um, podemos ter um loop interno indo da direita para a esquerda. Também à procura de um se ele encontrá-lo e não está na mesma posição que o loop externo está em, sabemos que temos uma duplicata e podemos retornar imediatamente falso. Se não houver duplicado, isto vai correr até chegar ao A aqui, e sabemos que é único na rua. Podemos repetir isso indo da esquerda para a direita como nosso segundo loop vai direito do dedo esquerdo. Para cada caso individual, isso pode parecer complicado, mas há um pequeno método que nos torna muito simples para nós. Vamos escrever e discutir logo após o último índice. Isso vai fazer exatamente o que eu estava descrevendo. Ele vai passar pela corda direita dedo do pé esquerdo, procurando o personagem que fornecemos neste caso, qualquer personagem que eu esteja atualmente em. Então, novamente, nós damos a ele um neste caso para a primeira rodada, e ele vai para a direita pela esquerda procurando um Então o que estamos fazendo é certificar-se que o último índice de A é o mesmo que o índice atual que estavam em. Isso mostrará que o caractere não é duplicado na string. Se, no entanto, o último índice off A não é o mesmo que o primeiro índice de a, então podemos retornar imediatamente falso Um, isso é realmente toda a lógica que precisamos no final da função, podemos retornar É verdade, ele só chega aqui depois de processar cada personagem aqui e se certificou de que não há duplicatas, trabalho
disfuncional. Vamos seguir em frente e código runner aqui, e esperamos ver true, true, true, true, false e isso é exatamente o que vemos aparecer para que nossa função funcione corretamente. Vamos passar pela complexidade de tempo desta função para que possamos ver que temos um loop for e que imediatamente traz nossa complexidade de tempo para O de n porque cada caractere está sendo processado aqui mesmo. Na verdade, temos outro loop na forma de último índice de Bem, não
é um loop que escrevemos. É um loop que está passando pela cadeia da direita para a esquerda. Então este é, na verdade, outro o de fim. Uma vez que este é aninhado dentro do loop externo, precisamos multiplicar essas complexidades de tempo para dar uma complexidade de tempo final de O de n vezes n oh de n ao quadrado. Qual é a complexidade do espaço? Bem, vamos pensar sobre isso. Não importa o tamanho da string, quer se trate de três caracteres ou 30 ou 300, estamos sempre usando apenas uma variável em toda a nossa função. E isto é, eu só estava armazenando um personagem de cada vez. Não importa o quão maior é a entrada, nossa função ocupa a mesma pequena quantidade de espaço. Então dizemos que ele usa espaço constante, ou O de um. É isso para esta versão. A solução. Podemos melhorar um pouco a complexidade do tempo. Sim, podemos. Vamos tentar isso. Há algo que podemos fazer antes de passarmos por nossa corda para torná-la um pouco mais simples , podemos classificar nossa corda. Então vamos em frente e tentar isso. Então o que eu fiz até agora aqui é que eu estou pegando a corda e dividindo-a em uma matriz. Isso é o que este método dot split faz com uma string vazia aqui. Então, neste ponto, carros seriam apenas iguais a uma série de caracteres individuais na mesma linha que nós
consortamos . Os caracteres agora serão classificados da esquerda para a direita. Então, se nos dessem algo como D B A C, pareceria que teria uma matriz. Seria agora uma matriz de A,
B, B, C e D. Simples é que o que podemos fazer agora que nossos personagens são classificados? Bem, há uma lógica diferente que podemos aplicar para tornar isto muito mais fácil. Vamos precisar do padrão para loop novamente. Na verdade, eu ia começar em um para este, e vamos explicar por que em um segundo então agora. Mas eu não sei o que os personagens são classificados individualmente. Se houver duplicatas, elas serão colocadas ao lado uma da outra novamente. Assumindo que temos D B A. C A. Isto agora se transformará em B C D.
As duas duplicatas aparecem ao lado uma da outra. Então o que queremos fazer é para esta string, ou melhor, esta matriz de caracteres. Queremos começar pelo segundo
caractere, e o que queremos fazer é compará-lo com o personagem anterior. Se forem iguais, é uma duplicata, e podemos retornar falso imediatamente. Vamos codificar isso. É isso. Esta função funciona perfeitamente também. Vamos executá-lo apenas para ter certeza de que
estamos esperando Verdadeiro, Verdadeiro,
Verdadeiro ,
Verdadeiro , Falso. E isso é exatamente o que temos. Vamos limpar isso um pouco. E novamente, vamos falar sobre as complexidades do tempo e do espaço. Então, neste caso, estamos começando com uma loja para aqui. Agora, diferentes algoritmos de classificação têm diferentes complexidades temporais, mas em geral, se estamos falando de uma espada, podemos assumir a complexidade temporal de O do fim dos tempos. Log de n Isto aqui é um loop padrão. Só vai ser Oh, de N porque essas coisas acontecem sequencialmente e não temos um loop dentro de um loop. Podemos simplesmente adicioná-los. Então vamos começar com O de M Times. Um log de fim mais o de N, que se transforma em oh de N mais n vezes ao longo de End e N é um termo de ordem inferior a este aqui. Vamos simplificar ainda mais isso para mostrar exatamente o que isso significa quando estamos falando de tempo, complexidades enfraquecem. Simplesmente elimine os termos de ordem inferior para que possamos nos livrar deste mais e nossa complexidade final acaba sendo exatamente isso. Oh, do fim dos tempos muito tempo deles e que sua complexidade de tempo para esta solução. E quanto ao espaço? Anteriormente era mais de um, mas agora estamos pegando cada personagem e estamos armazenando com pressa. Isso é o que acontece aqui. Então estamos armazenando cada caractere, que
significa que ocupamos a mesma quantidade de espaço que o tamanho da entrada. Então vai ser, oh de, e vamos falar sobre mais duas soluções no próximo vídeo. Vejo você lá
3. Processamento rápido de cadeia: Bem-vindos de volta ao seu único. Agora passamos por duas soluções, e conseguimos melhorar a complexidade do tempo de O e quadrado Tio de End Times. Log de Fim. Nós conseguimos isso classificando a string que obtemos como uma entrada. Podemos realmente tornar nossa complexidade de tempo ainda melhor. E isso exigirá uma estratégia diferente. Vamos apagar tudo isso e começar de novo. Então, da última vez, nós tínhamos ordenado a string. Você quer fazer algo diferente desta vez, vamos criar um objeto para armazenar personagens enquanto nos deparamos com eles novamente. Vamos precisar de um loop atravessando nossa corda e não gosta de algo. 04 loop. Então o que queremos fazer é verificar se o nosso objeto já contém uma cópia do
trabalho do personagem que está sendo processado atualmente. É isso. Este é, na verdade, todo o problema é apenas isso. Corra de novo e certifique-se de que está funcionando bem. E não está funcionando bem. O que está acontecendo? Devolveu False aqui. Isso precisa ser verdade. Lá vamos nós. Minhas desculpas. Então vamos analisar o que está acontecendo aqui mais uma vez enquanto passamos por cada personagem, por exemplo, Vamos pegar essa string aqui. ABC A e F. Vamos processar cada item individualmente. Então, a primeira vez que passarmos por
este loop, este carro vai ser um Nós vamos verificar se o nosso objeto já o contém. E se isso acontecer, queremos retornar as quedas. Nosso objeto está vazio no início. Então esse cheque passa e passamos para aqui. Nós vamos armazenar um em nosso objeto. Vamos apenas definir seu valor igual a true. Então nosso objeto conterá todos os caracteres que já processamos até agora. À medida que
passarmos pela corda, vamos adicionar um e depois B e depois ver quando chegarmos ao próximo
a vamos novamente verificar se os carros tem o personagem A E seisso é verdade, isso é verdade, porque já temos visto e já o inserimos em nosso objeto. Sabemos que é uma duplicata e podemos retornar imediatamente falso. Se passarmos por todo esse loop, sabemos que não há duplicatas e a string e podemos retornar true. É isso. Vamos falar sobre a complexidade do tempo nesta versão desta função. Só temos um loop. Estamos passando por cada personagem e à medida que passamos por cada personagem, as coisas que fazemos aqui são tempo constante. Não há mais loops ou qualquer coisa dessa natureza. Então nós temos um único loop nos dando uma complexidade Tom de O de N. E quanto ao espaço? Bem, cada personagem que passa está sendo armazenado em nosso objeto. Então o espaço também vai ser um amor N porque é proporcional ao tamanho da entrada. Há uma maneira de mudarmos isso um pouco. Em vez de um objeto, vamos usar uma construção E S 2015 chamada conjunto, agora um conjunto semelhante a um objeto. Exceto que é mais apropriado para essa tarefa exata, repente como uma estrutura de dados destinada a conter itens únicos. Vamos realmente ir em frente e olhar para o Indian Page quatro conjunto como podemos ver, um conjunto, é um objeto que permite armazenar valores únicos de qualquer tipo, uh, em um conjunto. Portanto, um valor em uma configuração pode ocorrer apenas uma vez, e é exclusivo na coleção de conjuntos. Então esta é uma estrutura de dados especificamente feita. Essencialmente, para este problema, só
precisamos mudar algumas coisas. Por exemplo, Em vez disso, precisamos usar um método embutido e a mesma coisa aqui em vez de definir. Em vez de definir nosso item como verdadeiro, vamos simplesmente adicioná-lo ao conjunto. Não precisamos disso. E não precisamos disso. E novamente para ter certeza que isso funciona. De facto, dá-nos o que queremos. Verdadeiro, verdadeiro, verdadeiro, falso. vez, Isto é muito semelhante a um off para o método que tínhamos antes com um objeto. A única diferença é que trocamos ou estrutura de dados. E há uma boa razão para termos feito isso. Isso nos permitirá escrever nossa solução de uma maneira nova e ainda mais simples. E discutiremos isso no próximo vídeo. Veja, ali
4. Personagens exclusivas: simplicidade definitiva: Bem-vindos de volta ao seu único. Agora cobrimos três maneiras diferentes de resolver esse problema. Para o último método, mostramos como fazê-lo com um objeto e um conjunto. Agora você deve estar se perguntando por que eu te mostrei este conjunto. Ele faz a mesma coisa que um objeto, e ele realmente não oferece nada de novo. É só mais uma coisa para aprendermos e nos acostumarmos. Quero mostrar-vos o verdadeiro poder por trás de um conjunto,
e quero mostrar-vos uma forma de tornar a nossa solução muito,
muito mais simples. Quero mostrar-vos o verdadeiro poder por trás de um conjunto, e quero mostrar-vos uma forma de tornar a nossa solução muito, Então, antes de fazermos qualquer coisa, vamos mergulhar em algumas das propriedades de um conjunto. Vamos apenas criar um novo aqui e vamos jogar em alguns itens então vamos dar-lhe um array com os números de um a cinco, e vamos fora disso. Então, como você pode ver, quando nós nos damos definir um array, ele vai levar cada item individual na matriz. Um adicionado no set. Agora, o que foi un intuitivo, pelo
menos para mim, foi o que acontece quando lhe damos uma corda em vez disso? Esperanças então vamos em frente e nos livrar disso e em vez disso dar-lhe a corda A B C D e. Como você pode ver, o que aconteceu é que cada caractere individual na string foi inserido no conjunto. Um por um, a corda dividiu-se essencialmente. Para nós, isso é muito importante. Há mais uma coisa que eu quero apontar e que é a propriedade tamanho. Portanto, uma string tem uma propriedade length, que informa o número de caracteres na string. Um conjunto tem uma propriedade de tamanho que apenas informa o número de itens no conjunto. Então, como esperado
, são cinco porque temos cinco itens diferentes no conjunto. Quero mostrar mais uma coisa, que é o que acontece se adicionarmos duplicatas. Deixe-me ir em frente e adicionar ABC novamente e nós executá-lo e vemos que a saída aqui é exatamente a mesma porque set novamente só pode conter itens exclusivos. E os personagens A, B e C já estão lá. Então ignora completamente esses três. E o conjunto contém cinco itens como podemos ver aqui. Vamos voltar ao nosso problema. Vou apagar tudo isso e escrever uma linha de código e falaremos sobre isso logo depois. Essa é, na verdade, toda a solução. E deixe-me executar isso só para mostrar que funciona. E ele faz. Vá em frente e teste sozinho, se quiser. Vai funcionar toda vez. Vamos discutir por que isso é como mostrado antes aqui. Se formos duplicados no set, eles serão completamente ignorados. Isso é o que está acontecendo aqui. Nós inserimos uma string no conjunto, e cada caractere individual está sendo inserido no conjunto foram então verificando para ver se o tamanho do conjunto é o mesmo que o comprimento da string original. Se não houvesse duplicatas do que o tamanho do conjunto, deve ser exatamente o mesmo que o comprimento da string. No entanto, se houvesse duplicatas no acordo, ser um pouco menor. Ao retornar esta comparação diretamente, nós resolvemos todo o problema se sua única esta igualdade do verdadeiro e do funcional retornar verdadeiro. Se houver caracteres duplicados, essa igualdade não será realizada e a função retornará false novamente. Vamos passar pela complexidade do tempo e do espaço para esta função. Estamos pegando uma string e estamos adicionando-a ao caractere definido por caractere. É uma operação linear. Então é O de espaço final novamente foram adicionando cada caractere individual no conjunto, então ele vai ser proporcional ao tamanho da string. Então, mais uma vez ,
oh, de n vamos rapidamente terminar falando sobre tudo o que cobrimos até agora. A primeira solução que surgiu foi a solução de força bruta que tinha um juramento e complexidade de tempo
quadrado é
simples, direta. E é a primeira solução que a maioria das pessoas vem com. Se você puder identificar a complexidade do tempo e depois trabalhar para torná-la melhor, você enfrentará essa pergunta em uma entrevista. A segunda solução envolveu a classificação da string. Primeiro, era melhor em termos de tempo, complexidade, mas tivemos que aumentar a complexidade do espaço para essa solução. A terceira e a quarta soluções são ideais. Temos a menor complexidade de tempo, e reduzimos a O de fim, que é uma melhoria muito significativa. A 4ª 1 aqui é inteligente, mas a 3ª 1 teria sido mais do que suficiente. Em uma entrevista, ambos
alcançaram a melhor complexidade de tempo possível. A idéia principal é tirar isso é que a aplicação de várias técnicas para um problema, Consignia melhorar eficientemente tempo ou espaço complexidade. A classificação de nossos dados os
reduziu, reduziu nossa complexidade de tempo e, em seguida, usando uma estrutura de dados apropriada, um objeto ou conjunto melhorou novamente. Veremos isso surgindo de novo e de novo nos problemas futuros. Tente usar um conjunto de matriz de objetos. Empilhe a nossa sugestão ou qualquer outra estrutura de dados e veja se isso abre novas vias para a sua solução. Vejo você no próximo problema no próximo vídeo.
5. Arrays aninhados: Bem-vindo ao nosso segundo problema achatado array. Neste problema são entrada vai ser uma matriz de matrizes aninhadas,
às vezes matrizes profundamente aninhadas. E nosso objetivo é escrever uma função que levará cada item individual na matriz e extraído para uma nova matriz plana. Aqui está um exemplo. Recebemos um array que tem vários ou raise dentro dele, além de outros itens. O objetivo é tirar esses itens de suas matrizes profundamente aninhadas em uma única matriz plana preservando a ordem. As entradas podem ser números, ou podem ser strings, ou podem ser objetos que podem realmente ser qualquer coisa. Nosso objetivo é levá-los o que quer que sejam e colocá-lo em uma nova matriz plana,
preservando a ordem. Este problema tem alguns usos práticos em uma carreira de desenvolvedores. Eu tive que lidar com fontes de dados aninhadas muitas vezes, e resolver esse problema vai lhe dar algumas informações sobre como resolver problemas semelhantes que surjam no futuro. Ao contrário do último problema em que mostrei soluções e depois discuti-las, acho que será mais instrutivo neste caso percorrer a solução. Então vamos em frente e começar. Eu encorajo você a pausar o vídeo e tentar você mesmo primeiro. Vamos em frente. Então precisamos criar um novo array. Primeiro, vamos em frente e fazer isso. Ok? Vamos precisar examinar cada item em nossa memória e processá-los um por um. Então vamos precisar de um loop. Ok? Vou apenas armazenar o item atual em uma nova variável. E o que queremos fazer aqui? Bem, vamos querer fazer alguma coisa. Se este item aqui é um array e vamos querer fazer outra coisa se não estiver compressa,
Se
nãofor pressa,
Se
não um array, então podemos imediatamente empurrá-lo para o nosso novo array. Mas se for, precisamos passar por cada indivíduo, o
chefe da escola e começar a revestir isso. Então, primeiro, o que queremos fazer é verificar se este item é um array. Então, se este item não é um array, sabemos que ele não está mais aninhado, e podemos ir em frente e empurrá-lo diretamente para o nosso novo array. No entanto, se for um array, o que queremos fazer é pegar cada item individual dentro da bateria e empurrar aqueles um por um
para um novo array. Então nós vamos realmente precisar de outro loop aqui, e no final, queremos retornar nossa nova matriz. Ok, então esta função aqui vai funcionar se tivermos uma matriz aninhada um nível de profundidade,
por exemplo, por exemplo, digamos que esta é a nossa entrada. Nosso funcional funciona corretamente para este array, e ele irá transformá-lo em um array que não está aninhado. Isso se parece exatamente com isso. Só para ter certeza que funciona. Vamos em frente e testá-lo. E funciona. Vamos ver por que isso funciona. Então nós estamos dentro para loop, e este item, a primeira vez, vai ser o número um. Não é um array tão ruína para empurrar diretamente para o novo array, que agora terá apenas um dentro dele. A próxima vez que este item vai ser, também, e nós vamos fazer a mesma coisa e novamente a mesma coisa para três. Eventualmente chegamos a este array, que tem cinco estrangeiros dentro dele, e nós vamos para esta parte da declaração if nós vamos passar por cada item aqui e empurrar cada item, que é cinco estrangeiros individualmente em. Então ele vai apenas ir em frente e adicioná-los em novo organizar novamente com seis. Vamos entrar aqui e empurrá-lo diretamente. E é por isso que esta função funciona da maneira que funciona agora. O que acontece se tivermos mais necessidades? Por exemplo, se temos algo como, Desculpe-me, algo
assim, não vai funcionar porque estamos indo apenas um nível profundo. Em vez de ir para este e empurrar sete, ele vai empurrar este array inteiro para o nosso novo array. Então, como consertamos isso? Bem, a chave está aqui, então não sabemos quantos níveis de profundidade vamos precisar ir. Por exemplo, o sete pode ser outro array profundo. Pode até ir mais longe, e pode continuar. Esse é o problema que estamos tentando resolver. Então nós realmente não sabemos quantas vezes, e nós vamos precisar ir porque nós não sabemos quão profundamente aninhados esses itens podem ser. Se o ator precisaria transformar isso em uma função recursiva, e aqui está como fazemos isso. Isto vai funcionar. Vamos testá-lo só para ter certeza. E funciona exatamente como esperamos. O que fizemos aqui? Bem, estamos dizendo que se nos depararmos com uma matriz aninhada, vamos chamar toda a função achatada novamente sobre isso necessário. Vamos pensar sobre isso. Vamos ver. Chegamos a este item, que é uma matriz aninhada. Parece três níveis de profundidade. Quando isso acontecer, vamos passar por ele. Aplanar mais uma vez, assim achatado na próxima vez em torno de baixo receber uma matriz, aninhado dois níveis de profundidade. Mais uma vez, vamos passá-lo. Ele vai receber este, e novamente ele vai passar e receber este. Eventualmente, ele vai chegar a apenas sete, e ele vai pegar isso e ele vai empurrá-lo para um novo array. Isso funcionará não importa o quão profundamente aninhados estejam. Array é
6. Discussão de matriz de Flattening: Bem-vindos de volta ao achatado. Rickerson é um conceito difícil, então eu encorajo você a tomar algumas entradas diferentes e percorrer a função várias vezes por conta própria. Certifique-se de que você se convenceu de que a solução funciona da maneira que você acha que funciona . Vamos falar sobre a complexidade do tempo dessa função. Temos um loop de quatro aqui, e temos uma chamada recursiva e até mais quatro loop aqui em baixo. Na superfície, parece que a complexidade do tempo vai ser muito insana neste caso, mas na verdade é bastante simples. Vamos ignorar a função por enquanto, e apenas pensar sobre o que ela está fazendo com uma entrada. Novamente. Vamos levar este. À medida que passamos pela função, cada item é empurrado um por um em nossa nova matriz. Então nosso loop irá aqui e ele vai processar um e colocá-lo de outra maneira, pouco processo para e colocar em nossa nova matriz, e ele vai fazer a mesma coisa com três. Uma vez que ele chegar a esta matriz, ele vai mergulhar dentro dela e vai processar quatro, depois cinco e depois seis. E quando ele chegar aqui, ele simplesmente mergulhará no fundo,
processará o sete e depois voltará para fora. Como você pode ver, cada item é processado apenas uma vez. Temos todos esses loops e até temos uma chamada recursiva. Mas no final, cada item aqui é processado. Uma vez que nos dá um tempo linear, complexidade ou oh, de fim. E quanto ao espaço? Bem, cada item individual é armazenado em sua nova matriz, então é proporcional ao tamanho da entrada novamente, Linear. É isso mesmo para este problema. O que você pode tirar é que Rikers em é uma ferramenta poderosa. Sempre que você pode ver que você vai estar repetindo algo neste caso mergulhando em uma matriz e você não sabe quantas vezes você pode precisar fazer isso, você provavelmente vai precisar de Rickerson. Obrigado. E vejo-te no próximo vídeo.
7. Removendo personagens duplicados: Bem-vindos ao problema número três. Remova os enganos. O objetivo aqui é escrever uma função que levará em uma string. A função deve retornar uma nova string com os mesmos caracteres que a string original, mas com caracteres duplicados removidos. Então, se a nossa função é dada uma string com caracteres únicos, queremos retornar essa string exata. Se houver duplicatas, queremos removê-las mantendo a ordem dos caracteres. Isso é o que estes dois exemplos de ar fazendo aqui. Vamos em frente e começar a escrever esta função novamente. Eu recomendo que você pausar e ter certeza de si mesmo e, em seguida, voltar para este vídeo. Precisamos iniciar esta função criando uma matriz para armazenar os caracteres únicos em nossa string. Vamos em frente e fazer isso. Vamos precisar de um loop para processar cada personagem individual. Então vamos direito que dentro deste loop primeiro queremos verificar se o caractere atual estava processando já existe em nossa matriz. Se ele já está em nosso array, isso significa que nós já vimos antes e não queremos reinseri-lo, então nós só queremos continuar. Se, no entanto, é a primeira vez que o
vemos, queremos empurrá-lo para o nosso array. Nosso conjunto exclusivo de carros agora contém apenas personagens únicos. O que queremos fazer é transformar isso em uma string e retornar essa string, e essa é a solução. Vamos executá-lo e certificar-nos de que funciona. E ele faz. Na verdade, vemos um B. C D aparecendo três vezes exatamente o que queremos. Vamos ver as complexidades do tempo e do espaço para o tempo que não temos fora para loop aqui. Isso imediatamente nos leva a O de N Senhor linear porque estamos processando cada personagem dentro deste para loop que usamos inclui este em si é um loop porque ele está passando por este conjunto de carros
únicos e procurando por este carro. E para fazer isso, ele tem que passar individualmente por tudo no array. Então ele tem que percorrer a matriz da esquerda para a direita, e isso irá parar quando outro encontrar o item ou chegar ao fim. Mas é de fato um loop, e porque temos um loop em um loop, vamos ter oh do fim dos tempos. Desde que você está multiplicando suas complexidades de tempo, que nos leva dedo do pé de n Square e que é a nossa complexidade tempo. E quanto ao espaço? Bem, nós temos que pegar a corda e inserir cada caractere único em nossa matriz. Então temos que essencialmente armazenar a string inteira novamente, quase toda a string, pelo
menos. Então isso vai ser Oh, de N porque a quantidade de dados que usamos vai ser proporcional ao tamanho da entrada . Há uma maneira de tornarmos esta complexidade do tempo um pouco melhor depois de muito melhor . Vamos passar por isso. Então eu estou adicionando um objeto à nossa matriz bem aqui. Sempre que empurrar um caractere em nossa matriz, também
queremos adicioná-lo ao nosso objeto. Em vez de verificar o array para ver se ele contém nosso personagem, agora
queremos verificar o objeto. Então vamos substituir isto. Isso não é mais um “O” de uma operação. Esta é uma verificação de tempo constante. Se um objeto contiver um item é uma operação de tempo constante. Acontece praticamente instantaneamente, ao contrário
de uma matriz que tem de ser procurada do início ao fim. Como não temos mais um loop dentro de um loop, temos apenas um único loop trazendo nossa complexidade de tempo para um total off. Oh, e há uma maneira
de tornarmos isso um pouco mais simples. Não vai fazer muito para um tempo ou espaço complexidades, mas vai tornar o problema muito mais elegante e muito mais fácil de entender. E vamos passar por isso no próximo vídeo. Vejo você lá.
8. Remova duques: simplicity definition: Bem-vindos de volta para remover dupes. O que fizemos até agora foi resolvido este problema e, em seguida, reduzir a complexidade do tempo. Começamos por cima e ao quadrado, e ao adicionar um objeto, conseguimos reduzi-lo a O de fim. Há outra maneira de resolver esse problema, que não muda suas complexidades de tempo ou espaço. Isso torna o problema muito mais fácil de pensar. Eu só vou escrever a solução e depois podemos discutir isso. Vamos ter certeza que funciona e funciona. Conseguimos o que esperamos. Esta é a solução, e vamos explicar o que está acontecendo. Estamos usando um conjunto mais uma vez. Então, quando inserimos uma string em um conjunto, cada caractere individual é inserido em um conjunto apenas valores únicos ar armazenados. Assim, todas as duplicatas serão ignoradas e descartadas depois que o conjunto é criado. Usamos esse método chamado de ponto de raio a partir de agora o que o ataque faz é levar em uma epidural, um adorável, e JavaScript é uma estrutura de dados que mantém nosso controle da ordem em que os dados foram inserido e um conjunto faz exatamente isso. Um conjunto vai manter o controle dos caracteres na ordem em que foram inseridos, que é exatamente o que precisamos, porque ele faz isso podemos dizer que se set é um honroso e ele vai trabalhar com este método arrancado a partir do qual vai literalmente transformou-o em um array. Então esta declaração aqui é igual a uma matriz contendo os caracteres únicos e a força com sua ordem preservada. Tudo o que estamos fazendo depois disso é usar juntar-se para transformá-los em uma corda. A complexidade do tempo aqui é exatamente a mesma. Tomamos cada personagem e inseridos no conjunto um por um. Então esse é o loop. Dando-nos oh, de fim. Juntá-la a uma matriz é o nosso arrependimento. Transformá-lo em uma matriz também é antigo, em seguida, juntando-o como oh, de n mais uma vez. Então temos três n e quando deixamos cair a constante, ficamos em O de n para a complexidade do espaço. Colocamos cada personagem em um conjunto e, em seguida, em uma matriz. Então temos oh de dois n, que novamente se torna O de n. Esperemos que o mostra o quão poderoso é um conjunto e quanto masterização estruturas de dados pode ajudá-lo com esses problemas. Quanto mais você souber, mais você será capaz de aplicar essas coisas e problemas futuros. Viramos o que era sobre uma função de 15 linhas. Se as duas linhas, é muito mais fácil de ler, entender e certo, eu vou vê-lo no próximo vídeo.
9. Frequência mais elevada: Bem-vindos ao próximo problema. Frequência mais alta. O objetivo aqui é escrever uma função que levará em uma matriz de strings e retornar. A string que ocorre mais comumente implícita neste problema é que a teoria que você recebe pode ter algumas strings duplicadas, algumas lá várias vezes, e queremos a que aparece com mais freqüência. Se houver várias strings com a mesma alta freqüência, queremos retornar a que aparece primeiro. Aqui estão alguns exemplos no 1º 1 C é a única string que aparece mais de uma vez, modo que é o que queremos retornado no próximo. ABC aparece três vezes e D E F duas vezes, então queremos ver ABC saindo no próximo. Ambos são presidentes apenas uma vez. Tão arrependido. E já que ABC é o primeiro, queremos que um volte para fora e no último olhos GH e eles são mais vezes do que qualquer um dos outros. Então é isso que queremos voltar. Vamos em frente e começar a solução, então vamos precisar processar cada string que está em nosso array, a fim de manter o controle das freqüências. Então nós vamos precisar começar com um loop como de costume como chegamos a cada corda ou de alguma forma vamos precisar manter o controle de quantas vezes nós vimos isso. Vamos em frente e usar um objeto para manter o controle dessas cordas e no loop. À medida que processamos cada string, podemos ir em frente e atualizar nosso objeto. Então vamos pensar na primeira corda. Vamos avançar e focar neste exemplo por enquanto, em I é igual
a zero, o primeiro item será ABC. Vamos em frente e criar uma variável para isso. Então esta string vai ser A B, C e R Object está vazio. Vamos querer adicioná-lo às frequências. Objeto. Certo, até
agora, tudo bem. Vamos ver o que acontece se passarmos para a próxima cadeia de novo. ABC nós vamos estar aqui, e esta corda vai ser ABC mais uma vez. Mas agora essa linha de código não está fazendo o que queremos. É redefinir o valor para um que não faz nada por nós. Vamos precisar de alguma forma de verificar se é a primeira vez que o nosso objecto vê esta corda. Se for, temos de lhe dar o valor de um. Caso contrário, de alguma forma precisamos pegar o valor e aumentá-lo em um. Então vamos começar por verificar para ver se é a primeira vez que vimos esta string. E se for, então não estará presente no objeto ainda. Então, se ele ainda não existe no objeto, então verificar se ele deve nos dar indefinido. E se for indefinido, precisamos dar um valor de um. Quem é a primeira vez que vemos a corda? Se, no entanto, já existe, que
significa que já cimentou o seu valor 123 ou o que for necessário para aumentar isso em um . Parece que faz sentido para mim. Vamos em frente e estender nossa matriz de frequências. Desculpe, apenas para ter certeza de que estamos fazendo isso corretamente. E eu vou me livrar desses três por enquanto e apenas trabalhar com esse exemplo para vermos o que esperamos. A.B . C está aqui duas vezes D E F. Três vezes e G H I quatro vezes. Nosso objeto reflete isso corretamente. O que precisamos fazer agora? Bem, de alguma forma
precisamos descobrir qual desses valores é o mais alto. Precisamos saber que quatro é o valor mais alto aqui e que a cadeia correspondente a isso é G H I. Poderíamos fazer algum processamento aqui em baixo. Poderíamos pegar cada valor individual no objeto e, em seguida, encontrar o número mais alto mantendo controle. Mas já temos um loop for. Só podemos fazer isso atualizando uma variável ao longo do loop. Vamos em frente e criar uma variável para armazenar a maior vaidade livre que encontramos
até agora . E vamos inicializá-lo para zero. E também é variável criativa para a string mais frequente, e vamos inicializá-lo para o primeiro item em nossas strings são um em nosso loop. Vamos atualizar isso toda vez que passarmos pelo nosso ciclo. Então eles só precisarão ser atualizados se tivermos uma nova frequência máxima. Vamos verificar se nós dio esta verificação aqui verifica se a nossa nova frequência significa que o valor acabamos de atualizar é maior do que a frequência máxima anterior que tínhamos. Se for, queremos atualizar esse número de freqüência Também queremos atualizar a string mais freqüente porque isso significa que ela é alterada uma vez que passamos por esse loop, essas duas variáveis atualizam repetidamente como precisam de Teoh. No final, a variável de strings
mais freqüentes aqui conterá a rua mais freqüente. Então podemos ir em frente e devolver isso. Vamos adicionar estes de volta e ter certeza de que tudo está funcionando como esperamos, Então, se for, esperamos ver ABC, ABC e G H I. E é isso que obtemos. Parece estar funcionando corretamente. Vamos em frente e falar sobre a complexidade do tempo dessa solução. Temos um loop aqui imediatamente. Traga-nos 20 de fim dentro do circuito. Tudo o que fazemos é fazer algumas verificações e atualizar algumas variáveis, se necessário. Esses não são loops em si mesmos, então eles não vão mudar nossa complexidade de tempo. Então nossa complexidade do tempo final vai ser o de qualquer. E quanto ao espaço? Bem, estamos armazenando cada string que encontramos em nosso objeto de frequências. Se a nossa matriz de strings contém apenas strings únicas, então este objeto de frequências vai conter todos eles. Então, é essencialmente vai ser proporcional ao tamanho de nossas cordas são um significado. Também vai ser oh, de fim. O que podemos tirar deste problema? Bem, este problema essencialmente nos obriga a armazenar uma atualização de dados à medida que passamos por nosso loop. Esta é uma boa técnica para ter em mente. Os problemas geralmente não exigem isso, e uma solução pode ser alcançada sem se manter o controle. Na verdade, mesmo aqui não precisávamos fazer isso. Nós poderíamos apenas comentar isso e comentar isso, e nós poderíamos executar algum significado pós-processamento aqui em baixo. Poderíamos adicionar um pouco mais de código para então descobrir qual valor é o mais alto e, em seguida, qual string que corresponde a. Mas em vez disso, mantemos o controle de tudo enquanto passamos pelo nosso ciclo, então não precisamos fazer nada depois. Em geral, tente ver. Se o armazenamento de dados e de alguma forma criativa pode tornar um algoritmo mais fácil, ele pode ser capaz de reduzir a complexidade do tempo. Mas se não, pelo
menos pode tornar o código mais simples. Veremos no próximo vídeo
10. Rotação de corda: Bem-vindos ao próximo problema. Rotação de string. O objetivo aqui é escrever uma função que levará em duas cordas e determinar se suas rotações um do outro. Agora, qual é a rotação? Estes são exemplos de rotações, então temos a string 1234 Para girá-lo, podemos tirar um caractere do início e colocá-lo no final. Isso nos dá 2341 Nós podemos fazer isso de novo e pegar os dois e movê-lo para o fim, e nós temos 3412 e fazer isso mais uma vez. Mover um três para o fim recebe o seu 4123 Isso é uma rotação aqui. Mais alguns exemplos. Vamos em frente e começar a escrever esta função, então a primeira maneira que podemos descobrir se eles certamente não são rotações é se as cordas têm comprimentos diferentes para duas cordas três rotações de outra uma da outra. Eles têm que ter exatamente o mesmo comprimento. Então vamos em frente e verificar isso. Certo, terminei com isso? - Não. Uma maneira de resolvermos esse problema seria pegar nossa primeira corda e criar cada rotação
possível dela enquanto fazemos isso. Vamos verificar se essas rotações são iguais à segunda corda. Se o fizerem, podemos voltar a verdade. E se passarmos por todas as rotações e não houver nenhuma correspondência do que podemos retornar false, vamos em frente e escrever um loop para fazer isso para nós, e para fazer isso, vamos usar o método string dot fatiado. Este é um método que irá extrair texto de uma string. A maneira de usá-lo é dar aos parâmetros o índice inicial e final que gostaríamos cortar e ele vai cortar entre esses dois índices. Então, por exemplo, cortar isso nos Índices um e oito significa Índice um está bem aqui e o próximo oito está bem aqui e vamos colocar tudo entre esses dois. O que significa que este é o método que usará. Vamos ver o que nesta impressão e vamos em frente e livrar-nos de três destes e concentrar-nos neste. À medida
que me movo da esquerda para a direita,
temos fatias ligeiramente maiores e maiores. À medida
que me movo da esquerda para a direita, Agora vamos tentar outros índices. Vamos tentar cortar. Fizemos desde o início até o índice, e agora vamos tentar no índice até o comprimento das cadeias de caracteres. E o que vemos aqui é uma divisão perfeitamente limpa. O que precisamos fazer para realmente girar esta corda, seu lugar, isso no início. E então nós obteríamos rotação com um R no final. Continuamos fazendo isso e colocando essa corda antes desta, e geramos todas as rotações possíveis. Deixe-me mostrar-lhe o que isso significa. Só precisamos mudar a ordem desses dois e temos cada rotação uma por uma de letras. Tire-o do início e colocado no final. Isso é exatamente o que precisamos fazer agora é verificar. A rotação de rotação F é igual à segunda string. Se for, podemos sair do loop e retornar verdadeiro. E se chegarmos ao fim e nenhum deles corresponder, retornaremos falso. Vamos em frente, livrar-nos disto e ver se funciona. Então esperamos tréguas e duas falsas é, e é isso que temos. Estamos parecendo bem. Vamos falar sobre a complexidade do tempo dessa função. Então nós já temos um loop aqui, trazendo-nos para Ole de Ed desta vez n não é o tamanho da teoria a ou o número de argumentos . Na verdade, vai representar o comprimento das cordas porque isso é praticamente a única coisa que muda. Na verdade, essa é a única coisa que muda que podemos medir. Então nós temos um loop de não final aqui. Vamos inspecionar esta linha esta linha um pouco de perto. Então fatia, acordo com as docas para Indian, é na verdade um loop porque cada personagem tem que ser contaminado um por um. Então acredite ou não, fatia é um O de n operação. E o que temos aqui é um loop dentro de um loop trazendo-nos para, embora de n ao quadrado e espaço. Estamos armazenando uma rotação e essa variável, então a quantidade de caracteres na string que esta variável contém será igual
ao comprimento da string. Então, em outras palavras, a quantidade de espaço que esta variável usa vai ser equivalente à quantidade de espaço que esta string usa. Então isso vai ser linear. Isso é tudo para a solução. Mas há mais um que torna isso muito mais simples para nós. Vou escrever o código e discutiremos imediatamente depois e vamos executá-lo e estamos prontos para ir agora. Vamos pensar por um minuto por que isso está funcionando. Vamos pegar esses dois e colocar a rotação ao lado de si mesmo. Então, em outras palavras, estamos realizando essa ação aqui mesmo. Str wana mais str um E estamos verificando para ver se esta corda assim que o primeiro 1 duplicado tem o 2º 1 em algum lugar nele. Então estamos procurando a existência disso em algum lugar dentro disso e podemos encontrá-lo. Está bem ali. Experimente você mesmo. Mas cada rotação que você pode vir acima com estará presente nesta corda. Isso é praticamente uma lei aqui. Em termos de como essas rotações funcionam, você coloca uma string ao lado de si mesma e ela contém cada rotação da string inicial. A complexidade do tempo desta solução é oh, de n. Tudo o que estamos fazendo é adicionar uma string a si mesmo, que é linear e, em seguida, verificar se inclui o 2º 1 que também é Lanier. Então isso se transformou em oh, off e espaço também é de n porque estamos adicionando esses dois e o comprimento vai ser proporcional exatamente. O dobro do comprimento deste aqui. Isso é tudo para este problema ver o próximo.
Arnav Aggarwal, Full-Stack Engineer & Instructor
