Transcrições
1. Pronto? Defeito. Vamos.: [MÚSICA] Entrevistas de programação
são realmente intimidantes. Existem perguntas difíceis, quebra-cabeças
complicados e até problemas
insolúveis. Há planos de ataque
para cada cenário, mas vamos nos concentrar
no mais óbvio quando a pergunta
for direta. Onde não há bolas
curvas, nem truques. Eu quero ter certeza de que
você aceite a entrevista. Oi. Eu sou Alvin, um cientista pesquisador
na indústria. Na primavera passada,
recebi ofertas da Meta, Apple, Amazon, Tesla e muito mais. Nos últimos anos, também recebi
ofertas de engenharia do Google, NVIDIA, Facebook e Lyft. A experiência que adquiri essas entrevistas foi inestimável. Eu realmente me sentei para
entender quais são todas as peças que fizeram
minhas entrevistas serem bem-sucedidas? Quais são os fundamentos
e os truques? Este curso é um passo
em direções importantes, um avanço na preparação para
uma
entrevista e um avanço no domínio da
codificação. Para realizar as duas coisas,
aprenderemos sobre estruturas de dados. As estruturas de dados são uma forma de
organizar os dados e,
neste curso ,
você verá exemplos de
como eles funcionam e como usá-los. Ao final do curso,
você terá duas habilidades, uma para cada objetivo. Você poderá escolher estruturas de
dados para usar em entrevistas de codificação.
Isso é muito importante. Em vez de inventar algoritmos
eficientes, apenas para algoritmos eficientes
prontos para chamadas. Você também poderá implementar
essas estruturas de dados, combinando e misturando
implementações conforme necessário. Este também
é um. Conhecer as implementações de
forma eficaz fornece o código
inicial da entrevista, uma vantagem gratuita. Espero que você esteja animado. Eu sei que
eu sou. Vamos começar.
2. Por que você precisa de estruturas de dados: Deixe-me explicar por que você precisa de estruturas de dados,
em particular, por que esse curso sobre estruturas de
dados é tão importante para seu
crescimento como programador e como você pode aproveitar
esse curso de forma eficaz. Abordaremos três pontos de
discussão principais: primeiro, discutiremos os benefícios de dominar esse tópico; segundo, discutiremos objetivos específicos de
aprendizado
no curso para acelerar
seu domínio e Em terceiro lugar,
apresentaremos um exercício para ajudá-lo a adquirir domínio
após o término do curso. Aqui está nosso primeiro ponto de discussão, por que você deveria se importar, por que
estou ministrando este curso, os benefícios que você colherá. O maior benefício de fazer esse curso é estar mais
preparado para entrevistas. Existem dois tipos de entrevistas
técnicas: Primeiro, existem questões de codificação, problemas específicos como:
como você inverte uma string? Como você remove todos os números
duplicados? Em segundo lugar, há questões de
design de sistemas. Essas são
questões mais amplas,
como : como você construiria
um clone do Airbnb? Basicamente, como projetar infraestrutura e software
para um produto inteiro. Ambas as entrevistas podem
ser desafiadoras, mas as estruturas de dados ajudam
você tremendamente com essas
duas
entrevistas técnicas, e veja como fazer isso. Aqui estão dois benefícios específicos conhecer as estruturas de dados. benefício número 1 é para sua primeira
entrevista técnica, entrevistas de codificação. Uma parte significativa,
provavelmente mais de um terço das questões de codificação, está
relacionada às estruturas de dados. Se você conhece suas estruturas de
dados, geralmente pode aplicar algoritmos em vez de projetar
em suas entrevistas. Isso é enorme. Não há necessidade de criar
ideias do zero. Se você sabe que a estrutura de dados A
atende exatamente a essas necessidades, basta dizer:
“Eu sei que os HashMaps são
ideais para esse caso de uso; eis por que e como
eu os usaria”. Essa é uma resposta matadora
à entrevista. benefício número 2 é para sua entrevista de design de
sistemas, sendo capaz de otimizar sistemas para sua aplicação
específica, tanto em suas entrevistas
quanto na prática. Não estou
falando de um sistema 10 por cento ou 25 por cento mais rápido, estou falando de um sistema
que opera ordens de magnitude com mais eficiência,
escolhendo o banco de dados,
servidor ou servidor certo infraestrutura sem servidor e muito mais. Você diria: “Precisamos de gráficos acíclicos
direcionados. Os bancos de dados gráficos são otimizados especificamente para esse tipo de
relação, e aqui está o porquê.” Agora, essa é uma decisão de design bem informada e convincente. O benefício número 3 está além
do processo de entrevista. Com uma compreensão
das estruturas de dados, você poderá abordar tópicos
mais avançados
além de suas entrevistas. Na ciência da computação em geral, esses tópicos oferecem novas
habilidades, como criar um jogo. Uma das ferramentas de criação de
jogos mais populares, o Unity, usa o que chamamos de paradigma de
programação orientada a dados. Como o nome sugere, entender suas
estruturas de dados é muito importante. Para resumir, aqui estão três benefícios de
entender as estruturas de dados. Ser capaz de aplicar em vez de projetar do zero
em entrevistas de codificação, ser capaz de otimizar a aplicação em entrevistas de
design de sistemas e ser capaz de abordar tópicos
mais avançados para abrir novas portas além de
apenas entrevistas. Neste curso, vamos nos
concentrar no benefício número 1. Em todas as outras lições, você praticará a aplicação
de estruturas de dados para codificar perguntas de entrevistas. Para obter esses benefícios, você precisará se concentrar em dois objetivos de aprendizado
neste curso. O objetivo número 1 é
saber como cada estrutura de dados funciona e praticar a implementação de
cada estrutura de dados. Isso é fundamental porque, no
futuro, talvez seja necessário
implementar partes
dessas estruturas de dados ou combinar estruturas dados para finalidades
diferentes. Assim como nas minhas outras aulas, eu recomendo fortemente que você
codifique ao meu lado, coloque este vídeo em um lado da tela e seu editor de
código favorito no outro lado. Copie meu código com exatidão
e, não precisa se apressar, pause o vídeo
sempre que precisar. O mais importante é que
você construa a memória muscular. O objetivo número 2 é saber como e quando usar
cada estrutura de dados. Especificamente, lembre-se dos prós e contras de cada estrutura de dados. Na próxima lição, compartilharemos
itens de rubrica específicos pelos quais você avaliará cada estrutura de
dados. Os prós e os contras
não são insossos, são muito precisos
e bem definidos. Resumindo, seus dois principais objetivos de
aprendizado
são saber como as estruturas de
dados
funcionam praticando implementações e
codificação ao meu lado.
Segundo, saber como e quando usar os dados estruturas lembrando os prós e os contras que examinamos. Nosso último
ponto de discussão aqui é como
solidificar sua
compreensão da estrutura de dados além deste curso. Claro, é para praticar, mas na verdade não é
o que você espera. Temos que virar
o jogo, fingir que você é o entrevistador, digamos que você está escrevendo as questões de
estrutura de dados agora. Sua tarefa é
praticar a criação questões de estrutura de
dados e fazer isso diariamente por três dias. O objetivo é fazer você
pensar em estruturas de dados apenas algumas vezes após
uma boa noite de descanso. Faça isso durante o tempo de inatividade,
durante o trajeto, enquanto estiver
escovando os dentes ou enquanto espera na fila. Adicione isso à sua lista de fazer isso
quando eu estiver entediado. Quanto mais você fizer isso, quanto mais perguntas
tiver, melhor
dominará
as estruturas de dados. Para recapitular, discutimos os benefícios de conhecer as estruturas de
dados, melhor prontidão para entrevistas e um trampolim para tópicos
avançados Discutimos seus objetivos de
aprendizado, Saiba como implementar estruturas de
dados e como usar estruturas de dados, finalmente discutimos uma maneira reforçar seu conhecimento, por três dias após o curso, elaborar uma
pergunta de estrutura de dados todos os dias. Eu também encorajo você a
postar sua pergunta
na seção de discussão, minha culpa. Eu realmente quero dizer isso. É incrivelmente gratificante para mim ver as
perguntas que você publica, seja uma pergunta que você fez
ou uma pergunta sobre o curso,
então, por favor, faça o upload.
Estou ansioso por isso. Isso é tudo para a visão geral. Para obter uma cópia desses slides
e de mais recursos, não
deixe de conferir
o site do curso. Terminamos a
visão geral e, a seguir, falaremos sobre como
comparar estruturas de dados.
3. O que é uma estrutura de dados "boa"?: O que é uma boa estrutura de dados? Isso é fundamental para entendermos porque um dos nossos objetivos de
aprendizado é saber como e quando
usar cada estrutura de dados. Mas mesmo antes de
fazermos essa pergunta, precisamos primeiro perguntar o que
é uma estrutura de dados? Podemos começar com uma definição
simples. Uma estrutura de dados é simplesmente
uma coleção de dados. Isso parece simples, então vamos agora expandir um pouco isso. Vamos expandir essa
definição adicionando algumas expectativas para
uma estrutura de dados. Em particular,
devemos ser capazes de
modificar e acessar
os dados contidos. Uma estrutura de dados
é uma coleção de dados que podem ser
modificados e acessados. Para modificar a estrutura de dados, devemos ser capazes de inserir
e remover dados. Para acessar os dados, devemos ser capazes de
pesquisar e buscar dados. Essas são as quatro ações que toda estrutura de dados
deve suportar. Cada uma dessas ações
pode ser muito lenta ou muito rápida,
dependendo da estrutura dos dados. Isso nos leva à
nossa próxima seção, que é como quantificamos
muito rápido ou muito lento? Quão eficiente ou ineficiente
é cada uma dessas ações? Em outras palavras, como
avaliamos a eficiência? Para avaliar a eficiência
de um algoritmo, contaremos o número de operações que um algoritmo
precisa para executar. Por exemplo,
digamos que temos essa lista de frutas e estamos
procurando por abacate. Para pesquisar a lista, precisamos percorrer
a lista uma a uma
até encontrarmos o item que
estamos procurando. Nesse caso, fizemos três “operações” para
procurar abacate. No entanto, se
o abacate estiver no final ou se não estiver
na lista, seu algoritmo de busca
teria que
percorrer todos os
itens da lista. Para uma lista com n itens, pesquisar um valor na lista
leva até n operações. Agora, a definição de
operação é vaga. Talvez o acesso à memória
seja uma operação, talvez verificar a igualdade de cadeias de caracteres
seja outra operação. Digamos que o número
de operações necessárias para um único item seja c. Em seguida, a pesquisa
leva as operações cn. No entanto, essa constante c
não é interessante para nós quando
comparamos algoritmos. Simplesmente dizemos que o
algoritmo usa operações O de n em que a
notação O oculta todas as constantes. Chamamos isso de estatística O de n, tempo de execução ou complexidade
computacional. Aqui está outra maneira de ver o
que significa O de n complexidade. O que sabemos é que,
à medida que a lista fica mais longa, o número de operações, seja qual
for a contagem, aumenta linearmente. Isso significa que a complexidade
computacional de nossos algoritmos pode ser limitada acima e abaixo
por funções lineares. Qualquer algoritmo cuja
complexidade esteja dentro desses limites é O
de n. Como resultado, pesquisar sua lista tem complexidade computacional O de n. Agora sabemos que para uma lista, que também é chamada de matriz, usa O de n vezes uma pesquisa. Para ser mais específico,
buscamos um valor quando não sabemos onde um
determinado valor está na lista. No entanto, digamos que queremos buscar exatamente o item i. Sabemos que queremos o item i e não precisamos
pesquisar um valor. Essa busca leva
tempo constante ou O de um, porque simplesmente
acessamos o item i
da lista sem
olhar para outros valores. Mais especificamente, à medida que
o tamanho da lista aumenta, o esforço necessário para buscar
um item não muda. Isso é ótimo. Buscar
um item é barato. Para maximizar a eficiência, isso significa que devemos
usar uma matriz quando precisamos
buscar mais dados com
mais frequência do que buscamos dados. Esse é um exemplo de
uma lição prática, e veremos muitas
delas no curso. Cada uma dessas decisões visa
maximizar a eficiência. Devemos alterar nossa definição
de estrutura de dados. Uma estrutura de dados é
uma coleção de dados que podem ser
modificados e acessados com eficiência. Com base em cada aplicativo, precisaremos escolher estruturas de
dados para garantir essa eficiência. Analisaremos a complexidade de algumas estruturas de dados
neste curso. Ao realizarmos essas análises, encontraremos várias ordens
comuns de crescimento. As ordens de crescimento são o resultado de algo que
vimos anteriormente. Já vimos dois exemplos de
ordens de crescimento. Crescimento em tempo constante O de um
e crescimento linear O de n. Essas são seis ordens comuns de crescimento mostradas
aqui neste slide. Mas para as estruturas de dados
e algoritmos que estamos abordando, veremos apenas
quatro ordens de crescimento, constante O de um, logarítmico de log n, linear O de n e O de n ao quadrado. Veremos a
aparência de O do log n mais tarde, mas, por enquanto, lembre-se de que você tem
uma nova ferramenta para analisar a complexidade
algorítmica
e que essas quatro são as
ordens de crescimento mais comuns que você encontrará. Para obter uma cópia desses slides
e de mais recursos, não
deixe de conferir
o site do curso. Agora, você tem uma nova ferramenta e ordens
de análise de crescimento, que permitem avaliar a complexidade
computacional de qualquer algoritmo. Mais importante ainda, ele
permite que você escolha estruturas de
dados para
diferentes aplicativos com base na lentidão ou
rapidez com que uma estrutura de dados
é para inserção, exclusão, busca
e pesquisa. Na próxima seção,
praticaremos análise de ordens de crescimento.
4. Ordens de prática de crescimento: Bem-vindo a algumas práticas de
estruturas de dados. Nesta lição, avaliaremos
as estruturas de dados. Em outras palavras,
avaliaremos algoritmos e estruturas de
dados usando um sistema
chamado ordens de crescimento. isso que falamos
na lição anterior. A notação Big O nos
dirá a rapidez ou lentidão com que um algoritmo leva para
ser executado com base em seu tamanho de entrada. Vamos deixar de lado as
táticas de entrevista por enquanto, pelo
menos as táticas
específicas da entrevista. Certamente teremos dicas relacionadas a
entrevistas, mas precisamos nos concentrar primeiro
nos fundamentos. Comece navegando
até esse URL, alvinwan.com/data
structures101/oog. Depois de ver esta página, bifurque o projeto para obter
sua própria cópia editável. Para fazer isso, clique no nome
do projeto no
canto superior esquerdo para abrir uma lista suspensa. Em seguida, clique nas reticências
no canto superior direito para obter
outra lista suspensa. Por fim, clique
no botão “Fork”. Então, sugiro colocar
suas janelas Skillshare e Repl.it
lado a lado, conforme mostrado aqui. Você deve então
ver uma janela
igual à minha no lado
direito. Antes de realmente nos
aprofundarmos nos problemas, vamos analisar as ordens de crescimento
sobre as quais falamos anteriormente. Existem quatro
ordens relevantes de crescimento. Como lembrete, o que estou escrevendo
aqui é uma função de n, onde n é o
tamanho da entrada. Essas ordens de crescimento
nos dirão quanto mais lenta
a função será executada se aumentarmos o tamanho da
entrada n. Como resultado, queremos que os tempos de execução cresçam mais
lentamente à medida que a entrada
aumenta em tamanho. bom subir nessa lista
de tempos de execução. Quanto mais lenta a ordem de crescimento, mais eficiente e preferencial é o algoritmo
ou a estrutura de dados. Uma dica que tenho para você é
conhecer esses tempos de execução de cor, esses são os quatro principais tempos de execução que você precisa saber para
cada entrevista. O primeiro O (1)
ou tempo constante significa que, independentemente
do tamanho da entrada, nossa função sempre leva
a mesma quantidade de tempo. Em segundo lugar, O (login)
realmente falará sobre isso mais tarde. Esse é um
tempo de execução
um pouco mais complicado de explicar. O terceiro, O (n), ou tempo de execução linear, significa que,
se nosso tamanho de entrada dobrar, nosso tempo de execução também dobra. Se nosso tamanho de entrada triplicar,
nosso tempo de execução também triplica. Em outras palavras, o
tempo de execução da nossa função realmente cresce linearmente em relação a n. O (n) ao quadrado aqui
significa quadrático. Se dobrarmos o tamanho da entrada
, nosso tempo de execução da função quadruplica ou o
tempo de execução do algoritmo quadruplica. Se nosso tamanho de entrada triplicar, nosso tempo de execução realmente
aumentará nove vezes, e assim por diante. Agora vamos mergulhar
direto nos exercícios. No lado direito aqui, eu tenho nosso primeiro exercício. Qual é a
complexidade do tempo de execução para o seguinte? Aqui temos apenas um
loop for para i no intervalo n. Lembre-se de que o intervalo
de n fornece um editável de n itens
diferentes. Qual é a
complexidade do tempo de execução dessa função? Pause o vídeo aqui e
experimente . Aqui está a resposta. Essa função novamente
itera uma vez sobre cada item neste
iterável de n itens. Em outras palavras, ele itera
uma vez para cada n itens, ele iterará n vezes. O tempo de execução dessa função
ou desse algoritmo é O (n). [Risos] Eu esqueci de te mostrar. Aqui está a lista
de quatro opções diferentes de
tempo de execução que você tem. Vou mantê-los aqui enquanto
realizamos esses exercícios. Agora vamos passar para
o segundo exercício. Qual é a complexidade
de tempo de execução dessa função, novamente, função de n. Aqui
temos dois, para loops. Cada um deles
itera até n. Outra forma de ver
isso seria
perguntar quantas vezes a função de
impressão foi chamada? Pause o vídeo aqui e
tente e aqui está a resposta. Aqui, iteramos sobre isso n vezes. Então, para cada i, também
iteramos mais de j n vezes. Isso faz um total
de n vezes n corridas. Esse algoritmo é O (n) ao quadrado. Vamos passar para
o próximo exercício. Qual é a
complexidade de tempo de execução dessa função
em função de n? Aqui começamos com n.
Então, nesse loop while, para cada etapa,
teremos esse valor. Qual é a
complexidade do tempo de execução dessa função? Você pode usar um processo
de eliminação para descobrir qual é o tempo de execução. Pause o vídeo aqui e
experimente, e aqui está a resposta. A resposta para essa função, que podemos deduzir
pelo processo de eliminação, é O (logn). Veja como esse processo de
eliminação pode funcionar. Aqui vemos que a função definitivamente não
é constante. Definitivamente, demora um pouco
mais sempre que n aumenta. Definitivamente não é O (1). No entanto, não é
tão lento quanto O (n), porque O (n) iteraria uma vez. Ele iteraria sobre todos
os itens, um por um, até n. No entanto, não
fazemos isso. Metade do valor
todas as vezes. Estamos apenas
pulando um pouco. Não é tão lento quanto O (n) e não é tão rápido quanto O (1). O único tempo de execução
intermediário é O (log n). Faremos isso
com mais precisão mais tarde para explicar como o (logn) surge. Mas, por enquanto, vamos falar
sobre uma explicação visual. Qual é a aparência
do crescimento logarítmico e o que significa
ter crescimento logarítmico? crescimento logarítmico é
muito lento. Para ter uma ideia de quão lenta, considere a função de log. Lembre-se de que n é o tamanho da entrada, o valor do log
n é o tempo de execução. Digamos que nossa entrada tenha tamanho dois, então o tempo de execução tem o tempo de execução
da unidade um. Digamos que nossa entrada
dobre o tamanho quatro, o tempo de execução aumente em um. Se nossa entrada dobrar
novamente para o tamanho oito, o tempo de execução aumentará em um. Finalmente, se sua entrada
dobrar novamente para o tamanho 16, o tempo de execução ainda
aumentará apenas em um. Observe que nosso
tamanho de entrada precisa continuar dobrando para aumentar
o tempo de execução em um. Isso significa que nosso algoritmo
é bastante eficiente. Visualmente, aqui está o
que parece. Traçamos o tamanho da entrada
ao longo do eixo x, traçamos o tempo de execução
ao longo do eixo y
e, em seguida, traçamos todos os
pontos anteriores. Observe que nossa função
cresce muito lentamente. Na verdade, aqui está um
gráfico maior com mais valores de x. Você pode ver que nosso gráfico
se torna plano muito rapidamente. Em outras palavras, as
funções logarítmicas crescem muito lentamente. Tenha isso em mente. Vamos voltar à nossa função. Agora podemos ver que aqui isso, ou i ou n, digamos que n precise dobrar
para aumentar o número de iterações de loop
while em para aumentar o número de iterações de um. Se n for dois, o loop while itera uma vez. Se n for quatro, isso itera duas vezes. Se n for oito, isso itera três vezes, e assim por diante. Esse valor n precisa
dobrar a cada vez para aumentar o
tempo de execução em apenas uma. Isso é crescimento logarítmico. A outra maneira de
ver isso é que nossa função logarítmica reduz pela metade o tamanho da entrada em cada etapa. Como você pode ver aqui, reduzimos pela metade em cada etapa, então estamos reduzindo pela metade nossa carga de trabalho cada etapa.
Essa é a dica. As funções logarítmicas reduzem
pela metade o tamanho da entrada em cada etapa. Aqui está um resumo
dos três exemplos que
acabamos de analisar e
seus tempos de execução. Isso é tudo para os
“exemplos básicos”. Não quero dizer básico, pois são fáceis. Esses exemplos são
muito confusos, especialmente quando você os
vê pela primeira vez. Eu digo básico para significar que
todos os outros exemplos
serão alguma modificação
dessa estrutura básica. Para descobrir os tempos de execução
no futuro, há duas etapas. Primeiro, comece memorizando a aparência desses “
exemplos básicos”. Segundo, depois de
conhecer esses exemplos, você poderá memorizar as diferentes
modificações possíveis. Essa é a nossa dica. Agora vamos passar para
essas modificações, esses exemplos complicados. Essas são novamente modificações
dos exemplos acima para parecerem confusas
ou para alterar o tempo de execução. Aqui estão os quatro
tempos de execução anteriores. Vamos agora passar para os
exemplos, os exemplos complicados. Quantas vezes a impressão é chamada
na função a seguir? Aqui temos um loop for aninhado. Então temos essa condição if, se i é igual a j. Observe essa afirmação if e como ela
afeta a
complexidade, se é que afeta? Pause o vídeo aqui e
tente novamente, quantas vezes a impressão é chamada? Aqui está a resposta.
A impressão só é chamada n vezes. Isso ocorre porque nosso loop
for interno só é executado uma vez. Se i for igual a zero, então essa condição se passar
somente se j
também for igual a zero. Se i for igual a um, novamente, essa condição se passar somente
se j também for igual a um. Isso significa que para
cada loop externo,
o loop interno é executado apenas uma vez, então isso é n vezes
uma iteração, isso é um total de O (n). Vamos agora passar para o nosso
próximo exemplo complicado. Quantas vezes a impressão é
chamada em função de n? Aqui temos um loop for aninhado,
mas observe que o
loop for interno só conta até i. Novamente, como isso afeta o tempo de execução, se é que isso
afeta o tempo de execução? Pause o vídeo aqui
e experimente. Aqui está agora a resposta. Ao que parece, mesmo que estejamos apenas iterando até i, parece que podemos ter
uma complexidade de tempo de execução mais rápida. Acontece que não temos. Isso ainda é O (n) ao quadrado. Aqui está o motivo. Vou ter que explicar
mostrando uma foto. Aqui, digamos que temos um loop for
normal
no lado esquerdo. Então, para cada valor
único de i, passamos por j n vezes. Faremos isso porque
i é igual a um, iteramos
todos os valores de j, i é igual a dois, todos os valores de j e assim por
diante. Continue fazendo isso. O que isso significa é que há um total de n
vezes ao quadrado diferentes que imprimimos. Digamos que imprimimos i j. Agora, digamos que
temos esse novo loop for onde
só iteramos até i. Então o que isso significa é
aqui na primeira linha, quando i é igual a um, nós Só execute j uma vez. Quando i é igual a dois
na segunda linha, executamos j apenas duas vezes. Quando i é igual a três, executamos j apenas três vezes, e assim por diante. Aqui, em vez de n ao quadrado total de vezes
que chamamos de impressão, temos 1/2 vezes n vezes
ao quadrado que chamamos de impressão. No entanto, 1/2 de n ao quadrado ainda está na
ordem de n ao quadrado, é por isso
que essa
função ainda é O de n ao quadrado em complexidade
algorítmica. Isso conclui esse exemplo
complicado. Se você tiver alguma dúvida ou
ainda estiver confuso, sinta-se à vontade para deixar uma pergunta
na seção de discussão. Esses são os quatro
tópicos diferentes que abordamos. Ordens de crescimento, recuperamos
alguns exemplos fundamentais, crescimento
logarítmico e alguns exemplos complicados,
além de como eles modificaram esses exemplos básicos
para um exemplo mais complicado. Para obter uma cópia desses slides e o código
finalizado desta lição, não
deixe de conferir
o site do curso. Isso conclui esta lição para
avaliar estruturas de dados.
5. Sequências: pilha x fila: Um formato comum para
dados é uma sequência
e, em particular, há dois tipos comuns de sequências. Há pilhas, como uma pilha de roupas ou uma pilha de pedras. Também há filas, como uma fila de pessoas ou
um túnel de carros. Depois de analisarmos
as pilhas e as filas, discutiremos
seus prós e contras. A primeira é uma pilha. Assim como com uma pilha de pedras, você adiciona itens ao
topo da pilha. Em seguida, para remover uma
pedra ou um item, você também
o remove do topo da pilha. Resumimos isso como último a entrar, primeiro a sair; o último item que você adiciona é o primeiro que você remove. A
operação de inserção de acordo com essa lógica é simples então. Pegamos o valor que queremos agregar, colocamos esse valor
na pilha e pronto. É preciso uma constante ou O
de uma vez para inserir um novo valor na pilha pois não importa
o tamanho da pilha, o esforço de simplesmente inserir
um item é o mesmo. Observe que, por definição, só
podemos inserir valores
no topo da pilha. A operação de exclusão também
é simples. Pegamos o último
valor mostrado aqui em cinza e adicionamos o valor. Isso também requer constante ou
O de uma vez. Como o tamanho da
lista não altera o número de operações, a exclusão é reduzida. Juntos,
agora sabemos que as pilhas apresentam
inserção e exclusão em tempo constante,
portanto, a modificação é barata. Mas e quanto ao acesso? Quanto custa pesquisar um valor
na pilha? Infelizmente, muito lento. Digamos que estamos
procurando o valor 8. Nós colocamos um item e verificamos seu valor. 7 é igual a oito? Não é, então adicionamos
outro valor verificamos seu valor. 2 é igual a 8? Não é assim que estouramos
mais uma vez e depois verificamos seu valor. 8 é igual a? Com certeza é, então nossa busca está completa. No entanto, se houver
n itens na pilha, precisamos realizar
até n verificações. Isso significa que a pesquisa leva
linear ou O de n tempo. busca de um
item específico é semelhante. Digamos que queremos buscar o
segundo item com o valor 8. Estouramos um item, esse é um item, estouramos outro item, são dois itens, depois estouramos outro item,
são três itens. Finalmente buscamos
o valor que queremos. Como antes, se houver
n itens na pilha, podemos precisar de até n pops. Isso faz com que a busca seja O de n a tempo. Para resumir, podemos inserir
e excluir de uma pilha
em tempo constante. modificação é
eficiente. No entanto, pesquisa e a busca
levam um tempo linear. O acesso é ineficiente. Mas e se, em vez
de uma pilha de pedras, tivéssemos uma fila de pessoas? A primeira pessoa
a entrar na linha deve ser a primeira a sair dela. Isso é chamado de fila. Dessa vez, inserimos um valor
no final da fila e excluímos um valor da
frente da fila. Chamamos isso de sequência de primeiro a entrar, primeiro a sair ou fila. Como mencionamos anteriormente,
a inserção é simples. Consideramos um valor a ser adicionado
e, em seguida, colocamos esse
item na fila. Independentemente do
tamanho da lista, a simplicidade de
inserção não é afetada. Este é o O de uma operação. exclusão é semelhante. Consideramos um valor a ser
removido mostrado em cinza e, em
seguida, desenfileiramos esse
valor da fila. Isso também é o O
de uma operação. Resumindo, a inserção
e a exclusão de uma fila são, portanto,
O de uma vez. Mais uma vez, a pesquisa é
bastante lenta, no entanto. Digamos que estamos pesquisando na fila
pelo valor 8, novamente,
desenfileiramos e, em seguida, verificamos se 7
é igual a 8? Não é assim que retiramos a fila
novamente e depois verificamos. 2 é igual a 8? Não é. Nós retiramos a fila e verificamos. 8 é igual a 8? É isso. Nossa busca está concluída. No entanto, se houver
n itens na fila, podemos precisar de até n verificações. Isso torna a pesquisa e
as filas um algoritmo O de n. Fetch é novamente semelhante. Digamos que pretendemos buscar o
terceiro item com o valor 8. Descolocamos um item na fila, seja, 1, desenfileiramos
outro item, seja, 2, e descolocamos
outro item na fila para finalmente recuperar o valor do
terceiro item, que é oito. Para uma fila com n itens, precisamos de n defilas, então a busca é O de
n. Para resumir, uma fila é eficiente para modificar, mas ineficiente para acessar,
assim como acontece com pilhas. Vamos agora analisar os prós e os
contras das pilhas e filas. Na extremidade esquerda, temos as quatro operações que nos
interessam: inserção, exclusão, busca
e busca. Na 2ª coluna, temos
os tempos de execução de uma pilha
e, na 3ª coluna, temos os tempos de execução
de uma fila. Infelizmente, os
tempos de execução em si não são muito interessantes
, então precisamos saber quais usar com
base no aplicativo e como cada
estrutura de dados foi definida. Por exemplo, uma
pilha é ideal para rastrear alterações, como
desfazer uma operação e refazer essa operação. Isso é uma pilha, pois a última alteração adicionada
é a primeira que você desfaz. Uma fila é ideal para processamento
sequencial, como
processamento de carros em uma fila em uma ponte de pedágio ou
solicitações de download em um servidor. Lembre-se desse slide, pois ele resume toda a lição. Para obter uma cópia desses slides
e de mais recursos, não
deixe de conferir
o site do curso. Agora vamos ver essas
estruturas de dados em ação. Na próxima lição, praticaremos o uso
e a implementação dessas estruturas de
dados, abordando nossos dois
objetivos de aprendizado para este curso.
6. Prática de sequências: Bem-vindo a outra aula
prática. Nesta lição,
abordaremos sequências, em outras palavras,
pilhas e filas. Assim como antes, deixaremos lado as táticas básicas de
entrevista, precisamos dominar esses
fundamentos primeiro. Observe que essas perguntas
são bem difíceis. Este não é um aplicativo interessante. Esses são os fundamentos
que você precisaria para entrevistas e é um material tecnicamente
desafiador. Então, assim como antes, navegue
até esse URL,
alvinwan.com/datastructures101/sequences. Depois de ver esta página, bifurque o projeto para obter
sua própria cópia editável. Para fazer isso, clique
no nome do projeto no canto superior esquerdo para
obter uma lista suspensa, clique nas reticências para
obter outra lista suspensa
e, finalmente, clique
no botão Fork. Então, sugiro colocar
suas janelas de
edição do Skillshare e do Replit lado a lado
, conforme mostrado aqui. Falaremos sobre palmeiras em
três categorias diferentes. Primeiro, falaremos sobre os problemas de
implementação. Esses são problemas
que implementam funcionalidade
principal
de uma estrutura de dados. O segundo é o uso, implementaremos
algumas funcionalidades e escolheremos a estrutura de
dados correta para usar, essa é a parte fundamental. Vamos aprender como escolher
as estruturas de dados com
base em seus prós e contras. Para o terceiro, vamos combinar estruturas de
dados em possivelmente uma nova estrutura de
dados ou um novo aplicativo que
exige que combinemos várias estruturas de dados para
cada um de seus pontos fortes. Independentemente da
categoria de problemas, aqui está uma dica profissional que você
deve sempre ter em mente. Na verdade, vamos
seguir essa dica profissional durante toda a aula e todas as
aulas práticas que se seguem. Vamos conduzir todas as
nossas
questões de resolução de quebra-cabeças dessa forma. Você também deve conduzir todas as suas entrevistas
para resolver quebra-cabeças dessa maneira. Primeiro, projetaremos o
algoritmo sem codificação. Crie
o algoritmo verbal ou visualmente com
seu entrevistador. Isso é para que seu
entrevistador possa orientar você e seu pensamento na
direção da resposta certa. Em segundo lugar, relate o tempo de execução e a complexidade da memória.
Isso é importante. Primeiro para demonstrar
compreensão, mas também para ver se
seu entrevistador quer uma solução mais eficiente. Terceiro, e finalmente,
então você codifica. Vamos estruturar sua
prática dessa forma. Projete o algoritmo, depois examinarei a solução, relatarei a complexidade, depois examinarei a solução,
relatarei a complexidade, depois
examinarei a solução
e, finalmente, codificarei o algoritmo
e, novamente,
examinaremos a solução. A ideia é que,
mesmo que você
estrague qualquer parte desse processo de
três etapas, você ainda poderá
praticar as outras etapas. Aqui está nossa primeira pergunta. Vamos implementar
filas, mas usando pilhas. Mas antes de começar, deixe-me falar sobre uma dica. Lembre-se de que uma pilha
é a última a entrar, a primeira a sair. O que isso significa é que é como uma pilha de pedras ou
uma pilha de caixas. O último item que você colocar
nessa pilha será o primeiro
a ser
retirado, ou seja, empilhar. Agora, a fila é como
uma fila, digamos, uma fila de carros. Isso significa primeiro a entrar, primeiro a sair. Portanto, o primeiro carro
alinhado é o primeiro carro que sairá dessa
fila. Tenha isso em mente. o que eu escrevi aqui, uma fila é primeiro a entrar, primeiro a sair, uma pilha é o último a sair, o primeiro a entrar. Agora, claro, nunca me
lembro desse primeiro a entrar, primeiro a sair, último a sair, primeiro a entrar. Em vez disso, o que me lembro é que estou trabalhando com a
pilha, como uma pilha de pedras, pilha de roupas,
pilha de caixas, e então eu penso em uma
fila como apenas uma linha. Se você tiver isso em
mente, isso vai começar a dizer em que direção
você está se movendo. Novamente, o
exercício aqui é
implementar uma fila usando pilhas. Se você rolar para baixo
em seu ripl.it, você verá isso aqui. Isso é o que você
precisa implementar. Então, pause o vídeo
aqui e, primeiro, pense no algoritmo. Como você vai fazer isso conceitualmente? Então, experimente. Aqui está a resposta. Então,
vamos fazer o seguinte. Digamos que temos essa
lista aqui em preto. Temos 9, 8, 2, 7. Nove é nosso primeiro item. Nosso último item é sete. Para emular uma fila, precisamos remover
o primeiro item, que é nove, com aquela seta
vermelha ali mesmo. Nosso objetivo, mostrado aqui em vermelho,
é remover o valor nove e devolver ou manter a pilha
restante, 8, 2, 7. Então, sabendo que esse é
o nosso objetivo, a única coisa
que podemos fazer com uma pilha é remover do último item. Só podemos estourar sete. Bem, está tudo bem.
Podemos continuar fazendo isso. Vamos estourar sete, vamos estourar dois, vamos estourar oito e,
finalmente, vamos estourar nove. Lá vamos nós.
Agora podemos devolver nove. Agora podemos tirar a fila de uma pilha. No entanto, perdemos todos os itens que foram
retirados anteriormente, todos os 8, 2 e 7. Então, precisamos de outra pilha
para guardar todos eles. Então, aqui o que vamos
fazer é colocar sete, mas empurrá-lo para
a outra pilha. Então vamos tirar dois, oito e, finalmente,
retornaremos nove. Isso é ótimo. Estamos
quase lá. No entanto, precisamos de 8, 2, 7 em nossa pilha. Agora temos
o reverso 7, 2, 8. Então, o que vamos
fazer é sair
da segunda pilha e empurrá-la volta para a pilha original. Então, vamos
empurrar isso para trás, e lá vamos nós. Temos os dois objetivos. Podemos retornar
nove como se fosse uma fila e podemos
manter a pilha restante de 8,
2, 7 como queríamos. Agora, isso parece
uma solução inteligente. Eu provavelmente diria para mim mesmo jeito
nenhum eu posso encontrar
essa solução. Se você está pensando
a mesma coisa, estou completamente com você e estou aqui para lhe dizer
que isso não é um problema. Na verdade, não há necessidade de
encontrar essa solução. Em vez disso, entenda
bem. Em suas entrevistas
ou nos empregos, basta relembrar as táticas
disponíveis para você. Então, realmente concentre
sua energia mental em entender a solução. Se algo não fizer sentido, basta perguntar na seção de
discussão. Sabendo que esse
é o algoritmo, vamos passar para
a segunda etapa. Qual é a
complexidade algorítmica? Qual é a complexidade do tempo de execução e qual é a complexidade da
memória? Pause o vídeo aqui
e tente
descobrir . Aqui está a resposta. A
complexidade algorítmica ou de tempo de execução aqui é O (n). Temos que
realizar basicamente duas operações n, que é o tempo O (n). Precisamos colocar
cada item na segunda pilha
e, em seguida, colocar
cada item da segunda pilha de volta na primeira. Então isso é O (n) para complexidade de
tempo de execução, para complexidade de memória, também
é O (n) simplesmente porque tivemos que
manter essa outra pilha, e essa outra pilha exigia
até n itens diferentes. Portanto, temos a complexidade do
tempo de execução O (n) , a complexidade da memória
O (n). Agora, vamos tentar
implementar isso em código. Novamente, pause o vídeo aqui
e experimente você mesmo primeiro. Agora, vamos implementar
essa solução. Começaremos
escrevendo um construtor. Esse construtor
aceitará um iterável. Então, aqui podemos ver que esse construtor
usa um iterável, que é uma lista
de apenas um item. A partir do iterável,
construiremos uma pilha. [RUÍDO] Agora, para colocar na fila, [RUÍDO], vamos simplesmente empurrar
para a pilha. [RUÍDO] No entanto, eu quero desenfileirar
ou remover da pilha, é aí
que entra a lógica
especial. Esse é todo o
algoritmo sobre o
qual falamos aqui
no lado esquerdo. Vamos
começar esvaziando a pilha original
em uma nova pilha. Aqui teremos a nova pilha. Então, enquanto tivermos
itens na pilha antiga, os
empurraremos para a nova pilha e os moveremos
da antiga. Agora que temos
todos esses itens lançados, agora
vamos finalmente
retirar o último item. Isso nos dará o valor que precisamos realmente retornar. Agora vamos esvaziar a nova pilha volta para a pilha original. Lembre-se de que essa foi a última etapa aqui em que tínhamos
tudo ao contrário. Precisamos colocá-los todos de
volta na pilha original. Agora, aqui teremos, enquanto a pilha tiver itens, empurraremos de volta para
a pilha original. Finalmente,
retornaremos o valor. Aqui vamos nós. Implementamos nosso algoritmo
de três etapas de antes. Vamos agora verificar se
essa função passa ou não em
nossos doctests. Para fazer isso, clique em Executar, o botão verde na
parte superior do seu arquivo. Aqui podemos ver que tivemos falhas em todas as outras
funções, mas não nesta. Lembre-se de que nossa função
aqui é fila via pilha, que está ausente nesta lista. Estamos prontos para ir. Passamos nossos testes de documentos para essa função. Vamos agora para
a próxima pergunta. Em nossa próxima pergunta,
faremos o contrário. Vamos implementar
uma pilha usando filas. Novamente, aqui implementamos
uma fila usando pilhas. Agora, em nosso próximo problema, vamos fazer o contrário. Passe
um segundo para pausar o vídeo e considere qual algoritmo você
criaria para fazer isso. Aqui está uma solução. Isso é muito parecido com
o último problema. Assim como antes, vamos instanciar
uma segunda fila. Em seguida,
pegaremos todos os itens da nossa primeira fila e os
colocaremos na segunda fila. Quando chegarmos ao último item, retornaremos esse
item da lista exatamente como uma pilha faria. É basicamente isso. Agora
que temos o algoritmo, vamos
pensar na complexidade da memória
e do tempo de execução
do algoritmo. Pause o vídeo novamente. Agora, aqui está uma solução
conceitual. Aqui queremos implementar
uma pilha, no entanto, temos apenas uma fila. Lembre-se de que uma fila
só pode ser desenfileirada desde o início, enquanto que,
para emular uma pilha, precisamos ser
capazes de sair do final. Temos esse dilema,
mas vamos resolvê-lo da mesma forma ou
da mesma
forma que fizemos antes. Vamos criar uma segunda fila. Em seguida, desenfileiraremos nove e colocaremos
na segunda fila. Em seguida, desenfileiraremos oito
e adicionaremos uma segunda fila, depois desenfileiraremos duas e adicionaremos à segunda fila. Finalmente, vamos retirar
sete da fila e devolvê-la. Aqui, conseguimos
realmente “estourar sete”. Aqui está algo
novo, diferente de antes nossa segunda fila já está
na ordem correta. Lembre-se de que
antes nossa fila era 9, 8, 2, 7 e agora é 9, 8, 2. Este é o pedido exato e
correto. Não precisamos movê-lo de volta para
a fila original,
como fizemos antes. Sabendo que agora podemos saber exatamente como vamos
implementar esse algoritmo. No entanto, antes de fazermos isso, vamos relatar o tempo de execução e a complexidade
da memória da função. Pause o vídeo aqui e
tente descobrir. Agora, aqui está a solução. O tempo de execução e a complexidade da
memória são o de n, assim como antes. Para a complexidade do tempo de execução,
temos que desenfileirar cada item da lista e enfileirá-lo
na segunda fila, então é o de n. Agora,
para a complexidade da memória, precisamos manter
a segunda fila. segunda fila consiste
basicamente descarregar na memória até n itens.
Aí está. Tanto o tempo de execução quanto a
complexidade da memória são iguais a n. Agora, vamos finalmente passar
para a terceira etapa. Vamos tentar codificar esse algoritmo. Pause o vídeo aqui
e tente codificá-lo. Agora, vamos
falar sobre a solução. Vamos implementar a
pilha usando filas. Assim como antes, criaremos
um construtor. Esse construtor precisará
de um iterável. Esse iterável será o valor inicial de nossas
filas. Em seguida, vamos implementar o
push para essa pilha. Isso será apenas uma chamada de
fila e fila. Toda a mágica agora
acontecerá no método pop. Nesse método pop, primeiro
esvaziaremos n menos um item na
fila original na nova fila. Para fazer isso, vamos
criar uma fila. Essa é a nossa nova fila. Então, embora nossa fila antiga
tenha pelo menos um item, continuaremos
removendo dela. Aqui, na verdade,
ele será retirado da fila antiga e o
adicionará à nova fila. Agora que colocamos
quase todos eles na fila, vamos agora retirar o último
item da fila antiga. Opa, então isso é
fila, desenfileiramento. Esse último item
seria sete, por exemplo. Em seguida, retornaríamos esse valor. Assim como dissemos antes, nossa nova fila tem todos os elementos de que
precisamos na ordem certa. Simplesmente substituiremos nossa fila
antiga pela nova. Agora podemos retornar um valor. Vamos
tentar executar todos os nossos testes e ver o que
acontece. Lá vamos nós. Podemos ver que nossa pilha via fila não está
mais na lista de falhas. Tada,
passamos nesses testes. Vamos agora passar para
o próximo problema. No próximo problema, vamos
usar uma estrutura de dados. Eu não vou
te dizer qual deles usar, e caberá a
você decidir qual deles. Vamos usar pilhas ou filas. Em particular, para imprimir todas as combinações das letras
a e b. Vamos
imprimir todas as combinações de comprimento k. Aqui está um exemplo, print_baba de 2 nos
dará aa, ab, bb. Agora, se chamarmos print baba de 3
, isso nos dará todas as “palavras” de
três letras que
têm as letras a e b. Novamente, são todas as combinações
possíveis. Observe que não
há repetições. Observe que cada
valor aqui tem comprimento três. Sabendo disso, vamos passar
novamente processo de três etapas sobre o qual
falamos anteriormente. Na primeira etapa, vamos
criar o algoritmo. Pause o vídeo aqui e
tente criar o algoritmo. Novamente, você vai querer usar
uma pilha ou uma fila. Agora, vamos falar sobre a
solução conceitualmente. Aqui nesta solução
específica, vamos usar uma fila. Vou indicar
a fila usando apenas uma lista básica aqui primeiro para visualizar
o que está acontecendo. Para começar, digamos que eu
tenha a letra a aqui. O que vamos fazer é
primeiro desenfileirar a letra a. Agora temos a e
vamos colocar na fila as duas únicas maneiras possíveis de estender
a letra a. Para partir de uma sequência de uma letra
de todos os possíveis a's e b é para todas as
sequências possíveis de duas letras de a e b. Vamos adicionar aa e ab. Isso explicará
todas as formas possíveis de
criar uma sequência a e b
a partir desse ponto de partida. Agora podemos tornar isso um
pouco mais extenso. Vamos começar
com a sequência vazia. Em seguida, vamos
desenfileirar essa sequência vazia. Em seguida, adicionaremos as
duas únicas formas possíveis
de estender isso, que são adicionar um a
no final ou adicionar
um b no final. Em seguida, vamos desenfileirar e, em seguida,
adicionaremos a mais a mais b, então aa ab. Então faremos
isso de novo. Vamos desenfileirar o primeiro item
aqui, que será b. Em seguida, estenderemos
com ba e bb. Vamos continuar fazendo isso. Agora, aqui teremos
aa, desenfileiramos
e, em seguida, adicionaremos
aa mais aa mais b, então aaa, aab. Vamos continuar fazendo isso. Ao parar no momento
certo, garantiremos que realmente
cobrimos todas as
sequências possíveis de comprimento k de A e B. Sabendo que esse
é o algoritmo, vamos agora falar sobre a complexidade da
memória e do tempo de execução. Pause o vídeo
aqui e veja se você consegue descobrir essas duas
complexidades. Vamos falar sobre a complexidade computacional
e de memória. A complexidade computacional e de
memória é realmente complicada
nesse cenário específico, mas
falaremos sobre isso de qualquer maneira. Dado o que você sabe até agora, pode não ser capaz de
inventar este, mas está tudo bem. Novamente, seu objetivo é
apenas entender a solução que
estou apresentando agora. Vamos falar sobre
quantas vezes são necessárias, ou vamos falar primeiro sobre
quantos resultados existem aqui. Todas as possíveis
sequências de três comprimentos de a e b. Aqui teremos
duas opções para cada letra, ou b vezes 2 vezes 2 vezes 2. Isso significa que há
duas opções diferentes acima da potência de três opções diferentes aqui. Se quisermos todas as sequências possíveis de comprimento
k, produziremos duas para
as k respostas diferentes. Agora, para produzir duas a k respostas
diferentes, na verdade, tivemos que gerar todas as soluções de dois comprimentos e um
comprimento também. Na realidade, o que temos é
gerar de duas a
três opções diferentes. Tivemos que passar por
dois a dois e depois dois a um também. Isso é verdade em geral. Se quiséssemos gerar
todas as quatro sequências de comprimento, teríamos gerado dois
para um dois três e dois para quatro combinações diferentes
e assim por diante. Na realidade, o que isso
significa é que isso é na verdade, uma soma de até, digamos, valores j onde
no máximo j é igual a k. Aqui temos essa
soma desagradável de vários termos. No entanto, felizmente para nós, a análise de ordem de magnitude só se preocupa com o termo de maior
magnitude. Aqui podemos simplesmente
resumir isso como o de 2 elevado a n, ou eu acho que k, já que estamos usando k. Sabendo que esse
algoritmo é muito lento, essa é a
complexidade computacional. Felizmente para nós, a complexidade da
memória é,
bem, na verdade,
infelizmente para nós, complexidade
numérica também
é a mesma. O de 2 para k. Este é
um algoritmo bem lento. Também é um algoritmo muito
caro, mas vamos deixar isso, que é bonito,
é complexo. Mas pelo menos considerando o que
dissemos até agora, essa é uma maneira de fazer isso, e faremos dessa maneira por enquanto. Faça uma pausa no vídeo
aqui e tente codificá-lo. Agora, aqui está uma solução. Para começar,
vamos criar uma fila. Assim como
falamos antes, adicionaremos a sequência vazia. Essa sequência vazia contém todos os conjuntos possíveis de sequências de comprimento
zero. A partir disso,
geraremos todos os conjuntos possíveis de sequências de um comprimento,
e assim por diante. Embora haja
algo na fila, continuaremos gerando de novo e de
novo e de novo. Vamos seguir em frente e sair da
fila ou retirar a primeira sequência de caracteres. Se nossa palavra aqui tem
exatamente o comprimento k, então vamos simplesmente imprimir essa palavra e estamos prontos para começar. No entanto, se a palavra ainda
não tiver o comprimento k
, nós a estenderemos. Vamos estendê-lo
com a letra
a e estendê-lo com a letra b. Aí vamos. Isso é tudo para nossa função. Isso nos dará todas as sequências Kalign
possíveis porque isso garante que vamos estender com
todas as possibilidades, a e b, e isso garante que capturemos todas as
sequências de Kalign à medida que elas surgirem. Se houver algo
mais longo do que uma sequência de Kalign, então, bem, ela
não vai a lugar nenhum. Não continuaremos
trabalhando com isso. Na verdade, você pode
provar que
não haverá comprimento maior que k, mas isso não é muito importante. O ponto é que essa função
deve nos dar o que queremos. Vamos tentar agora. Clique no botão verde “Executar”
na parte superior e você
verá que print_baba
desaparecerá dessa lista
de falhas. Lá vamos nós. Print_baba agora saiu
da lista de falhas. passamos nesse teste. Vamos passar para
a próxima pergunta. Na próxima pergunta,
vamos agora usar pilhas ou filas para imprimir escadas. Em particular, imprima o
número de maneiras pelas quais
podemos subir k escadas se você puder dar um ou dois
degraus por vez. Se você tiver uma escada, só
poderá subir de uma maneira. Se você tiver duas escadas, você pode subir de duas maneiras, dando um
passo de cada vez
ou dando os dois degraus ao mesmo tempo. Se houver três escadas, você pode subir 1,1,1 ou subir dois
degraus e depois um degrau, ou pode subir um
degrau e depois dois degraus,
então é 1,1,1; 1,2 ou 2,1. Há três maneiras de
subir três degraus. Essa função deve
calcular o número
de maneiras necessárias para subir k escadas se você puder
dar um ou dois degraus. Agora, antes de considerar o
algoritmo, aqui está uma dica. Bem, você pode pausar o vídeo aqui se não quiser a dica, mas a dica é a seguinte; antes de nossas
ações, entre aspas, para cada palavra que ainda não tinha o comprimento k, tivemos duas ações diferentes. Você pode adicionar a ou você pode adicionar b. Aqui, você tem
algo parecido. Se você ainda não
subiu todos os k degraus, você tem duas ações diferentes. Você pode subir um degrau ou
subir dois degraus. Sabendo disso e sabendo que anteriormente
usamos a fila para representar todas as
formas possíveis de criar uma palavra, você também pode usar essa
fila agora para criar todas as formas
possíveis de subir escadas. Pause o vídeo aqui e veja se você consegue
descobrir o algoritmo. Agora, aqui está uma solução. Na verdade, a solução
refletirá bem de perto a
solução anterior. O que vamos fazer é para cada conjunto de escadas, digamos que tenhamos uma fila agora, nosso objetivo será, pois cada item
na fila
será outra maneira de
alcançá-la certo número de etapas. Aqui está uma maneira de colocar isso.
Digamos que temos zero. Isso significa que essa é uma maneira de chegar
a zero escadas. Em seguida, vamos
desenfileirar esse 0. Em seguida, adicionaremos
à fila dois itens. Você pode dar um passo
ou dar dois passos. Vamos pegar 0 mais
1 e 0 mais 2. Em seguida, você desenfileirará
o primeiro item. Então, vamos, novamente, entrar na fila. Nós diremos que existem
duas possibilidades você pode dar um passo, você pode dar 1 mais
1, que é 2, ou você pode dar dois
passos, que são três. Em seguida, vamos sair da fila novamente. Vamos desenfileirar esses dois. Então diremos, aqui estão dois. Você pode dar um ou dois
passos a partir desse ponto. Você pode pegar 2 mais 1
ou três, ou 2 mais 2, que é 4, e assim por diante e assim por diante.
Você pode continuar fazendo isso. Basicamente, o que acontecerá é se você contar o número de vezes que k ocorre
nessa fila, isso lhe dirá
quantas maneiras existem chegar a esse número de escadas. Isso é tudo para a
solução conceitual do algoritmo. Na verdade, vamos ignorar a complexidade da memória e do tempo
de
execução desse problema específico só porque é bastante
difícil de computar. Existe uma maneira de computá-lo. Vamos pular isso por enquanto. Incluirei uma versão
escrita
da solução no arquivo
final da solução. Enquanto isso,
vamos passar a realmente codificar essa função. Novamente, pause o vídeo aqui e tente codificar a solução. Agora, vamos codificar a solução. Começaremos
criando uma fila
aqui com apenas zero itens. Essa fila agora tem zero itens. Também inicializaremos que
o número de maneiras pelas quais podemos
subir até k escadas é zero. Embora tenhamos algo
na fila, enquanto houver
maneiras de subir as escadas, sairemos da fila para
subir as escadas. Isso vai sair da fila para
subir as escadas. Então, se tivermos feito
até k etapas, aumentaremos o número de maneiras
possíveis de obter
até k etapas em um. Se ainda
não chegamos a k degraus, então as escadas são menores que k, consideraremos
maneiras de chegar lá. Consideraremos
mais 1 escada ou consideraremos dar dois degraus. Então, finalmente, retornaremos
o número total de maneiras necessárias para
chegar a k etapas. Agora que você tem isso,
vamos em frente e aperte “Executar”. Lá vamos nós. Agora podemos ver que print_stairs não está mais
em nossa lista de falhas. Passamos em todos os casos de teste. Antes de passarmos para
a próxima pergunta, eu queria trazer essa dica. A dica é resolver
o problema central e,
em seguida, considerar os casos extremos. Estamos ignorando algumas
das dicas aqui para casos extremos e você pode vê-las se
voltar aos slides,
mas a ideia básica é, novamente, focar no problema central antes de abordar a borda casos. Isso não é muito
relevante no momento,
mas, à medida que resolvemos os problemas, veremos cada vez mais
esses casos
extremos
e, às vezes, eles
podem ser uma distração. Novamente, concentre-se primeiro em resolver
o problema central. Aqui, agora vamos usar pilhas e filas para
verificar parênteses. Na verdade, esse é o primeiro problema em
que veremos vários casos extremos
aleatórios.
Aqui está o problema. Vá e role um
pouco para baixo em seu arquivo e você verá que nosso objetivo é
verificar se a string fornecida contém parênteses correspondentes. [Risos] Na verdade, eu
já te dei uma dica aqui. Você deve usar uma pilha, mas vamos entrar e rolar até aqui
e ver o que isso significa. Parênteses correspondentes significam que para cada parêntese
inicial, você tem um parêntese de
fechamento correspondente. No entanto, não é
só se existir, tem
que estar na ordem correta. Por exemplo, veja, aqui você tem um parêntese
inicial. Na verdade, só
falta um parêntese final, mas aqui está um caso em que você
tem parênteses inválidos. Aqui você tem o parêntese final
e, em seguida, o parêntese inicial. Eles estão fechados incorretamente. O que isso significa é antes de cada parêntese
fechado, você precisa de um parêntese
inicial correspondente. Isso é o que significa combinar. Na verdade, esse é um problema
muito comum que você verá tanto como exercício quanto possivelmente até mesmo
na própria entrevista. É bom saber isso, é bom entender qual é a
premissa do problema. Novamente, queremos verificar se a string fornecida contém parênteses
correspondentes. Novamente, a dica é
usar uma pilha. Faça uma pausa
no vídeo aqui e veja se você consegue criar
o algoritmo. Agora vamos falar
sobre a solução. Nossa solução, como
mencionamos anteriormente
na dica ou na dica, é realmente usar uma pilha. Digamos que temos
essa pilha aqui. Essa pilha representará quantos
parênteses iniciais ou quão profundos estamos entre parênteses. Digamos que
iteramos
a string e vimos
esses parênteses iniciais, vamos adicionar um parêntese
inicial aqui. Então, agora vemos um parêntese
fechado. Sempre que virmos parênteses
próximos, sairemos da pilha. Saímos da pilha, removemos um nível acima, removemos esse grupo. Agora que vemos outros
parênteses iniciais, vamos adicionar novamente, vemos outros parênteses iniciais que
vamos adicionar novamente, e aqui vemos
parênteses fechados, então vamos vá em frente
e remova isso, e então vemos outros
parênteses iniciais, então vamos adicioná-los novamente. Finalmente, vamos
fechar isso novamente. Agora podemos ver
no final da
função que ainda temos um parêntese não fechado,
que é esse. Esse grupo não está fechado. O que isso significa é que este
não é um conjunto correspondente
de parênteses, podemos retornar falso. Em essência, essa pilha realmente
representa o quão profundos
estamos nesse
conjunto aninhado de parênteses. Sempre que você sai, significa que estamos de volta a um nível. Nós nos livramos de um conjunto
aninhado de parênteses. Se não tivermos voltado
totalmente para cima e para fora dos parênteses, então não está combinando. Ao mesmo tempo, se você
ver algo assim, que começa com parênteses
próximos,
então, logo no início da string, a
pilha está vazia, então não há nada para estourar. Isso nos
dirá imediatamente que, novamente, esse é um
conjunto inválido de parênteses. Isso é conceitualmente, como
vamos fazer isso. Agora, vamos falar sobre qual é a complexidade
do tempo de execução
e a complexidade da memória. Pause o vídeo aqui e
tente descobrir. Aqui está a resposta.
Tanto para o tempo de execução
quanto para complexidade da memória,
ambos são lineares. Temos à medida que
iteramos aqui, bem, basicamente só iteramos sobre a corda uma vez. Cada item só
é visto uma vez. Segundo, para compreender a complexidade da memória
linear, imagine se você tivesse uma string
parecida com essa
, nossa pilha
seria simplesmente todos esses
parênteses iniciais. Temos até N
itens diferentes em nossa pilha, que significa que nossa
complexidade de memória é O de N. Agora vamos finalmente passar
para a terceira etapa, vamos começar a codificar
esse algoritmo. Pause o vídeo aqui
e tente codificá-lo. Vamos entrar e
codificar esse algoritmo agora. Aqui vamos criar
uma pilha para começar, e para cada
letra da string, vamos
verificar se a letra começa com um novo conjunto de parênteses, vamos
empurrar para a pilha. Caso contrário, podemos supor que a letra é um parêntese de
fechamento. Isso é algo que
acabei de escrever anteriormente. Basicamente, em uma entrevista, você deve perguntar se a sequência pode conter outros caracteres, como números ou
letras, e qualquer outra coisa. Agora, só para simplificar, vamos supor que
há apenas parênteses
na string. Aqui, se não for um parêntese de
abertura, é um parêntese de fechamento. Para cada parêntese de
fechamento, vamos
sair da pilha. Então, finalmente, se a
pilha não tiver mais nada
, retornaremos verdadeira. Se sobrar alguma coisa na pilha, isso significa que não fechamos
todos os nossos parênteses, então devemos retornar false. Agora, sabendo disso, aqui está uma
dica que eu mencionei anteriormente ou nos slides anteriores, mas
eu não mencionei. Aqui, considere uma sequência vazia. O que acontece quando sua
pilha está realmente vazia? Existe algum lugar em seu código onde seu código seria quebrado? Nesse caso específico, sim, stack.pop. Aqui, não verificamos se a pilha já está
vazia, então vamos fazer isso. Se a pilha já estiver vazia, bem, o que fazemos aqui? Se a pilha já estiver
vazia e estivermos tentando remover um parêntese de
abertura, isso significa que vimos um parêntese de fechamento antes vermos os parênteses
iniciais correspondentes. Sabendo disso, isso significa, novamente, a string é inválida, então devemos retornar false. Isso é tudo para os casos
extremos, na verdade. Entradas inválidas
não se aplicam aqui, então isso conclui esse problema, vamos ver
se elas passam em todos os nossos testes. Executando o código, você notará que is_valid_parênteses não está nessa lista de falhas, então
passamos nesses testes de funções. Vamos passar para
o próximo problema. Aqui está a dica: na verdade,
considere personagens estranhos. Essa foi a dica aqui em cima, em uma entrevista, certifique-se
de perguntar se a string poderia conter outros caracteres para
esse problema específico. Agora você deve tentar
isso sozinho. Use pilhas ou filas
para verificar se há parênteses
e colchetes correspondentes. Aqui temos parênteses
que abrem e fecham, e também temos colchetes
que abrem e fecham. Esse é um agrupamento válido porque cada par de parênteses
é perfeitamente combinado. Mas há um desafio
adicional. Observe aqui que, se você
considerar apenas colchetes, eles estão corretamente combinados. Se você considerar apenas
os parênteses, eles também serão combinados. No entanto, você notará
que esse conjunto de colchetes e parênteses estão se cruzando, ou
seja, um agrupamento inválido. Sabendo disso, vamos
tentar criar um algoritmo
para esse problema. Pause o vídeo aqui e tente ver como você usaria
suas estruturas de dados, pilhas ou filas para
resolver esse problema. Novamente, você pode usar seu
problema anterior como inspiração. Pause o vídeo aqui
e experimente. Aqui está uma solução.
Assim como antes, vamos usar uma
pilha, exceto que desta vez, a pilha conterá parênteses
iniciais
ou colchetes iniciais. Ele sempre conterá basicamente a pontuação
inicial. Sabendo que,
sempre que quisermos, digamos que vemos um parêntese de
fechamento
, tentaremos
sair da pilha. Nesse caso, vamos
retirar esse colchete. No momento, estamos vendo
um parêntese de fechamento. parênteses de fechamento e esse
colchete de abertura não coincidem, então isso significa que esse é
um agrupamento inválido. Isso ocorreria
neste caso específico. Você veria na pilha
algo assim. Você veria um colchete, veria um parêntese
e, quando saísse , veria esses parênteses de
abertura versus esse colchete de fechamento. Então, quando esses dois não
coincidem, agora são inválidos. Caso contrário, o algoritmo parece praticamente o mesmo de antes. Sempre que você vê uma pontuação de
abertura, adicione-a à pilha, sempre que você vê uma pontuação de
fechamento, tente aparecer e
certifique-se de que está
exibindo a pontuação de
abertura correta. Isso é tudo para o algoritmo. Novamente, vamos agora considerar qual é o tempo de execução
e a complexidade da memória. Pause o vídeo aqui e veja
se você consegue descobrir. Agora, aqui está a resposta. Tanto para o tempo de execução quanto para a complexidade da
memória, temos O de N. Assim como antes, para
complexidade computacional, simplesmente
iteramos uma vez sobre
cada caractere, então isso é O de N. Para complexidade de
memória, novamente, poderíamos
ter uma string com apenas um monte de
pontuação de abertura como esta. Se você tem um monte de
pontuação de abertura como essa
, sua pilha é praticamente
tão longa quanto sua string de entrada. Aqui, nossa
complexidade de memória também é O de N. Agora que passamos pelas duas primeiras
etapas, vamos agora tentar a terceira etapa. Vamos tentar codificar esse algoritmo. Pause o vídeo aqui e
veja se você consegue programar. Agora vamos tentar
codificar essa função. Vamos começar
criando uma pilha
e, em seguida, vamos
iterar sobre a pilha exatamente como
fizemos antes. Se nosso caractere atual for
um sinal de pontuação inicial, então o
colocaremos na pilha. Então, se virmos um parêntese de
fechamento, verifique novamente se
a pilha atual tem parênteses iniciais
e, em seguida, retorne false, se os dois não coincidirem. Caso contrário, se for
um colchete de fechamento, certifique-se de que sua pilha esteja
atualmente dentro de um colchete, caso contrário, retorne false. Por fim, certifique-se de que sua pilha tenha fechado
todos os grupos possíveis. Se você fechou todos os grupos
, sua pilha não
teria mais nada nela. Todos os
grupos correspondentes teriam
sido retirados. Agora que temos nossa função, vamos executá-la. Clique no
botão “Executar”, na parte superior, no botão verde que
executará todos os testes. Aqui podemos ver que is_valid_grouping está ausente
em nossa lista de falhas, então
passamos com sucesso em todos esses testes. Isso conclui os
exercícios desta lição. Mais uma dica final, pilha é como uma pilha de pedras, pilha de roupas,
pilha de caixas, o último item que você adiciona é
o primeiro item que você tira. Uma fila é como uma
fila, uma fila de carros, de fila de pássaros, eu
acho, eu não acho que
os pássaros façam fila. Fila de pessoas, fila de caixas, qualquer linha, o primeiro item que você adiciona é o
primeiro item que sai. Novamente, tenha isso em mente. Isso conclui esta
dica final e esta nota final. Para obter uma cópia desses slides e o código
finalizado desta lição, não
deixe de conferir
o site do curso. Finalmente, isso conclui
nossa prática de sequências. Eu mencionei algumas dicas para
entrevistas, mas não gaste muita energia
mental
memorizando-as. Deixe que a prática que
estamos fazendo você
adquira o hábito de
seguir essas três etapas. Essa é a parte mais importante, adquirir o hábito de
fazer essas três coisas, modo que quando você está
extremamente nervoso, quando você está
pirando, quando você
não está pensando
direito em um entrevista, você usará como padrão essas
três etapas. É isso mesmo.
7. Listas: array vs. lista vinculada: Nossa primeira categoria é
para listas de itens. Analisaremos duas estruturas de
dados, em particular, matrizes
e listas vinculadas. Em seguida, abordaremos seus prós e contras com base em nossa análise. Vamos começar concluindo
nossa análise de matriz. Uma matriz é simplesmente
uma lista de itens. Na memória, os itens da matriz são colocados um
ao lado do outro. Anteriormente, descobrimos que
pesquisar uma matriz leva O de n tempo, pois
precisamos percorrer toda a lista um item de cada vez,
para encontrar o valor. Também descobrimos que a busca
leva O de 1 tempo constante. Vamos agora finalizar essa
análise e ver quanto tempo
leva para inserir um
item na matriz. Digamos que você tenha essa
matriz de três itens. Agora estamos visualizando um pedaço da sua memória no seu computador. Gostaríamos de inserir um
novo item, com um valor de quatro. Em teoria, poderíamos alocar um espaço para quatro como este. No entanto, seu computador
pode já ter alocado esse espaço
para outros dados. Como resultado, a
operação de inserção alocará um novo pedaço de memória para
o novo tamanho da matriz e, em
seguida, o algoritmo copiará
cada elemento um por um. Por fim, ele atualizará
o valor do novo item. Para uma matriz com n itens, a inserção faz n cópias. A inserção é, portanto, uma operação
O de n. Para resumir, a inserção
leva tempo linear. Vamos ver quanto tempo a
exclusão demora. Digamos que você tenha uma
matriz de seis itens, você gostaria de excluir o
terceiro item, o número 2 aqui. Para fazer isso, o algoritmo de
exclusão
mudará todos os
números depois de aumentar. Ele copiará 3 para frente, copiará 4 para frente, copiará 7 para frente e,
em seguida, desalocará o último ponto. Como resultado, para uma
matriz de comprimento n, exclusão faz n cópias. Isso torna a exclusão O de n. Isso completa nossa tabela de complexidades de
tempo
de execução da matriz. Você notará imediatamente que a matriz é muito eficiente para a busca, mas ineficiente
em todo o resto. Nosso array é ineficiente para
modificações, em particular apenas porque precisamos manter todos os dados
contíguos na memória. Em outras palavras,
todos os itens devem estar um ao lado do
outro assim. Mas podemos mudar isso. Vamos colocar cada item em uma lista onde quisermos na memória. Para conectar todos os
itens em uma lista, precisamos adicionar links. Cada um desses links
também é chamado de ponteiros. Cada ponteiro aponta para um local para o
próximo item na lista. Também precisamos adicionar um marcador que indique que
a lista terminou. Isso é o que
chamamos de lista vinculada por causa de todos os
links que inserimos. Esta lista vinculada vem com
algumas propriedades muito boas. Vamos agora analisar
essa lista vinculada. Digamos que queremos inserir um novo valor 3 no
final da lista, depois simplesmente
alocamos dois novos pontos e garantimos que 2 pontos a 3. Não importa quantos itens
existam na lista vinculada, temos um trabalho constante
a ser
feito para inserir um novo item, alocar dois espaços e
alterar um ponteiro. Como resultado, a inserção para listas
vinculadas é O
de 1 tempo constante. A história é semelhante, mesmo se quisermos inserir um valor no
meio da lista, alocar dois novos espaços para
o novo valor e um ponteiro, depois apontar o valor
anterior de 8 a 3 e, em
seguida, aponte o novo valor de 3 a 2. Aí está.
A inserção está completa. Não importa o tamanho
da lista vinculada, só
precisamos alocar dois espaços e
alterar dois ponteiros. Este ainda é um tempo
constante O de 1. Para resumir até agora, uma lista vinculada tem inserção de tempo
constante. Vamos ver agora como a remoção
ou a exclusão funcionam. Digamos que queremos excluir
3, o último item. Isso é simples. Nós apenas revertemos o que
fizemos para inserção. Exclua o penúltimo ponteiro. Agora, o item 3 não faz mais
parte da lista vinculada. Para excluir o último item, você só precisa de uma alteração
de um ponteiro. Isso é tempo constante ou O de 1. Excluir um item no meio
da lista também é simples. Digamos que você queira excluir
3, o terceiro item, mude o ponteiro para
oito para pular 3. Agora, na verdade, o 3 não
faz mais parte da
lista vinculada, e pronto. Para excluir um item, não importa onde ele esteja, simplesmente
trocamos um ponteiro. Esse tempo é constante
novamente ou O de 1. Para resumir até agora, uma lista vinculada tem
tempo constante de inserção e exclusão. Agora vamos ver quanto tempo leva para acessar
a lista vinculada. Digamos que estamos
procurando o valor 4. Precisamos percorrer toda
a lista vinculada, uma
por uma, até encontrarmos 4. Primeiro, verificaremos o primeiro item. Isso é 4? 9 não é 4, então
acesse o próximo item. Isso é 4? 8 não é 4, então
acesse o próximo item. Isso é 4? 3 não é 4, próximo, 2 não é 4. Portanto, para uma
lista vinculada de comprimento n, precisamos de até n verificações. Pesquisar uma lista vinculada
leva O de n tempo. Resumindo, uma lista vinculada tem tempo
constante de inserção
e exclusão, mas tempo de busca linear. Infelizmente,
buscar itens de uma lista vinculada também é
muito lento. Digamos que queremos verificar ou buscar o terceiro item
na lista vinculada. Não há como saber onde o terceiro item está na memória , então precisamos começar
do início. Acessaremos o primeiro item e seguiremos o ponteiro
até o próximo item. Acesse o próximo item e siga o ponteiro do mouse
até o próximo item. Por fim, acesse este item. Como esse é o terceiro
item, retorne seu valor. Para uma lista vinculada de comprimento n, precisamos percorrer
até n nós. A busca pelo item de uma lista vinculada leva o O em um tempo. Para resumir,
concluímos agora a análise da
lista vinculada. Modificar a lista, inserir ou excluir é eficiente. Acessar a lista, pesquisar ou buscar é ineficiente. Agora que analisamos
matrizes e listas vinculadas, vamos ver quando usar quais. Essa é a
parte mais importante desta lição. Mesmo que você esqueça
tudo o que eu disse antes, mantenha o próximo slide enfiado no bolso de trás. Esta
é a sua lição. Aqui está um resumo das complexidades do
tempo de execução. À esquerda, temos as
quatro operações que analisamos. Na segunda coluna, temos as
complexidades de tempo de execução da matriz de antes. À direita, temos uma
lista vinculada de complexidades de tempo de execução. Para uma matriz, a
modificação é lenta, mas a busca é rápida. Isso significa que as matrizes são ideais para muitos acessos aleatórios de
um conjunto fixo de dados. Para uma lista vinculada, o
acesso é lento, mas a modificação é rápida. Isso significa que as listas vinculadas
são vantajosas por seu tamanho dinâmico, ideal para armazenar dados em constante
mudança. É isso mesmo. Este é o
slide de resumo desta lição. Para obter uma cópia desses slides
e de mais recursos, não
deixe de conferir
o site do curso. Agora vamos ver essas
estruturas de dados em ação. Na próxima lição,
praticaremos
o uso e a implementação
dessas estruturas de dados, abordando nossos dois
objetivos de aprendizado para este curso.
8. Listas de prática: Bem-vindo a outra aula
prática. Aqui vamos
praticar listas. Em particular,
abordaremos a maioria das listas vinculadas. Assim como antes, navegue
até esse URL
alvinwan.com/datastructures101/lists. Depois de ver esta página, bifurque o projeto para obter
sua própria cópia editável. Para fazer isso, clique
no nome do projeto no canto superior esquerdo para
obter uma lista suspensa, clique nas reticências para
obter outra lista suspensa
e, finalmente, clique
no botão “Bifurcar”. Então, sugiro colocar seu
Skillshare e
ondulá-lo lado a lado,
conforme mostrado aqui. Aqui estão os diferentes subtópicos que eu
quero abordar. Vamos
começar com o prompt. Esse é o código que seu entrevistador
fornecerá a você. Em seguida, falaremos sobre
três categorias de solicitações: implementação,
uso e, em seguida, a combinação de
diferentes estruturas de dados. Para começar, no
lado direito, você deve ver o código que seu entrevistador
provavelmente lhe forneceria. Aqui, você teria uma pilha, você teria uma fila. Bem, acho que empilhar e filar provavelmente não
forneceriam, mas você certamente poderia
usá-los se precisasse. Esse é o código
que você receberia, basicamente uma implementação de
lista vinculada. Você terá algo
parecido com o seguinte. Você teria o valor
do link e
também teria uma conexão com
o próximo link. Este aqui é
um utilitário que eu forneci para que
você possa realmente visualizar sua lista vinculada. Isso pode ou não ser fornecido. Mas se não fosse, você também poderia usar
essa implementação. Vamos agora começar com
nosso primeiro exercício. Agora, para todos os nossos exercícios,
incluindo este, vamos seguir
os mesmos três passos os quais falamos antes. Novamente, é muito importante ter isso em
mente e praticar. Primeiro, projetaremos
o algoritmo sem código verbal ou visualmente. Em segundo lugar, relataremos o
tempo de execução e a complexidade da memória. terceiro lugar, então começaremos a codificar. Aqui está a lista vinculada anexando. O que vamos fazer é acrescentar um item à lista vinculada. Então, aqui teremos, digamos, uma lista vinculada
que tenha 1, 2 e 3. Queremos acrescentar
o valor quatro. Depois de anexá-la, teremos uma
lista vinculada que é 1, 2, 3, 4. Agora, faça uma pausa no vídeo aqui para determinar
qual algoritmo você está usando. Conceitualmente, quais serão as
etapas. Aqui está a resposta. Conceitualmente, o que vamos fazer é, novamente, ter apenas um ponteiro para o início
da lista vinculada. Vamos seguir esse
ponteiro exatamente como o que é mostrado aqui no lado esquerdo com esta seta esquerda em preto. Começaremos com esse ponteiro, depois
navegaremos até o próximo link e
continuaremos até que você chegue ao
final da nossa lista de links. Então, no final
da nossa lista de links, simplesmente
criaremos um novo link
e o anexaremos à lista. Isso é conceitualmente
o que vamos fazer. Vamos até
o final da lista de links e depois
adicionaremos um novo link. Sabendo que agora, novamente, teremos que considerar
a segunda etapa em nosso processo de três etapas. Qual é a complexidade de memória e tempo de execução
desse algoritmo de acréscimo? Pause o vídeo aqui e veja
se você consegue descobrir. Agora, aqui está a solução. Esse algoritmo é linear em complexidade
computacional
simplesmente porque você precisa percorrer
toda a lista vinculada, que pode ter até o comprimento N. Essa é a complexidade
computacional O de N. Para a complexidade da memória,
temos a complexidade de memória O de
1
simplesmente porque
não usamos nenhuma
memória adicional além do armazenamento para o item atual e a lista vinculada existente. Na verdade, não criamos
nenhuma nova estrutura de dados. Nós só temos esse link
que é O de 1 custo. Sabendo disso, vamos agora
codificar o algoritmo. Novamente, pause o vídeo aqui e veja se você consegue codificá-lo. Agora, aqui está uma solução. Aqui, vamos
até o final da lista. Aqui, diremos que
link.next não é nenhum. Isso significa que, enquanto tivermos outro link em
nossa lista atual, continuaremos percorrendo
até chegarmos ao fim. Então, finalmente, no
final da lista, então esse link agora estará
depois desse loop while, o último elemento, então será 3. Agora que temos 3, vamos escrever link.next
é igual ao nosso novo link, que contém um valor 4. Sabendo disso, vamos
agora fazer nossos testes. Agora podemos ver que o
acréscimo está ausente nessa lista de falhas, então
passamos em nosso teste anexado. Vamos agora passar para
a próxima pergunta. Agora, antes de
passarmos para a próxima pergunta,
na verdade, também para a próxima
pergunta, memorize como
percorrer uma lista vinculada. Sempre será
quase o mesmo. Você terá um
loop while, verificará se não está
acessando algum objeto do tipo nenhum e, em
seguida, acessará o próximo link. É assim que você
praticamente sempre percorre
uma lista vinculada. Lembre-se disso porque o próximo problema usará
algo semelhante. Vá em frente e role para baixo em seu arquivo e você verá agora
aqui a pergunta de inserção. Nosso objetivo é inserir após
o índice fornecido I. Em particular, digamos que você
tenha essa lista vinculada 1, 2, 3 e queremos inserir
um link aqui mesmo após o índice 0 e
queremos inserir o valor 4. Aqui vamos inserir após o
índice 0, o valor 4. Aqui temos 1, 4, 2, 3. Se você estiver olhando para
o lado esquerdo, nós
realmente visualizamos como isso vai
parecer para
ajudá-lo um pouco. [RISOS] Faça uma
pausa no vídeo aqui e veja se você consegue
determinar como seria
o algoritmo. Agora, aqui está a resposta. O que faremos é primeiro
percorrer a lista até chegarmos ao link
certo para modificá-la. Nesse caso,
digamos que estamos inserindo H depois de 9, assim como estamos
inserindo 4 após 1. Aqui, vamos
navegar até 9. Quando atingirmos o valor 9
, criaremos um novo link. Vamos revincular 9 a 8
e, em seguida,
revincular 8 a 2.
Existem três etapas. Navegue até o elemento correto, revincule ao link atual e use o
link atual para se conectar
ao próximo link. Esse é
o algoritmo. Agora, sabendo que esse
é o algoritmo, faça uma pausa
no vídeo aqui e descubra qual é o tempo de execução
e a complexidade da memória. A
complexidade da memória e do tempo de execução aqui. complexidade
computacional será linear. Talvez tenhamos que percorrer
todo o caminho até o final da lista
para inserir algo. complexidade da memória
é constante porque a única coisa que estamos criando
é esse link em si, que é O de 1 custo
constante de memória. Sabendo disso, vamos agora
passar para o código. Pause o vídeo aqui
e tente codificar. Agora, aqui está uma solução. Assim como antes,
vamos começar realmente navegando
usando um loop while. Na verdade, em vez de
usar um loop while ,
usaremos um
loop for porque sabemos exatamente quantos passos
você vai dar. Para link no intervalo i, link é igual a link.next. Eu usei o sublinhado aqui para indicar que não vamos
usar essa variável. Tudo o que importa é que
acessemos o.next.next.next
basicamente i vezes até você chegar
ao elemento certo. Quando você estiver lá, vamos
reatribuir algumas coisas. Primeiro, vamos reatribuir o próximo
atributo do valor atual ao novo valor. Mas então, também
precisamos conectar esse novo link ao
resto da lista vinculada. Vamos usar isso para conectarmos ao link
original.next. Novamente, neste exemplo
no lado esquerdo, 9 originalmente apontava para 2. Agora vamos aos pontos 9 a 8. Isso está aqui. Link.next
é igual ao nosso novo objeto. Em seguida, vamos
apontar 8 a 2, e isso está aqui
na segunda parte. Temos o link.next original e o substituímos
pelo novo link.next. É isso mesmo. Essa é a
nossa função Inserir. Vá em frente e execute novamente seus testes
pressionando o
botão verde “Executar” na parte superior. Agora podemos ver que
há uma falha a menos. Não inserimos em
nossa lista de falhas, passamos com sucesso nos testes. Vamos passar para
o próximo problema. Aqui, uma dica que
tínhamos para esse problema e para os futuros é
sempre verificar se não há nenhum valor. Então, um erro comum
que você obterá com
problemas de listas vinculadas é que você obterá, por exemplo, neste link. Em seguida, você obterá o link é
um objeto OneType. Next não é um atributo
de um objeto NoneType. Isso é muito comum. Quando você estiver depurando e
mesmo antes de depurar, mesmo antes de executar o código enquanto fala com
o entrevistador, verifique se você está
examinando seu código e verificando se há algum lugar
onde pode não haver nenhum valor e
garantir que você não esteja chamando.next ou.value
em um valor NoneType. Nesta
função específica
aqui nas linhas 83 e 84, é bem possível
que eu fosse inválido. Digamos que aqui fosse 100. Em seguida, alcançaríamos
em algum ponto valor de
NoneType e
tentávamos chamá-lo em seguida. Para tornar essa função
mais robusta, você precisaria verificar isso. Você teria que explicar isso. Nessa implementação
simples em particular, não
fizemos isso, mas apenas algo a ter em
mente sempre,
sempre verifique se não há valores em suas entrevistas e em qualquer
poema que você esteja escrevendo. Vamos agora passar para
o próximo problema. Nosso objetivo agora é implementar
uma pilha usando uma lista vinculada. Aqui temos uma lista vinculada, temos uma, duas. Nosso objetivo é poder tratar isso como se fosse uma pilha. Se chamarmos dot pop
nele, ele nos daria o
último item, que é dois. Se chamarmos push, aqui pressionamos 2, pressionamos 3, então se estourarmos, recuperaremos o último item
que empurramos, que é três. Estoure novamente, você
receberá o
penúltimo item que você empurrar,
que é dois. Nosso objetivo é implementar uma pilha , mas usando uma
lista vinculada no backend. Faça uma pausa no
vídeo aqui e veja se você consegue descobrir
se o algoritmo, neste caso, o algoritmo é como você vai empurrar e
como você vai estourar? pausa no vídeo aqui.
Aqui está a resposta. Conceitualmente falando, isso é realmente muito parecido
com o começo. Quando dizemos push aqui, vamos basicamente escrever
a função de acréscimo sobre a
qual falamos anteriormente. Podemos dizer pop aqui, vamos escrever uma
nova função, delete. Na verdade, ainda não escrevemos
uma função de exclusão, mas ela será
praticamente como qualquer outra função que
exclui de uma lista de links. Agora que conhecemos
o algoritmo, faça uma pausa no vídeo aqui e veja se
você consegue descobrir a complexidade computacional e de
memória. A solução para esta parte, complexidade do
tempo de execução e da
memória na verdade, a complexidade
do tempo de execução será linear. Vamos percorrer
todo o caminho até o final da
lista vinculada e depois adicioná-la. No caso do pop, vamos
percorrer todo o caminho até o final da
lista vinculada para removê-la. Agora, sabendo disso, a complexidade da memória
é constante. A complexidade da memória, tudo o que
você está fazendo é criar um novo link e isso
é O de um custo de memória. Você não está criando
uma lista totalmente nova. Você não está criando
outra estrutura de dados que armazene itens. Você está apenas criando um link. O custo da memória é O de um. Agora, pause o vídeo aqui
e tente codificá-lo. Agora, vamos escrever o código. Então, aqui vamos
implementar o push da
mesma forma que o
append reimplementado anteriormente. Vamos primeiro definir
um link de variável local que é o
início da nossa lista vinculada atual e depois enquanto
link.next não é nenhum. Então, embora tenhamos uma lista
vinculada, vamos percorrê-la. [RUÍDO] Então, finalmente,
no final, vamos adicionar um novo link. É basicamente isso para o método
push da função push. Vamos agora passar
para a próxima. Para remover algo,
vamos definir novamente esse link de variável local para começar com
a lista vinculada. Então, enquanto estamos
a um do fim, então não
queremos realmente o último link, queremos o penúltimo link porque esse será
o nosso novo link. Vamos atravessar novamente. Então, o que vamos fazer neste
momento é primeiro pegar o valor do último item antes de realmente removê-lo. Aqui, queríamos obter o
valor do último link. Em seguida,
vamos desvinculá-lo. Então, agora nosso penúltimo
link não aponta para nada. Esse agora é nosso
novo último link
e, finalmente,
retorne o valor. É assim que realmente excluímos do final
da lista vinculada. Vamos
clicar no botão verde, na parte superior, para executar
nosso arquivo e verificar nossos testes. Lá vamos nós. Agora podemos ver que nossa pilha via
Lista vinculada realmente desapareceu. Não há mais em
nossa lista de falhas, então passamos nesses testes. Vamos passar para
o próximo problema. Antes de passar para esse
problema, temos mais uma dica. Você quer facilmente fazer uma de suas próprias perguntas, basta misturar e
combinar qualquer uma delas. Você falou sobre três estruturas de dados
diferentes, listas
vinculadas,
pilhas e filas. Para criar
uma nova pergunta, basta implementar, escolher uma
usando e depois escolher outra. Qualquer uma dessas
combinações causará um problema totalmente novo
que você pode experimentar. Contanto que você possa passar nos mesmos testes que
escreveu para uma pilha, exceto usando sua nova estrutura de dados
, você está pronto para começar. Isso vale para
qualquer outra coisa. Se você tiver testes para fila, certifique-se de que
sua nova estrutura de dados possa passar nesses testes
e, em seguida, os testes foram vinculados à
lista, e assim por diante. É misturar e combinar qualquer uma
dessas combinações para criar um problema totalmente novo. Agora, vamos implementar a
remoção do ciclo para uma lista vinculada. Em particular, encontre e remova um ciclo em uma
lista vinculada, se ele estiver presente. Por enquanto, para simplificar, você pode assumir que todos os valores do
link são distintos. Isso é muito importante porque a primeira pergunta
que você vai considerar ao ver o
ciclo de busca e remoção é como você
vai detectar um ciclo? Uma maneira de detectar um
ciclo seria se eu já tivesse visto esse valor antes, então eu sei que atingi um ciclo.
Acho que para esclarecer isso. Digamos que você esteja
se movendo da esquerda para a direita ao longo desta lista vinculada. Conforme você avança, se de
repente você vê três duas vezes, então
você sabe que atingiu um ciclo. Mas isso só pode ser dito se souber que todos os valores do
link são distintos. É por isso que os valores dos links serem distintos é
uma questão muito importante para esse problema. Eu escrevi que aqui estão
todos os valores únicos. Essa será uma das suas primeiras perguntas para
o entrevistador. Sua segunda pergunta,
e esta é uma pergunta um
pouco mais
avançada. Você quer perguntar: existe
uma duração máxima do ciclo? Isso tem a ver com
a implementação, porque se você quiser
acompanhar todos os valores
que você viu até agora, e então você
quer dizer: “Tudo bem, eu
já vi esse valor?” Então você potencialmente
nunca poderia ver um ciclo. Toda essa lista vinculada
pode ter um milhão comprimento e que
não há um ciclo em lugar nenhum, então você basicamente a manteve
nesta enorme loja de um milhão de itens esperando para ver se algum desses milhões
os itens aparecem novamente. Esta é uma boa pergunta a se fazer: existe
uma duração máxima do ciclo? Porque dessa forma, você não
precisaria manter todos os milhões de itens se soubesse que a
duração máxima do ciclo é de apenas cinco. Essas são boas
perguntas a serem
lembradas sobre esse problema. À medida que avança e
pratica esses problemas, você começará a entender
quais perguntas fazer. Então, por enquanto, se você está
pensando que essas são
perguntas malucas do nada, não há como pensar
sobre elas, tudo bem. Assim como você vê mais
e mais delas, você se
familiarizará com os tipos de perguntas a serem feitas. Por enquanto, vamos ver se você
consegue pensar em um algoritmo. Eu distribuí partes, mas pausei o vídeo
aqui e veja se você consegue encontrar uma maneira de
remover ciclos , e aqui está a resposta. Basicamente, o que você
vai fazer é manter uma coleção de todos os
valores que você já viu. Se você já viu o
valor
, sabe que
isso é um ciclo e pode interromper o ciclo simplesmente reatribuindo
link.next de acordo. Sabendo disso, esse
agora é o algoritmo. Qual é o tempo de execução e complexidade da
memória?
Faça uma pausa no vídeo aqui. Para a complexidade da memória e do
tempo de execução, para a
complexidade computacional em particular, você terá O
de N. Vamos
percorrer toda essa lista, uma a uma. Precisamos fazer isso para descobrir se há
um ciclo ou não. Pois a segunda pergunta é: qual é a complexidade da memória? Para a complexidade da memória,
vamos
manter novamente uma coleção de todos os valores diferentes
que vimos até agora. Essa é uma complexidade de
memória O de N. de memória O de N
e complexidade computacional
O de N. Sabendo disso, vamos
agora tentar codificá-lo. pausa no vídeo aqui. Agora, vamos prosseguir e codificar isso. Aqui, vamos começar
criando um conjunto de valores. Então, se você ainda não
viu isso, um conjunto é uma estrutura de dados
que permite
verificar a associação
em tempo constante. O que significa que você pode fazer algo
assim na cena, e isso não
importa o tamanho do seu set, sempre
será executado
em tempo constante. Isso é um conjunto. Vamos usar
o conjunto para rastrear todos os valores que
você viu até agora. Embora haja algo
mais em nossa lista vinculada, vamos verificar
se esse próximo valor está em nossa lista de valores de cena. Se for, então vamos interromper
a conexão com
o próximo link. Novamente, se o próximo
link estiver em nossa lista, eu vi valores,
vamos quebrar esse link e terminaremos aqui. Estamos assumindo que há
apenas um ciclo em nossa lista. Novamente, essa seria uma ótima pergunta para fazer ao
seu entrevistador. Haverá
mais de um ciclo? Nesta
questão específica,
vamos fingir que
há apenas um ciclo. Veja.add e, em seguida,
vincularemos o valor aqui. O que estamos fazendo aqui é
dizer, tudo bem, consideramos que não
há ciclo aqui. Como não há
ciclo, vamos adicionar o valor atual dos links à
nossa lista de valores de visualização. Finalmente, esse é o padrão de
uma travessia de lista vinculada, vamos apenas acessar o
próximo item e ele
continuará funcionando. É isso mesmo. Vamos
executar essa função
e garantir que
nossos testes sejam aprovados. Pronto, podemos
ver que o
ciclo de remoção não está mais em nossa
lista de funções com falha. Vamos passar para
a próxima pergunta. Para a próxima pergunta,
e também para esta,
uma dica é sempre desenhar suas listas vinculadas e
verificar se há links quebrados. O que quero dizer com desenho são basicamente as ilustrações que eu tinha antes aqui. Se precisar misturar, desenhe-os para entender se você está vinculando tudo da
maneira certa. Eu passei rapidamente por
algumas dessas questões porque eu já
escrevi a solução e conheço as soluções. Mas, basicamente, se você
tiver um problema totalmente novo, as chances de criar um link
incorreto são muito altas. Tudo bem,
desde que você o retire. Se você desenhá-lo,
poderá descobrir os links corretos para se conectar. Essa é uma das minhas dicas aqui. Desenhe sua lista de links e
verifique se há links quebrados. Agora, para esse problema
específico, vamos apenas
discuti-lo conceitualmente. Na verdade, escrevi uma solução
totalmente funcional em código para você, mas
como ela é bastante complexa, vamos falar
sobre isso apenas de forma algorítmica. Para essa pergunta,
nosso objetivo é usar ou criar um novo objeto de arquivo usando as estruturas de dados
que já vimos. Nosso objeto de arquivo
será mesclado com outros arquivos. [Risos] Acabei de
te mostrar uma parte da
descrição da solução. Mas seu objetivo é criar um objeto de arquivo que possa se
fundir oficialmente com outros arquivos. A ideia é que existem
muitos desses arquivos. Isso significa que
você não quer copiar todos os dados
em um arquivo enorme. Se você fizer toda essa cópia, vai levar
muito tempo. Como podemos combinar vários
arquivos sem copiá-los? Se você não quiser a dica, faça uma
pausa no vídeo aqui. Mas uma dica que eu tenho para você é que não queremos copiar,
então, em vez de copiar, vamos armazenar um ponteiro
para o próximo arquivo. Teremos o arquivo 1
e depois diremos que, do arquivo 1, sabemos qual é
o próximo arquivo 2. Tudo o que você vai fazer é armazenar uma conexão ou um ponteiro. Isso deve soar muito
parecido com uma
das estruturas de dados que acabamos de
abordar e que estou usando. Agora, pause o vídeo
aqui e veja se você consegue descobrir
o algoritmo. Agora, aqui está a solução. Basicamente, vamos
usar uma lista vinculada. Cada arquivo será um link. Cada arquivo então
apontará para o próximo arquivo e dirá que esse é o próximo valor de
arquivo a ser percorrido. É assim que você armazenará esse enorme arquivo mesclado. Mas isso não é tudo,
há um pouco mais porque precisamos oferecer suporte a
essa função de mesclagem. Saber como vamos
armazená-los é ótimo. Não precisamos fazer
cópias, mas como você
realmente mescla um novo arquivo? Bem, o novo arquivo emergente, é exatamente como você adicionaria
a qualquer outra lista vinculada. Você praticamente vai até
o final da lista vinculada e adiciona o novo arquivo.
É basicamente isso. Para esse problema
ou este exercício, a única dificuldade conceitual é perceber que você
precisa usar uma lista vinculada. Esse foi realmente o problema
do indicador. Agora que abordamos
o problema do ponteiro, vamos
realmente seguir em frente só porque eu tenho uma solução por escrito para
isso e há anotações
linha por linha
para o que cada um é fazer e como funciona , mas os detalhes
não são muito importantes. Vamos passar para
a próxima pergunta. Novamente, nenhum outro navio aqui. Listas vinculadas que usamos para coleções de tamanho
dinâmico. Nesse caso específico, esse conjunto de arquivos é um
conjunto de coleções de tamanho dinâmico. Não sabemos o quão grande é, podemos acrescentá-lo
várias vezes e podemos até
removê-lo várias vezes. As listas vinculadas são ótimas para
essas coleções porque você não precisa copiar
dados sempre
que quiser adicionar ou remover um objeto. Sempre que você
quiser adicionar ou remover um link, é tempo constante. Agora, no entanto, as matrizes são
perfeitas para acesso aleatório. Falamos sobre
isso um pouco antes, mas basicamente o que isso significa é que se você quiser acessar
o item i em uma matriz, você sabe exatamente onde
ele está na memória. Você vai direto para
essa parte da memória. No entanto, para uma
lista vinculada, se você quiser o item i como viu antes, você precisa percorrer
a lista inteira, então não é tão eficiente.
Essa é a dica. As listas vinculadas são para coleções de tamanho
dinâmico, as matrizes são para acesso aleatório. Para nossa última pergunta aqui, seu objetivo é combinar estruturas de
dados para encontrar um palíndromo
em uma lista vinculada. Um palíndromo é uma palavra criada da mesma forma que é esportiva, como carro de corrida. Se você virar um carro de corrida,
você ainda ganha um carro de corrida. Aqui, sua palavra será representada
como uma lista vinculada. Aqui temos um link
que tem r nele, e que aponta para o próximo
link que tem a nele, aponta para o próximo
link que tem c, e depois aponta para
e, aponta para c,
aponta para a, assim por diante e assim por diante. Nossa lista vinculada representa
a palavra carro de corrida. Queremos verificar se essa lista
vinculada é um palíndromo. Considere quais outras
estruturas de dados você pode usar para ver
também nesta
lista vinculada como um palíndromo. Pause o vídeo aqui e veja
se você consegue descobrir. A solução conceitual para esse desafio bastante desafiador é que você quer uma
pilha e uma fila. Conforme você avança e
percorre essa lista vinculada, você adiciona à
pilha e à fila. Depois de terminar atender
toda a lista vinculada, basta abrir a barra e desenfileirar, remover de
cada fila de empilhamento e verificar se cada uma
delas é igual uma à outra. Isso é ótimo porque a
pilha é removida do final, a fila é
removida do início então você está basicamente se movendo
ao longo da corda para trás
e para frente
ao mesmo tempo, apenas removendo da
pilha e da fila. Isso é perfeito para nós,
porque em um palíndromo, uma forma de verificar se é
um palíndromo é verificar se o primeiro personagem
é você é o último. No segundo,
você vai para o penúltimo e assim por diante. Ao remover da pilha
e da fila, você obtém isso. Vamos fazer uma pausa aqui. Vamos ver, esse é o algoritmo. Qual é o tempo de execução
e a complexidade da memória? Aqui está a resposta.
Tanto para o tempo de execução quanto para a complexidade da memória, temos a complexidade linear. Pois a complexidade da memória
é linear porque estamos armazenando uma pilha e uma fila que cada uma pode ter até o comprimento n, e também temos complexidade computacional
linear porque estamos iterando sobre cada
uma dessas letras. Na verdade, estamos iterando duas vezes, mas não importa, é o de n. Agora que conhecemos o
algoritmo e conhecemos a complexidade, vamos
tentar codificá-lo. Pause o vídeo aqui
e tente codificá-lo. Vamos agora abordar a solução. Vamos
começar inicializando pilha
e a fila. Agora que temos essas duas estruturas
de dados, vamos percorrer a lista vinculada, exatamente como dissemos, e para cada
link, vamos adicioná-la a
essas duas estruturas de dados. Aqui eu vou
adicionar à pilha. Vou empurrar a
pilha e depois vou entrar na
fila também. Em seguida, passarei
para o próximo link. Assim como eu disse antes,
esse código de travessia é praticamente sempre o mesmo. Depois de terminar isso, vamos examinar essas duas estruturas
de dados, a pilha e a
fila, e
garantir que , para
cada item que removemos, eles sejam exatamente os mesmos. Enquanto houver algo
na pilha, saia da pilha e
saia da fila. Desde que coincidam,
estamos prontos para ir. Se eles não coincidirem em nenhum
momento, retornamos false. Se nada retornar falso, tudo coincide e
nós podemos retornar verdadeiro. É isso mesmo. Vamos
agora avaliar isso. Clique no
botão verde Executar na parte superior e verifique se
todos os seus testes foram aprovados. Aqui podemos ver que
nossa função é palíndromo. O link não pode
ser encontrado em nenhum lugar na
lista de falhas. Passamos com sucesso nesse teste. Essas três
funções restantes são funções bônus. Também incluí soluções
totalmente detalhadas para eles e explicações
no código,
para que você também possa experimentá-las em
seu próprio tempo. Se você tiver alguma
dúvida, sinta-se à vontade para publicá-la na seção de
discussão. Isso é tudo para esta lição. Vá em frente para ver os slides, para ver a natureza
totalmente detalhada do código e para ver a natureza
totalmente detalhada do código e
das soluções, visite
o site do curso. Isso é tudo para listas, tanto para matrizes quanto para listas vinculadas.
9. Mapeamentos: Hashmaps: Nesta lição, apresentaremos uma estrutura de dados para mapeamentos. Um mapeamento é o que
parece, um mapeamento de um
item para outro. Aqui, mapeamos o gato para
o número cinco. Nesse caso,
digamos que estamos mapeando o animal para a idade. Animal é o que
chamamos de chave no mapeamento, e idade é o que
chamamos de valor no mapeamento. Também podemos ter pares adicionais de
valores-chave no mapeamento. Observe que esse mapeamento não
tem senso de ordem, cada par de valores-chave é completamente
separado um do outro. A estrutura de dados que armazena esse mapeamento é
chamada de HashMap. Explicaremos como
um HashMap funciona, discutiremos seus prós e contras e,
em seguida, discutiremos brevemente
um conceito de bônus. Veja por que essa estrutura de dados
é chamada de mapa de hash. Basicamente, um HashMap usa uma função chamada
função hash. Essa função de hash assume algum valor com comprimento
arbitrário, como cat, e transforma essa entrada para produzir uma saída de tamanho
fixo, como dois. Essa função de hash é importante
e, como resultado, vamos ver como ambas
são usadas. Digamos que queremos
inserir algumas chaves e valores em uma tabela de hash. À direita,
temos uma tabela de hash que zero é o endereço de memória do primeiro
slot, um é o endereço de memória do segundo
slot e assim por diante. Queremos mapear o
gato-chave para o valor cinco, para fazer isso,
dividiremos o valor cat. Isso nos dá o endereço de
memória 2, então na posição dois
coloque o valor cinco. Vamos repetir isso para obter mais dados, para mapear o cão para três, o hash dog. Isso nos dá o endereço de
memória 3, então na posição três, coloque o valor três. Repetimos isso mais uma vez, para mapear porco em quatro, porco hash. Isso nos dá o endereço de
memória zero, então na posição zero
coloque o valor quatro. Esse processo requer
apenas uma constante ou O de uma vez para cada par de
valores-chave que inserimos. Para excluir do HashMap, seguimos etapas semelhantes. Para excluir cat do HashMap, primeiro faça o hash cat para obter dois
e, na posição
dois, remova o valor. Essa operação também é
constante ou O de uma vez. Resumindo, a inserção
e a exclusão de um HashMap são
O de uma vez. Muito rápido. Digamos que agora
queremos pesquisar o HashMap, cujo valor corresponde a cat. Quase no mesmo processo, hash o gato para obter seu endereço de
memória, que é dois. Então, na posição dois, pegue o valor cinco
e devolva-o. Como resultado, dizemos que pesquisar um HashMap exige A constante, novamente O de uma vez. Resumindo,
pesquisar um HashMap requer O constante de uma vez. Para um HashMap, pesquisar
e buscar são iguais, então pulamos a análise da
busca separadamente. Vamos agora entender os prós
e os contras desses HashMaps. Em resumo, os HashMaps têm tempos de execução, tempo
constante, modificação
e acesso
muito impressionantes tempo
constante, modificação . Devido à
forma como os HashMaps funcionam, eles são ideais para qualquer dado
com identificadores exclusivos. Por definição, os HashMaps
não são projetados para dados de pedidos. Como dissemos antes, cada um desses pares de
valores-chave é completamente separado. Não há senso de ordenação, não
há relação entre pares de
valores-chave separados. Já discutimos as
duas primeiras seções, o que é um HashMap e para
que ele é ideal. Discutiremos a seção de bônus depois de encerrar
o conteúdo principal. Para obter uma cópia desses slides
e de mais recursos, não
deixe de conferir
o site do curso. Isso conclui nossa
discussão central sobre HashMaps. Se você estiver satisfeito com
esse nível de detalhe, fique à vontade para prosseguir para a próxima aula
com
a prática do HashMap. Caso contrário, vamos agora
discutir a seção de bônus. Em particular,
discutimos uma ressalva para o HashMaps chamada colisões de
hash. Dissemos anteriormente
que os HashMaps são tempo
constante para
modificação e acesso. No entanto, isso nem sempre é verdade. tempo de execução realmente depende de como um HashMap foi implementado
e aqui está o porquê. Às vezes, esse fenômeno,
quando mencionado anteriormente, chamado de colisão de hash, ocorre. Por exemplo, digamos que queremos
inserir dois pares de valores-chave, mapas de
gatos para cinco e mapas de
cães para três. Como antes, batemos em
gatos para conseguir dois. Na posição dois,
colocamos o valor cinco, exatamente como antes. Agora, para inserir nosso
segundo par de valores-chave, fazemos um hash dog para obter dois, na posição dois, agora
temos um problema. Não podemos substituir
os dados existentes, então temos duas opções. A primeira opção é
chamada de endereçamento aberto. No endereçamento aberto,
simplesmente encontramos outro
slot no HashMap se o próximo slot estiver vazio, coloque seu novo valor lá. Uma maneira de encontrar um espaço
vazio é
simplesmente atravessar os slots
até encontrar um vazio e aí colocar seu valor. Também existem estratégias
para encontrar slots, que não discutiremos aqui. Outra técnica completamente
diferente para lidar com colisões de hash
é chamada de encadeamento. Nessa técnica, tratamos cada slot como uma
estrutura de dados própria. Por exemplo, poderíamos tratar
cada slot como uma lista vinculada
e, para
inserir na posição dois, simplesmente
inserimos três
na lista vinculada. Também podemos tratar cada
slot como um HashMap, qualquer estrutura de dados que fazemos, cada com suas próprias
desvantagens, mais uma vez. Em resumo, definimos
uma colisão de hash e também vimos duas maneiras de
lidar com uma colisão de hash. Abra o endereçamento ou encontramos
outros slots vazios para usar ou encadear, onde tratamos cada slot como sua
própria estrutura de dados. Isso conclui nossa seção de bônus aqui sobre colisões de hash Não
deixe de
conferir nossa próxima lição para praticar com o HashMaps.
10. Prática de mapeamento: Bem-vindo à prática da estrutura de
dados de mapeamentos. Aqui, novamente,
praticaremos mais exercícios e examinaremos algumas dicas de entrevistas relacionadas à estrutura de
dados de mapeamento. Em particular, essas estruturas
de dados também
são chamadas de Hashmaps. Então, usaremos muito esses
nomes, Hashmaps. Assim como antes, navegue
até este URL
alvinwan.com/datastructures101/mappings. Isso o levará a repl.it. Sei que já falamos sobre essas instruções
várias vezes. Vou repassar isso
mais uma
vez, caso você veja esta página, vez, caso você veja esta página, bifurque o projeto para obter
sua própria cópia editável. Clique no nome do projeto no canto superior esquerdo para abrir uma lista suspensa. Clique nas reticências para
obter outra lista suspensa
e, em seguida, clique
no botão “Bifurcar”. Então, sugiro colocar
o Skillshare e as janelas
repl.it
lado a lado, conforme mostrado aqui. Você deve então ver
algo
parecido com o que você tem
no lado direito. Então, vamos agora falar sobre os tipos de exercícios
que você verá. Você terá os exercícios de implementação, uso e combinação. Se você rolar para baixo,
verá que nosso primeiro exercício aqui é implementar uma pilha. Vamos fazer
isso em três etapas, assim como fizemos em
todas as outras aulas. Primeiro, projetaremos o algoritmo sem nenhum código. Vamos relatar o
tempo de execução e a complexidade da memória. Então, vamos realmente
codificar o algoritmo. Vamos aplicar essas três etapas ao
primeiro algoritmo ou ao nosso primeiro exercício aqui. Implemente uma pilha que limite todos os valores na pilha a
apenas três ocorrências. Se estiver sendo
enviado um valor com
mais de três ocorrências, simplesmente ignore esse valor. Então, neste caso específico, temos um exemplo aqui. Inicializamos uma pilha
primeiro e depois
aumentamos o valor um, 10 vezes. No entanto, somente os
primeiros três valores são realmente adicionados à pilha. Todo o resto é ignorado. Você pode então enviar outros
valores diferentes um e eles serão adicionados
à pilha normalmente. Vá em frente e experimente isso. Primeiro, crie o algoritmo
que realmente
implementará essa
pilha com um limite. Pause o vídeo aqui e
tente descobrir um algoritmo. Aqui está a solução
algorítmicamente. O que vamos
fazer é
usar primeiro a
implementação da pilha básica. Então você pode ver aqui que
minha classe de pilha limitada na verdade herda
da classe de pilha base. Sabendo disso,
vamos impor restrições sobre quando você pode realmente empurrar para uma
pilha, e pronto. Para fazer isso, vamos
manter um HashMap, mapeando todos os valores para
suas contagens na pilha. Sempre que você pressionar, você
incrementará esse valor. Se esse valor exceder o limite, simplesmente
ignoraremos o valor
e, em seguida, pop realmente se
certificará de
diminuir essa contagem. No push, você verifica a contagem, adiciona se a contagem estiver correta
e, em seguida, incrementa a contagem. No pop, você diminui a contagem. Então esse é o algoritmo. Agora, vamos discutir o tempo de execução
e a complexidade da memória. Pause o vídeo aqui e veja
se você consegue descobrir. Para a complexidade do tempo de execução, é qualquer que fosse a complexidade do algoritmo original. Nesse caso específico, push é linear e pop é a forma como o
implementamos, também linear. Portanto, tanto push quanto pop
são operações lineares. Agora, para a complexidade real da
memória,
então, o que isso parece? Bem, temos que criar
um novo valor aqui. Não é exatamente o
de n. Temos um valor adicionado ao
HashMap para cada novo valor, mas isso não é tanto quanto o número total de
valores que adicionamos. Temos apenas o número de valores
exclusivos em nosso HashMap. Precisamos inventar uma nova carta. Em vez de o de n, diremos que
é o de k, por exemplo, e definiremos k
como o número de valores
exclusivos que
foram adicionados à pilha. Se você realmente tivesse
isso em uma entrevista, diria
algo assim. Na verdade, precisamos
definir uma nova variável, k, onde k é o número
de valores exclusivos, e nosso algoritmo, nossa complexidade de memória para
nosso algoritmo é o de. Isso é tudo devido à complexidade. Vamos agora passar para o código. Então, pause o vídeo
aqui e tente codificar. No construtor,
vamos
inicializar um novo contador. De coleções,
importação, padrão, dict. Esse é um
tipo diferente de dicionário. O que esse dicionário
faz é se você acessar uma chave que não
tem um valor atual, ele inicializará esse
valor usando essa função. Nesse caso específico, para esse contador, se digamos que
acessamos o contador 0, 0 atualmente não é uma
chave válida para esse dicionário, então ele o inicializará
com essa função int. O padrão para a função
int é zero. Por padrão, o contador próprio
de 0 me dará 0. De fato,
autocontador de qualquer coisa, também me dará 0. É assim que esse
dicionário padrão funciona, e isso fará com que parte
do código pareça um
pouco mais simples. Agora que eu entendi isso, vamos agora implementar a função push. Como dissemos antes,
a primeira coisa que
vamos fazer é verificar se a contagem atual
está abaixo do limite. Se estiver abaixo do limite,
prosseguiremos. Se estiver abaixo do limite
, na verdade
incrementaremos a contagem e a
colocaremos na pilha. No pop, tudo o que faremos é
simplesmente diminuir a contagem. Aqui, primeiro encontraremos o valor. Aqui, vamos sair da pilha
e, quando retirarmos esse valor diminuiremos a
contagem desse valor
e, em seguida, retornaremos o valor. Vamos agora ver se nossos testes de
cap stack são aprovados. No topo, aperte o
botão verde e pronto, cap snack agora não está mais
na lista de falhas, então passamos nesse teste. Vamos passar para
a próxima pergunta. Uma dica é que os Hashmaps são ideais para dados
com IDs exclusivos. Nesse caso específico, sabemos que cada valor, ou a premissa do
problema, é que estamos controlando se devemos ou não
empurrar para a pilha
pelo valor. Portanto, o valor em si
é o ID exclusivo. Como temos esse ID exclusivo, Hashmaps foram perfeitos
para esse problema. No entanto, os Hashmaps são os
piores para dados ordenados. Se houver uma relação
entre seus dados, digamos que eu tenha uma sequência
de números, de um até 10, e preciso saber
essa ordem. Ou outra forma de
dizer isso seria, digamos que eu tenha 10 valores e
os insira em
uma estrutura de dados. Se eu precisar me lembrar da
ordem em que o inseri, Hashmaps não são a estrutura de
dados a ser usada, porque os Hashmaps esquecem
toda a ordem. Tudo o que eles fazem é manter um
mapeamento das chaves aos valores. Eles não se lembram de
nada sobre a ordem em
que você
insere as chaves. Então, isso é importante. hashmaps são ideais para
dados com IDs exclusivos, mas não são tão bons para dados em que fazer pedidos
é importante. Para nossa próxima pergunta, role para baixo para ver
a próxima pergunta. Retorna um histograma de todas as letras exclusivas e
seus números de ocorrências. Acho que isso deveria
ter acontecido primeiro. Esse é um subconjunto
do problema anterior. De qualquer forma, pause o vídeo aqui e veja se você consegue
descobrir o algoritmo. Conceitualmente, a solução é que
inicializaremos um
HashMap como um contador
e, sempre que
fizermos uma iteração sobre a string, e para cada novo valor, acessaremos nosso contador. Se já
vimos esse valor, adicionaremos
um à contagem. Se não tivermos visto
esse valor antes, inicializaremos a contagem para um. Então esse é o algoritmo. Qual é o tempo de execução
e a complexidade da memória? pausa no vídeo aqui.
Aqui está a resposta. A
complexidade do tempo de execução é linear. Temos que repetir cada letra
da string. Não há como contornar isso. A segunda, a complexidade da
memória. Novamente, precisamos inventar
uma variável totalmente nova. Essa variável é o
número de valores exclusivos, digamos k. Esse
algoritmo é o de k, onde k é o número de valores
exclusivos que
estão na string. Isso é tudo para a série
combinada, vamos agora tentar codificá-la. Pause o vídeo aqui
e experimente o código. Agora, vamos abordar a
solução em código. Aqui vamos
criar um contador. Esse contador será um dicionário. Na verdade, o que vou fazer é usar o
dicionário padrão de antes. Dessa forma, o dicionário
inicializa em zero. Aqui teremos de
collections, import, defaultdict. Então, aqui, para cada
letra da string, vamos incrementar
a contagem correspondente. Aqui vamos
incrementar a contagem correspondente e,
finalmente, retornar o contador. Agora, eu também quero
mostrar a implementação sem esse dict padrão. Vamos supor que você
não usou o defaultdict. Vamos supor que você acabou de
criar um dicionário normal. Então, aqui verificaríamos se
a carta está no balcão. Se já vimos
essa letra antes
, simplesmente
aumentaremos em um. Se não vimos isso antes, então vamos inicializá-lo em um. contra-letra é igual a um. Vamos agora
executar isso para verificar se exclusivo agora é um
teste aprovado. Lá vamos nós. Unique agora passou em
todos os seus testes. Também concluímos
esse exercício. Vamos agora passar para
o próximo exercício. Uma dica é garantir que sua chave
exista antes de acessá-la. Fizemos isso aqui mesmo. Na linha 103, verificamos se a carta estava
no contador. Em outras palavras, se
tivéssemos visto essa carta antes e já houvesse
uma chave válida em nosso mapeamento. Então, sabendo disso,
vamos passar para a pergunta que vem depois. Usando nossa estrutura de dados para encontrar o valor mais frequente em
uma lista de números inteiros. Eu especifiquei números inteiros para tornar isso um
pouco mais simples. Mas há várias perguntas que você gostaria de fazer ao
seu entrevistador. A primeira pergunta seria: se eles não tivessem especificado
os números inteiros, provavelmente não o fariam. Eles
provavelmente diriam números. Então você gostaria de perguntar: pode haver valores negativos? Pode haver valores decimais? Quais são os intervalos? Qual é o conjunto de
valores possíveis que eu possa ver? A segunda pergunta
que você gostaria de
fazer é: e se houver um empate? Que a pergunta em si
não está bem definida
se houver um empate. Agora, em caso de empate
na descrição do problema,
reporte qualquer um dos números empatados com a maior frequência. Isso geralmente é o que vai acontecer. Mas essas são boas
perguntas a serem feitas e fornecem alguns
pontos interessantes em sua entrevista. Nesta questão específica, temos uma lista de números, e eu quero descobrir qual é
o mais frequente, pausar o vídeo aqui e
ver se você consegue descobrir o algoritmo.
Aqui está a solução. Vamos fazer algo
muito parecido com o de antes. Vamos usar um HashMap para realmente armazenar as contagens cada valor em nossa lista. Depois de obter esse contador, usaremos o
contador para
descobrir qual foi o melhor. Essa seria uma maneira de fazer isso. Outra forma de fazer isso que não exige
duas passagens dos dados,
seria, na verdade,
ao adicionar ao contador, manter uma variável que represente
o valor mais frequente. Se você ver um valor que, de
repente, tem mais instâncias,
substitua essa variável. Você verá isso em
ação em apenas um segundo. Mas, conceitualmente, a ideia
principal é manter um contador de todos
os valores exclusivos e depois usar esse contador. Agora que conhecemos o algoritmo, pause o vídeo aqui e veja se você consegue
descobrir o tempo de execução e complexidade da
memória.
Aqui está a resposta. Assim como antes,
temos exatamente a mesma complexidade de memória de tempo de execução e as funções anteriores. complexidade do tempo de execução será linear. Você precisa percorrer cada item da lista. Não há como contornar isso. O segundo é O de k, onde k é o número
de valores exclusivos. Acho que isso
está se tornando um motivo agora. Mas pelo menos para
esses exercícios, O de k é a
vez correta, então tenha isso em mente. É linear no
número de valores exclusivos. Agora que abordamos
a complexidade, abordamos o algoritmo, pausamos o vídeo aqui
e testamos o código. Aqui está a solução. Vamos escrever isso agora. Vamos
começar com contador
e contador será um dicionário vazio. O maior valor será nenhum, digamos assim. Para o valor em números, vamos verificar se o
valor está no contador. Se já vimos esse valor antes,
na verdade, vou mudar
isso um pouco. Se o valor não estiver
no contador
, inicializaremos
isso para zero. Independentemente de qual
seja seu valor, aumentaremos em um. Se o contador for
maior que o maior valor, então se a contagem atual for maior do que a maior contagem, reatribuiremos
e, em seguida, retornaremos
o maior valor. Antes de executar essa função, você deve ter em mente
algo que é, bem, uma das táticas
que abordarei em um curso futuro é que você deve sempre executar
virtualmente seu código. O que quero dizer com isso
é apenas executar o código na sua cabeça como se você
fosse o intérprete. Se você detectar algum bug
antes de executar o código, isso geralmente é outro ponto
limite para você. Nesse caso em particular, veríamos um erro aqui por causa do
contra-maior. O melhor aqui é
nenhum e nenhum ainda não
existe no balcão. Isso remonta à
nossa dica anterior: sempre certifique-se de que a chave exista antes de
tentar acessá-la. Nesse caso específico, vou adicionar a chave
none aqui e
defini-la como menos um. Dessa forma, todos os
outros valores com uma contagem serão
maiores do que esse. Logo na primeira iteração, substitua o maior valor
pelo valor atual. Isso é tudo para essa função. Agora, vamos tentar executar os
testes e garantir que mais frequente não
apareça mais como um teste reprovado. Clique no
botão verde “Executar” na parte superior. Aí está você. Agora você pode ver que o mais frequente não é mais
um teste reprovado. Aqui, queremos
considerar uma entrada vazia. Há um caso
aqui em que você pode ter algo estranho
acontecendo se passasse uma lista vazia
para a mais frequente, então você simplesmente não
recuperaria nenhuma, o que é um padrão razoável. Mas você deve apenas garantir
que sua função não seja
interrompida se você receber uma entrada vazia. Nesse caso, nossa função
não é interrompida. Não retorna nenhum. Portanto, desde
que declaremos que a função não
retornará nenhum
após uma entrada vazia
, isso é perfeitamente válido. Para nossa próxima pergunta. Este é bastante
desafiador conceitualmente. Vamos usar
uma estrutura de dados ou qualquer estrutura de dados para
classificar várias viagens. Várias etapas são formatadas
como origem e destino. Você pode pensar nelas como cidades
de origem e destino. Quando tivermos isso, queremos
computar o caminho completo. Queremos encontrar a posição inicial
real
e a posição final real ou
final. Você pode supor, por
enquanto, que há apenas um caminho e que
há um caminho como completo. Isso significa que não
há lacunas. Nunca acabe em
uma
posição aleatória no meio com várias etapas não relacionadas
e não haja ciclos. Você nunca vai voltar de
um para dois para um. Se você passar de um para dois, você sempre
passará para três, quatro, e assim por diante. Seu objetivo é imprimir
a sequência de etapas em ordem da primeira à última. Aqui temos várias etapas. Passamos de três para dois, um para três e dois para cinco. Seu objetivo é descobrir qual é
a sequência correta
de etapas. Aqui aqui, a
sequência correta é de um a três, depois três a dois,
depois dois a cinco. Pause o vídeo aqui, veja quais estruturas de dados você deseja usar e como as usaria. Aqui está a solução.
Conceitualmente, o que vamos fazer é primeiro descobrir qual é a posição
inicial definitiva. Para fazer isso,
vamos
criar um conjunto de Hashmaps. Esses Hashmaps serão
mapeados do destino
até a origem. Então, o que
faremos é começar de qualquer destino arbitrário. A partir desse destino,
verificaremos se a fonte
está no HashMap? A fonte atual é
outro destino de etapas? Se sim, então vamos para as etapas de destino e origem, e você continua fazendo isso. Digamos, por exemplo, que comecemos de dois e depois digamos: é três em nosso mapeamento? É, três está em nosso mapeamento. Vamos pesquisar a fonte
correspondente. Um, está em nosso mapeamento? Não, não está em nosso mapeamento. Então, isso significa que uma é a posição inicial definitiva. É isso que vamos fazer. Vamos criar um
mapeamento do destino à origem. Então
vamos continuar percorrendo isso até chegarmos
à fonte definitiva. Depois de chegar lá,
esse é o primeiro passo. Nós temos a fonte
definitiva. Agora precisamos realmente
imprimir essa série de etapas. Precisamos voltar para trás,
precisamos começar
da fonte e continuar atravessando. Vamos começar de um,
vamos para três, depois vamos procurar três. Vemos três, depois vamos para dois. Procuramos dois, dois estão aqui.
Então continuamos fazendo isso. Você continua atravessando
na direção para frente. Você precisa de um conjunto de Hashmaps que forneça a direção inversa. Em seguida, você precisa
configurar o HashMap que fornece a direção para frente. Nós vamos fazer isso.
Vou criar dois Hashmaps. Um HashMap sempre vincula
do destino à fonte. Sempre se vincula da
origem ao destino, então esse é o nosso algoritmo. Agora, qual é o tempo de execução e complexidade da
memória?
Faça uma pausa no vídeo aqui. Aqui está a resposta.
Nossa complexidade de memória é linear no
número de etapas, porque para cada
etapa a adicionamos a esses
dois Hashmaps ou a
ambos os dicionários. Agora, para nossa
complexidade de tempo de execução, a mesma coisa. É linear no número
de etapas porque precisamos
acessar cada uma
dessas etapas pelo menos uma vez
e, felizmente, para nós apenas uma vez. Sabendo disso, vamos agora realmente escrever a
função, o código. Pause o vídeo aqui
e experimente o código. Vamos agora abordar a solução. Aqui vamos inicializar dois Hashmaps ou
dois dicionários. Um vai estar para frente, outro vai estar para trás. Para cada
par de origem e destino em nossas etapas, vamos preencher
os dois. O mapeamento direto irá
da origem ao destino. O mapeamento retroativo irá
do destino à origem. Agora que preenchemos esses
dois mapeamentos, vamos passar de
qualquer fonte
arbitrária até
a fonte definitiva. Enquanto a fonte está invertida, acho que isso
não está claro, mas aqui vou
deixar claro. Aqui teremos a fonte
igual à primeira etapa
e, em seguida, será
a fonte da primeira etapa. Enquanto a fonte estiver ao contrário,
continuaremos atravessando. Quando esse loop é concluído, a fonte não está mais no mapeamento inverso,
o que significa que
a fonte é a fonte definitiva, o primeiro lugar que
visitamos. Então, desde que a fonte esteja
no dicionário direto ou
no mapeamento direto
, nós a imprimiremos. Aqui, vamos usar strings
f em Python. Você pode imprimir isso da maneira que
quiser e, em seguida,
percorreremos esse caminho. Enquanto nossa fonte estiver
no mapeamento direto, acessaremos esse item
no mapeamento direto
para seu destino. É basicamente isso. Vamos agora executar essa função
e garantir que passamos essa função, obtenhamos o caminho dos testes. Pronto,
temos apenas um conjunto de testes
reprovados que estão
em outra função, então
passamos com sucesso neste exercício. Não vamos falar sobre
essa questão de desafio. Essa questão também é
bastante difícil, então vamos falar
sobre ela apenas de forma algorítmica, não
vamos
realmente codificá-la. Novamente, escrevi
soluções para você, no entanto, simplesmente não
falaremos sobre o código aqui. Eu anotei cada linha nas soluções para
que você possa examiná-la e entendê-la, e a parte mais importante aqui,
porém, é o algoritmo. Para esse problema, vamos criar
um dicionário com
um tamanho máximo que funcione como um dinheiro usado pelo menos recentemente. Neste dicionário,
sempre que você inserir, atualizar ou acessar uma chave, isso conta como o uso dessa chave, e se o dicionário tiver mais chaves do que o tamanho máximo, você descartará as menos
recentemente chave usada. Vamos ver um exemplo disso. Digamos que eu tenha esse
novo dicionário e insira o Valor
1 com a chave a,
então vamos dar uma olhada nas chaves aqui, os valores não
importam muito. Inserimos um valor para a chave e depois inserimos
um valor para a chave b. Nesse
ponto, b é o valor usado mais recentemente e 1 é o valor usado menos
recentemente. No entanto, aqui eu acesso a. Agora a se torna o valor usado mais
recentemente , aqui nós o trocamos. Um corresponde a a, então a é o usado mais recentemente e o outro valor é usado
menos recentemente. Agora atribuímos um novo valor
à chave c e você
notará que, neste momento, b foi o valor menos
usado recentemente aqui, então b foi descartado e agora
só temos a e c restantes. Nesse dicionário específico, o tamanho máximo era dois. Agora, foi assim que realmente vimos uma das chaves ser derrubada. Lembre-se de que
sempre que você acessa, atualiza ou insere
um valor para uma chave que conta como acesso
ou uso desse valor, e sempre que você insere se
exceder o tamanho máximo, você perde o menos
recentemente valor usado. Sabendo de tudo isso,
vamos agora
pensar em como projetar
isso de forma algorítmica. Pause o vídeo aqui e veja se você consegue criar
um algoritmo. Aqui está a solução. Para realmente implementar
esse cache, o que vamos fazer é manter na verdade, uma lista duplamente vinculada. Antes de falarmos sobre
uma lista vinculada, uma lista vinculada mantém um
link para o próximo link, então você teria uma aparência
parecida com esta. Você teria um vinculado
a dois, vinculado a três. No entanto, uma lista duplamente vinculada na verdade inclui
ambas as direções, três sabem que seu valor
anterior é
dois, dois sabem que seu valor
anterior é um. A razão pela qual você deseja
essa lista duplamente vinculada é porque queremos que
a lista vinculada acompanhe o pedido entre todos os nossos dados e
esse pedido
nos dirá que o usado mais recentemente e os valores
usados menos recentemente são. Felizmente, com uma lista vinculada, é muito fácil
inserir um valor e remover um
valor por vez. Ambas são operações
em tempo constante. Observe que isso não é
verdade para uma matriz. Em uma matriz, se você
quiser se mover, digamos três.
Digamos que tivéssemos isso. Digamos que tivéssemos 1, 2, 3, 4, 5 e digamos que cinco agora seja o valor usado mais
recentemente. Sua nova lista teria que
ser 5, 1, 2, 3, 4. Com uma lista com links duplos,
essa é uma operação de tempo constante, tudo o que você faz é reatribuir as conexões, como
falamos antes. No entanto, para uma matriz, você teria que realmente
copiar a posição de 1-2, 2-3, 3-4, 4-5 e, em seguida, copiar
cinco até o início. Você precisaria fazer n cópias, n operações
para reorganizar essa lista. No entanto, com uma lista com
links duplos, você não precisa
fazer nada disso. É uma operação em tempo constante. É por isso que queremos uma lista com
links duplos para combinar com nosso mapeamento ou um HashMap para implementar esse cache
menos usado recentemente. Sabendo que queremos
uma lista com links duplos, como vamos
realmente usá-la? Vamos falar sobre as duas
funções que realmente precisamos. Temos duas funções diferentes. Na verdade, não vou detalhar
totalmente essas funções, mas vou adicionar um
pseudo código aqui apenas para que você
saiba como seria a estrutura geral do código. Aqui, teríamos
a capacidade de obter um item e
também teríamos outra função aqui que nos daria a
capacidade de definir um item. A ideia básica aqui é que, por baixo
dessas duas funções, atualizaríamos a chave, diríamos algo como, criar a chave mais recente e, em
seguida, a mesma coisa aqui. Também criaremos a chave mais recente, e é basicamente isso
para a lógica de alto nível. A maior parte do âmago da questão
teria ocorrido aqui. Na
função tornar mais recente aqui, você realmente faria
toda a reatribuição necessária para
remover um item
da lista vinculada e
, em seguida, reinseri-lo logo
no início
e é isso. Essa é a
solução conceitual para esse problema. Você usaria uma lista
com links duplos e também usaria um mapa. Isso parece bastante complexo, não
vou codificar, pelo
menos não aqui na lição. Eu já escrevi
as soluções e elas
estarão disponíveis para você com um código totalmente
anotado. No entanto, a parte mais importante dessa pergunta foi criar o uso da lista
com
links duplos. Haverá
algumas perguntas como essa em suas entrevistas, nas
quais você precisará
criar uma nova combinação de diferentes estruturas de dados para
atingir seus objetivos. Nesse caso específico, queríamos um cache usado pelo menos
recentemente e queremos que ele
seja muito eficiente uso dessa lista de links duplos nos
permite manter essa
função eficiente. Isso nos leva à nossa segunda
parte da questão. Qual é o tempo de execução e complexidade
da
memória do nosso algoritmo? Em particular, qual é
o tempo de execução que sua
memória tem a complexidade de inserir e, em seguida,
acessar um valor? Pause o vídeo aqui
e aqui está a solução. Obter o valor
é bem simples. Obter o valor em si, apenas acessar algum valor em um HashMap, é uma coisa só,
é tempo constante. Mas a verdadeira questão é: quanto tempo é necessário para
atualizar o valor mais recente? Porque isso envolve
remover e inserir novamente em uma lista
com links duplos. Bem, felizmente, a inserção e exclusão de uma
lista vinculada é tempo constante. Diante disso, sabemos
que esse algoritmo, essa estrutura de dados é um tempo
constante de
acesso. Isso é ótimo. Mantivemos
a eficiência de um HashMap e agora, o que
dizer da atribuição? O que está atualizando este HashMap? Bem, felizmente, esse
também é um tempo constante. É hora constante de atualizar
um HashMap em si e, novamente, para tornar esse
par de chave e valor o mais recente. Essa operação em si
é novamente um tempo constante, assim como
falamos anteriormente. Como essa operação de
tempo constante, tornar algo
o mais recente é apenas inserir e remover
de uma lista com links duplos. Tudo isso para dizer, criamos uma boa combinação de estruturas de dados para
manter o tempo, a
inserção e o acesso
constantes a uma estrutura de dados. Isso é o mais eficiente
que você pode obter. Acho que a conclusão
aqui é que conhecer as
estruturas de dados corretas pode realmente significar uma diferença de ordem de
magnitude, uma
diferença de ordem de crescimento entre uma implementação que é
eficiente e ineficiente. Nesse caso, usar uma
lista com links duplos foi o que nos proporcionou uma eficiência e essa é uma habilidade
útil para entrevistas, talvez menos para o trabalho, mas se você tivesse um sistema de
produção massivo, se você tivesse um aplicativo
crítico do sistema que estava usando estruturas de
dados ineficientes, então você teria
a oportunidade de
criar um grande impacto nos
negócios. Isso é tudo para este exercício. Novamente, para acessar todos esses slides aproximados
de todas as soluções, certifique-se de acessar
o site do curso. Finalmente, isso
conclui a lição prática de mapeamento de
barras do HashMap .
11. Árvores: largura x profundidade: Nesta lição, discutiremos uma forma de armazenar dados
hierarquicamente. Uma estrutura de dados chamada árvore. Explicaremos como uma árvore funciona, como atravessá-la, como organizar uma árvore, o
que significa tempo (longo). Por fim,
discutiremos os prós e os contras dessa nova estrutura de dados. Vamos começar com o que é uma árvore. Uma árvore consiste em um nó raiz. Esse nó raiz tem
dois nós filhos. Cada um desses nós então tem mais
dois nós filhos cada. Essa estrutura é
o que chamamos de árvore. Na verdade, como cada
nó tem dois filhos, nós o chamamos de árvore binária. Digamos que você queira pesquisar um valor ou
modifique essa árvore, precisamos saber como
atravessar uma árvore. Aqui estão duas
maneiras diferentes de conseguir isso. O primeiro método é chamado de
Breadth First Traversal, ou BFS, para abreviar. No BFS, atravessamos os nós da esquerda para a direita, nível por nível. Primeiro, acessamos três. Terminamos o primeiro nível, então vamos passar
para o próximo nível. Em seguida, acessamos 7, depois 2, terminamos
o segundo nível. Então, vamos passar
para o último nível. Acessamos zero, um, nove e oito. Terminamos o último nível, então terminamos com o BFS. Nossa segunda forma de
percorrer essa árvore
é chamada de Depth-First Traversal, ou DFS, para abreviar. Aqui acessamos
a partir do nó raiz, três, também acessamos sete. Continuamos a nos aprofundar, então acessamos dois. Agora que chegamos a um beco sem saída, voltamos ao sete e exploramos o mais
profundamente possível. Então, acessamos um. Novamente, chegamos a um beco sem saída. Então voltamos para sete,
voltamos para três
e, novamente, exploramos o mais
profundamente possível. Acessamos dois e depois nove.
Chegamos a um beco sem saída. Então volte para dois e
, finalmente, acesse oito. E essas são as duas
maneiras de atravessar uma árvore travessia em
primeiro lugar ou em profundidade. Agora vamos explicar uma forma de
organizar os dados em uma árvore. Isso é chamado de árvore de busca
binária. Observe que
reorganizamos os valores. Em particular,
organizamos neles para que o filho esquerdo seja sempre
menor que o pai. Por exemplo, três aqui é menor que cinco e dois
é menor que três. Também organizamos
esses valores para que o filho certo seja sempre
maior do que o pai. Por exemplo, oito é
maior que cinco. Portanto, a criança certa é sempre maior e a esquerda
é sempre menor. Essa estrutura ordenada nos
permite gerenciar dados com muita eficiência. Digamos que queremos
inserir dados na árvore. Aqui, queremos inserir seis. Para fazer isso, comece
pelo nó raiz cinco. A partir daqui,
procuraremos iterativamente uma casa para seis. Como seis é maior que cinco, sabemos que seis devem
pertencer à direita. Agora temos o valor oito. Como seis é menor que oito, sabemos que seis devem
pertencer à esquerda. Não há nenhum nó aqui, então agora é a casa de seis. Isso conclui o algoritmo
de inserção. Digamos que a profundidade
da árvore seja d, então esse algoritmo leva
até d operações. Como resultado, a inserção
leva O de d tempo para ser executada. Para resumir, a inserção
leva tempo O (d). Agora vamos ver como a
exclusão funciona. Digamos que estamos excluindo
seis mostrados em vermelho. Bem, isso é bem simples. Basta excluir esse nó e
o ponteiro do pai. No entanto, digamos que tenhamos excluído do
meio da árvore. Em particular,
queremos excluir cinco. Vamos tentar o que fizemos da última
vez, apenas cinco. No entanto, agora há
um buraco na árvore. Podemos usar qualquer
criança para preencher
a lacuna, três ou oito. Aqui, usaremos a criança
certa de oito anos. Então, mude oito para cima. No entanto, agora há uma lacuna
onde costumavam existir oito. Para ser consistente, usaremos o filho certo de
oito, nove. Novamente, mude nove para cima. Agora há um todo onde
costumavam estar nove , mas tudo bem. Não há mais crianças. Então, podemos simplesmente excluir
o ponteiro extra. Assim como no algoritmo
anterior. Esse algoritmo leva
até d operações. Portanto, a exclusão leva O do tempo. Para resumir a inserção
e a exclusão de uma árvore de pesquisa binária,
ambas usam o tempo O de d. Nosso objetivo é
buscar o valor seis. Partimos do nó raiz
cinco, como na inserção, comparamos nosso valor desejado seis com o nó cinco atual. Seis é maior que
cinco, então vamos para a direita. Agora acessamos oito. Comparamos, seis é
menor que oito, então vamos para a esquerda. Agora acessamos seis, seis é o valor que
estamos procurando. Então terminamos de pesquisar.
Esse algoritmo pode levar até d operações. Portanto, a pesquisa é O de
d. Para resumir, uma
árvore de pesquisa binária apresenta modificação e acesso de O de d. Observe que em uma árvore
não existe algo como
buscar diretamente o oitavo nó, porque não há uma
ordenação global dos nós e você não sabe onde nenhum
dos nós está na memória. Como resultado, não há análise de tempo de execução de
busca. Isso conclui nossa
análise das árvores. No entanto, temos mais um a fazer. Gostaríamos de traduzir
esses tempos de execução. Todos os nossos tempos de execução são
expressos em função
da profundidade da árvore ou d. Visualizado, aqui está uma árvore e aqui está
a profundidade da árvore. Nesse caso, temos
uma profundidade de quatro. Gostaríamos de expressar
esses tempos de execução em termos de n, o número de nós;
nesse caso, existem 15 nós. Isso ocorre porque os
tempos de execução de todas as nossas estruturas de dados anteriores foram expressos em termos de n, o número de itens. Como resultado, também devemos expressar nossos novos tempos de execução em
n para
garantir que esses tempos de execução sejam
comparáveis. Aqui está a mesma árvore. Vamos tentar entender
a relação entre d e n. Considere
a primeira camada. Isso é a Profundidade 1 com um nó. Considere as duas primeiras camadas. Isso é a Profundidade 2
com três nós. As três primeiras camadas, isso é a Profundidade 3
com sete nós. Considere todas as camadas. Esta é a Profundidade 4 com 15 nós. Pode ser difícil
notar um padrão. Então, em vez de contar
o número de nós, contarei o número
de nós mais um. Agora, se você olhar os números em vermelho,
você vê um padrão? Como você deve ter notado,
o número de vermelhos, número de nós praticamente dobra. Como resultado, podemos
afirmar que n é aproximadamente dois elevado
à potência de d. Agora temos uma
relação matemática entre d e n. Como queremos inserir d
em nossas
complexidades de tempo de execução, vamos resolver para d. Para resolver
para d, primeiro
reescreveremos
a equação depois aplicaremos logaritmos em ambos
os lados. Lembre-se de que, com registros, podemos mover o expoente d para fora do log
como um coeficiente. Então, simplesmente ignoramos
a constante log dois. Então, agora obtemos que o log de n é aproximadamente d. Agora
podemos conectar. Anteriormente, tínhamos esses
tempos de execução expressos em termos de d. Conectar
d é igual a logn. Agora obtemos o OT do login para todos os tempos de execução de modificação e
acesso. Usando essa análise,
vamos agora discutir os prós e os contras das árvores de busca
binárias. As árvores de busca binária em algumas têm tempos de execução
impressionantes,
apenas (logn). Na prática, O de log n é muito próximo de o de
um tempo constante. Por design, as árvores de
busca binárias são ideais para sequências aleatórias. Quanto mais uniformemente
espalhados, melhor. No entanto, as árvores de
busca binárias são as piores para
dados sequenciais, e aqui está o porquê. Digamos que eu tenha uma sequência
de números de 0 a 10. Primeiro, criamos o nó raiz 0, depois respondemos um, depois dois, depois três, depois quatro e depois cinco. A lista continua
e, como você pode ver, temos basicamente
uma linha reta em vez de uma árvore de busca
binária preenchida. Isso significa que agora a
profundidade não é mais log n,
em vez disso, a profundidade é exatamente igual ao
número de nós. Isso significa que todos os nossos algoritmos agora usam O de n ou tempo linear. Então, em resumo, as árvores de busca
binárias são realmente ineficientes
para dados sequenciais. Em resumo,
discutimos o que é uma árvore, travessia em
primeiro lugar versus travessia em
profundidade, o que é uma árvore de busca binária, que significa o O do tempo de log n e alguns prós e contras
das árvores de busca binárias. Para obter uma cópia desses
slides e recursos, não
deixe de conferir
o site do curso. Agora vamos ver essas
estruturas de dados em ação. Na próxima lição,
praticaremos o uso e a implementação
dessas estruturas de dados, abordando nossos dois
objetivos de aprendizado para este curso.
12. Pratique as árvores: Bem-vindo à
aula prática final deste curso. Nesta lição, praticaremos com árvores,
em particular com
a busca por amplitude
versus pesquisa que prioriza a profundidade. Vamos seguir em frente e
começar aqui. Assim como antes, navegue
até alvinwan.com/datastructures101/trees. Nesse link, você verá
algo parecido com isso. Encaminhe o projeto
para obter sua própria cópia, clique no nome do projeto, clique nas reticências e clique na bifurcação. Sugiro colocar seu
Skillshare e a janela de resposta lado a lado para que você possa
codificar enquanto eu estou programando. Você deve então ver uma
tela como esta, vá em frente e role para
baixo e você chegará
ao primeiro exercício aqui chamado bfs ou
breadth-first search. Portanto, uma dica antes de
começarmos é memorizar como realizar pesquisas que priorizam a amplitude
e a profundidade, abreviadas aqui como bfs e dfs, porque
sempre serão as mesmas. Nesse caso específico, não estamos usando uma técnica
chamada recursão. Então, sem recursão, a maneira fazer bfs e dfs sempre é
assim. Sabendo disso, vamos agora tentar
implementar uma pesquisa abrangente. Veja como é
a primeira
travessia de busca de uma árvore. Aqui temos uma
árvore, 1, 2, 3, 4. Deixe-me
ilustrar como isso parece. Aqui você teria um, e então você
teria um filho
aqui que seriam dois, e então você teria outro filho
ali, ou seja, três. Então você também terá
uma árvore como essa. Essa é a aparência daquela
árvore. Você teria basicamente
uma das raízes, o filho esquerdo será dois, e então o filho
esquerdo de dois será três. Então esse é o filho
certo de um. Essa é a aparência da
árvore. Sabendo que essa é a aparência dessa
árvore, aqui está a primeira travessia de
busca. A primeira travessia nos
dará um primeiro, e depois nos dará dois, depois quatro e depois três. É uma travessia e
também é chamada de travessia de
ordem de nível, então aqui estamos basicamente
descendo os níveis de cada vez, 1, 2, 4, 3. Se tivéssemos aqui
cinco, por exemplo, então teríamos 1, 2, 4 ,
3, 5 e assim por diante. Isso é o que parece. Sabendo que isso
agora é a primeira travessia, aqui está uma dica. Pause o vídeo agora e tente esse problema sozinho, se não
quiser a dica. A dica é que você precisará
usar uma das
estruturas de dados sobre as quais falamos antes. Em particular, você
precisará usar uma pilha ou uma fila para fazer isso. Faça uma pausa
no vídeo aqui e tente criar o algoritmo para uma
travessia abrangente. Agora, aqui está a solução. A solução
envolverá o uso de uma fila. O que vamos
fazer é nessa fila, começaremos
adicionando a raiz. Depois de adicionarmos a raiz, o que faremos é pegar
a raiz e colocar todas as
crianças na fila por essa raiz. Depois de fazer isso
, vamos sair da fila. O desenfileiramento
nos dará o primeiro item aqui. Em seguida, vamos colocar na fila
todos os seus filhos. Isso vai ser
três e qualquer outra coisa é filho de dois. Na verdade, uma forma de
fazer isso seria incluir uma visualização. Aqui temos um,
vamos desenfileirar um e adicionaremos todos os
seus filhos de dois e quatro. Em seguida, vamos desenfileirar dois e depois vamos colocar seus filhos
na fila, que são apenas três. Então, digamos que talvez
haja outro, digamos que haja cinco. Aqui teríamos
três e cinco. Então, finalmente pegaríamos nosso. Em seguida, quatro colocávamos na fila
todos os seus filhos, o que não é nada
e assim por diante. A ideia é que você notará que a ordem de desenfileiramento
foi 1, 2, 4. Depois disso, serão três e cinco, que é exatamente o que é bfs. A fila nos dá exatamente a primeira passagem pela
árvore. Sabendo disso, vamos agora ver qual é o tempo de execução na complexidade da memória.
Faça uma pausa no vídeo aqui. Aqui está a solução.
O tempo de execução e a complexidade
da
memória serão o de n. Você pode estar
pensando: o que é n aqui? Bem, n é o número de nós. Isso é importante. Antes, tínhamos esse caso em que definíamos
uma variável por conta própria. Definimos uma variável
como um número de valores
exclusivos que
estão sendo inseridos. Nesse caso, por
padrão para uma árvore, essa variável n será o número
de nós na árvore. Você também pode redefini-lo, você pode redefinir o
n como a altura
da árvore ou você pode defini-lo como outra coisa, mas geralmente, n é o número de
nós na árvore. Sabendo que, ao relatar a
complexidade da memória de tempo de execução
de uma árvore, você deve relatar em termos do número de nós, que para nós será o de n, porque você precisa
atravessar
cada nó, isso é o que é uma
travessia em primeiro lugar e, em segundo lugar, você precisa adicionar todos
esses nós à sua fila. Em algum momento, na verdade,
desculpe, eu menti um pouco, sua fila nunca
excederá a
largura máxima da árvore. Veremos o que
significa largura mais tarde, mas diremos
por enquanto que o de n é a complexidade da memória. Podemos jogar com
essa nuance mais tarde, vou explicar o porquê, há uma resposta melhor. Por enquanto, faça uma pausa no vídeo e tente
codificar isso. Vamos escrever a solução. Aqui vamos
definir uma fila e o primeiro valor da fila será, na verdade, a raiz. Enquanto houver algo
na fila, vamos sair da fila. Então vamos estender,
então, na verdade, vamos nos
enfileirar. Para cada galho
nos galhos da árvore, vamos enfileirar, então enfileire o galho. Então, finalmente,
imprimiremos o valor atual. Isso nos dará uma
travessia pioneira. Vamos agora verificar se
isso passa em nossos testes. Clique no botão
verde Executar, na
parte superior, e você pode ver agora que o bfs não está mais na nossa
lista de funções com falha. Você
passou com sucesso neste teste. Vamos passar para
a próxima pergunta. Na verdade, antes de
passarmos para a próxima pergunta, uma dica é que você
sempre deve usar o novo, espere. Uma das dicas é
que você sempre deve usar uma fila
para percorrer em primeiro lugar. Você viu isso no exemplo aqui. Você viu como usá-lo.
Tenha isso em mente. Praticamente sempre
será assim que você implementa o bfs sem recursão. Falaremos sobre recursão
em um curso futuro. Sabendo disso, vamos agora
implementar uma busca que priorize a profundidade. pesquisa que prioriza a profundidade terá a seguinte
aparência. Digamos que tivéssemos essa árvore e essa árvore tenha praticamente
a mesma estrutura. Na verdade, é uma
estrutura um pouco diferente. Deixe-me desenhar isso para você. Aqui temos a raiz 1. O filho esquerdo terá
2 anos e o filho
esquerdo do 2 terá 3. Então não há
outras crianças aqui. A criança certa vai
ser 4, aqui mesmo. Então, o filho esquerdo
de 4 será 5. Aqui vamos bater. Uma coisa a observar é que eu continuo dizendo que
filho esquerdo e direito é porque geralmente problemas com árvores são construídos em torno de sua
árvore binária, onde você só tem um filho esquerdo
e um direito. Da forma como
implementamos uma árvore aqui, podemos ter ramificações ilimitadas. Você não está limitado
à esquerda e à direita. Tecnicamente falando, 5
não é filho esquerdo de 4, 5 é o único ramo de 4. Acabei de dizer esquerda
e direita por hábito, mas isso realmente não importa. A questão é que aqui está
a aparência aproximada da árvore. Temos 1 na raiz,
os filhos são 2 e 4 e, em
seguida, o único filho de 2 é 3, único filho de
4 é 5. Sabendo disso, atravesse
primeiro a profundidade ou primeiro siga um
desses caminhos. Da forma como o
implementamos, 1 primeiro seguirá
esse caminho aqui
4 e depois desceremos até 5 antes de voltar e
explorar outros caminhos. É assim que será a
travessia que prioriza a profundidade. Ele vai explorar
até uma folha. Novamente, uma folha é um nó
na árvore que não tem
filhos nem galhos. Ele explorará todo o
caminho primeiro e depois
voltará a subir e começará a explorar outras avenidas. É assim que se parece uma
travessia que prioriza a profundidade. Você vê aqui embaixo que vai 1, 4, 5, e então ele vai voltar a subir
e explorar 2 e depois 3. Essa é uma travessia que prioriza a profundidade. Vamos tentar criar
um algoritmo. pausa no vídeo aqui.
Aqui está a solução. Para travessia em profundidade em primeiro lugar, bem, anteriormente
usamos uma fila
para travessia em primeiro lugar. Para uma travessia em profundidade em primeiro lugar,
vamos usar uma pilha. A pilha vai operar de uma
forma muito semelhante. Vamos continuar adicionando
itens à pilha e continuaremos
saindo da pilha. Aqui está o que
vai parecer. Quando eu começar com 1,
vamos estourar 1 e depois
adicionaremos seus filhos 2 e 4. Agora que temos 2 e 4, vamos estourar o
último item que é 4. Em seguida, adicionaremos
seus filhos, que são 5. Então vamos estourar 5. Você pode ver para onde isso está indo. Até agora,
passamos por 1, 4, 5. Quando terminarmos com 5,
vamos estourar 2. Isso nos dará nossa
primeira travessia profunda usando uma pilha. Sabendo que esse é
o algoritmo, vamos falar
sobre a complexidade da memória e do tempo de execução. Qual é o tempo de execução
na complexidade da memória? Pause o vídeo aqui
e aqui está a resposta. A complexidade da memória
aqui será linear no
número de nós. Para a complexidade da memória,
vamos digerir
a complexidade da memória. Para a complexidade computacional,
teremos complexidade computacional
linear porque precisamos iterar em
todos esses nós. mesma ressalva que mencionei antes para a complexidade da memória: na
verdade, não é linear
no número de nós, mas falaremos sobre
isso mais tarde. Agora vamos
tentar codificar essa função. Pause o vídeo aqui
e experimente. Vamos prosseguir e
codificar essa função. Aqui, em
nossa primeira travessia profunda, vamos começar
inicializando uma pilha. Essa pilha terá
nosso nó raiz dentro dela. Em seguida, vamos iterar. Enquanto tivermos
algo na pilha, sairemos da pilha. Então, para cada
ramificação do nosso nó atual. Para a filial nas
principais ramificações atuais, colocaremos essa ramificação em nossa pilha e, em seguida, imprimiremos
nosso valor atual. É basicamente isso para
nossa travessia que prioriza a profundidade. Vamos
verificar se isso funciona. Clique no
botão verde “Executar” na parte superior. Pronto, o dfs não está mais na nossa lista
de falhas, então passamos com sucesso nos testes do dfs. A dica aqui é que você deve usar uma pilha para percorrer a
profundidade em primeiro lugar. Vamos agora passar para
a próxima pergunta. Para cada
nó na árvore, adicione um novo atributo chamado pai que aponte
para seu pai. Aqui, vamos usar bfs
ou dfs para a atribuição dos pais. Esse atributo pai
apontará para o
pai do nó na árvore. Vamos
desenhar aquela árvore novamente. Digamos que temos
essa árvore aqui. Temos aqui 1, e seu único filho tem 2
e 2 tem dois filhos, que são 3 e 4. Vai ficar mais ou
menos assim e não há outras
filiais, só esses caras. Agora que você tem isso, vamos realmente
preencher os pais. Vamos
implementar isso para que cada árvore aqui
volte para sua mãe. Então, 2 apontará para 1, 3 apontará para 2,
4 apontará para 2. Sabendo disso, vamos pensar sobre isso e criar um algoritmo para isso. Faça uma pausa no vídeo aqui. Vamos falar sobre a solução. Para essa pergunta,
na verdade, não importa se você usa bfs ou dfs. Em ambos os casos, você
pode fazer isso funcionar. Basicamente, o algoritmo
será Vamos realizar
alguma travessia ” e,
se você olhar acima, na verdade, iteramos sobre todas as crianças ou
todas as ramificações para obter
sua corrente. nó. Enquanto estiver fazendo
essa iteração, você atualizará essa ramificação para apontar de volta para o
nó atual, que é o pai. Realmente não importa
qual travessia você usa. Esse é o algoritmo
e, na verdade, essa é basicamente
a solução de código. Vá em frente e considere agora qual é a complexidade da memória e do
tempo de execução?
Faça uma pausa no vídeo aqui. Assim como antes, como estamos usando o DFS e o BFS de
forma eficaz, o tempo de execução e a complexidade
computacional são os mesmos de antes. A complexidade computacional é O de N e a complexidade da memória,
por enquanto, é basicamente O de
N. Sabendo disso, vamos
agora testar o código. Pause o vídeo aqui e
experimente primeiro. Agora vamos analisar a solução. Eu vou trapacear um pouco. Na verdade, vou apenas copiar e colar da função
anterior, que já executou o DFS. Vamos
colar isso abaixo. Vou remover
essa declaração de impressão e, em seguida,
atribuirei branch.parent é
igual a atual. É isso mesmo. Vamos verificar se
essa função está correta. Vamos clicar no botão
verde “Executar” na parte superior. Lá vamos nós. Podemos ver agora que
pais populares não estão mais
na lista de testes reprovados. Passamos com sucesso em todos esses testes. Como eu disse antes, BFS, DFS, contanto
que você memorize essa implementação, você verá
isso com muita frequência. Pelo menos sem recursão, isso é o que
vai parecer, então certifique-se de conhecer
essa implementação. Dica anterior sempre considere também uma entrada
vazia. Nesse caso específico, se nossa árvore estivesse vazia
, nossa função falharia porque aqui vamos aparecer, obteremos a
corrente, a corrente não será nenhuma e então vamos para
tentar acessar.branches dele. Novamente, para todas as suas entrevistas e para
todas as suas perguntas, considere o que você
faria com uma contribuição vazia. Nesse caso em particular, deveríamos ter dito que
se a árvore não fosse nenhuma, então simplesmente
não faremos nada, apenas retornaremos. É importante
ter isso em mente. Vamos passar para
a próxima pergunta. Aqui, usaremos o
BFS ou o DFS para calcular o valor máximo em uma árvore
extremamente larga, mas rasa. Vamos seguir em frente e
considerar o seguinte. Considere o que isso significa para
sua escolha de travessia. Qual é a complexidade máxima do
espaço da pesquisa abrangente
ou da pesquisa que prioriza a profundidade
. Vá em frente. Na verdade, isso está relacionado
à nuance sobre a
qual falamos anteriormente. Pause o vídeo aqui e considere primeiro antes
de considerar o algoritmo. Na verdade, enquanto você está
considerando o algoritmo. [RUÍDO] Aqui está a
próxima pergunta. Vamos obter o valor
máximo de uma árvore extremamente larga
, mas rasa. A parte importante dessa
questão é considerar o que uma árvore extremamente larga
, mas rasa ,
faz com seu algoritmo. Por que isso é importante?
O que isso significa para sua escolha
de travessia? Falamos sobre uma
nuance sutil anteriormente sobre a complexidade
de espaço ou memória do seu modo de travessia. Essa pergunta está realmente
focada nisso, para tentar entender o que essa nuance significa
para o seu algoritmo. Pause o vídeo aqui e veja
se você consegue descobrir isso. Qual é a diferença entre árvore
extremamente larga, mas
rasa, versus uma árvore profunda, mas muito estreita, para BFS ou
DFS. Faça uma pausa no vídeo aqui. Aqui está a resposta. Para uma árvore extremamente larga,
mas rasa, você vai querer usar o DFS. O motivo é que o BFS
ou a passagem em primeiro lugar, é a complexidade do espaço ou o número máximo de
itens na fila ou pilha ou qualquer
coleção que você esteja usando será
a largura do árvore. Já para
pesquisa em profundidade ou DFS, o espaço máximo que
usaremos é equivalente
à profundidade da árvore. Se eu tiver uma árvore
extremamente rasa
, convém que o DFS minimize
seu consumo de espaço. Porque se você tem
uma árvore muito rasa, você terá uma
coleção muito pequena a considerar. Sabendo disso, vamos projetar o algoritmo
para obter o valor máximo. Pause o vídeo aqui e
tente criar o algoritmo. Aqui está a solução.
Para o algoritmo, simplesmente
obteremos
o valor máximo sempre
que você atravessar um nó. Sempre que você atravessar um nó, compare o valor desse nó com
o maior valor global. Se seu
valor atual for maior, basta substituí-lo. Isso é muito semelhante
ao exemplo de frequência máxima o qual falamos anteriormente. Nesse caso, estamos
considerando o valor máximo. Agora que consideramos
o algoritmo, consideramos o
modo de travessia, pause o vídeo aqui
e veja se você consegue descobrir complexidade da memória e do
tempo de execução. Aqui está a resposta. Para a complexidade do
tempo de execução ,
novamente, é linear
no número de nós, é O de N. Para a
complexidade da memória, bem, falamos sobre isso antes, é exatamente por isso
que
escolhemos o DFS para esse problema. Sua complexidade espacial ou complexidade de
memória será
a profundidade da árvore. Isso não é exatamente O de N.
Também, pelo menos por enquanto, não está claro exatamente qual seria a
profundidade da árvore. Vamos apenas atribuir
uma nova variável a ela. Vamos dizer que D é
a profundidade da árvore, então nosso algoritmo é o de d. Agora vamos tentar
codificá-lo. Faça uma pausa no vídeo aqui. Agora, como temos uma implementação do
DFS, voltarei a ser preguiçoso. Vou apenas
copiar e colar. Vamos voltar aqui para cima
e, em seguida, copiaremos
essa implementação do DFS, depois vamos
rolar de volta para baixo e colá-la. Agora que temos essa implementação do
DFS, vamos realmente
remover a instrução print. Como dissemos antes, para cada nó
que
considerarmos, atualizaremos
o valor máximo. Digamos que o valor máximo logo
no início seja
apenas o valor das raízes. Então, quando explorarmos
cada nó, vamos calcular
o máximo entre o valor atual e
o maior valor. Finalmente,
retornaremos o valor máximo. Vamos tentar executar essa
função e
garantir que ela passe em todos os testes. Vá em frente e aperte o botão
verde “Executar” na parte superior. Lá vamos nós. Agora podemos ver que obter máximo não está mais
na lista de testes que falharam. Vamos agora passar para
a próxima pergunta. Vamos combinar estruturas de
dados para
calcular a largura da árvore. Vamos agora ver qual é
a largura da árvore. A largura da árvore é o número
máximo de nós em qualquer profundidade ou
nível. Vamos rabiscar essa árvore novamente. Aqui temos um e um tem
um filho, que são apenas dois, e
dois têm dois filhos, que são três e quatro. Aqui temos três, e aqui temos quatro. Essa é a aparência dessa
árvore. A largura dessa
árvore então é duas porque esse nível tem
dois elementos nela. Agora, se tivéssemos
outro aqui, digamos que tivéssemos cinco, e depois tivéssemos
outro,
seis , digamos, então a
largura dessa árvore
seria três porque você tem no máximo três
em um único nível. Sabendo disso,
vamos prosseguir e atualizar. Vamos discutir o algoritmo. Faça uma pausa no vídeo
aqui e veja como você calcularia a largura
dessa árvore. Aqui está uma solução. Felizmente para nós,
temos um modo de travessia que torna muito mais simples calcular
a profundidade,
que será a travessia de
ordem de nível ou BFS. Há duas maneiras de fazer
isso. Uma delas é que você pode usar
outra estrutura
de dados para realmente acompanhar para realmente acompanhar quantos nós
existem em uma determinada profundidade. O segundo é o BFS
modificado para que você atravesse um
nível por vez e
acompanhe basicamente
quando inicia o próximo nível. Essas
são suas duas opções. Esses são dois algoritmos
diferentes. Vamos implementar
a primeira em que usaremos
outra estrutura de dados, quando você usar um mapeamento. Agora que você
falou sobre isso, vamos falar sobre o tempo de execução
e a complexidade da memória. Pause o vídeo aqui e veja
se você consegue descobrir. Aqui está a resposta. Para a complexidade do tempo de execução,
os dois algoritmos independentemente de
qual você escolheu, serão O de N, onde n é o número de nós. Ambas as
complexidades computacionais são lineares no número de nós. Agora, se você decidir buscar
várias estruturas de dados, nas quais você mantém um mapeamento
da profundidade às contagens, essa será uma complexidade espacial
adicional de O de D na profundidade. Você será linear
na profundidade porque está armazenando um valor para
cada profundidade. No entanto, se você usar
o algoritmo em que modifica o BFS no local
, seu algoritmo
seria O de largura. Ambos os algoritmos têm pelo
menos O de largura, porque a linha de base é
exatamente assim que o BFS original funciona. No entanto, o algoritmo adicional usa um
HashMap para armazenar esse mapeamento da profundidade
à contagem será O da largura mais O da profundidade. Vamos implementar
o menos eficiente, que parece retrógrado,
mas eu já implementei o eficiente já
na solução, então você poderá verificar
isso se quiser ver a
implementação mais eficiente. Mas, por enquanto, vou implementar o
menos eficiente. Faça uma pausa
no vídeo aqui e veja se você mesmo consegue criar
o código. Aqui está nossa solução.
Vamos continuar escrevendo. Vamos usar nossa estrutura de dados
favorita aqui. Vamos usar um dicionário
padrão. Vamos começar
inicializando uma fila. Cada item dessa
fila será uma profundidade do nó atual,
além do próprio nó, porque precisamos acompanhar a
profundidade para saber qual
contagem em nosso contador. de
larguras para realmente atualizar. Aqui está nosso contador, larguras, e ele inicializará
todas as larguras em zero. Embora tenhamos algo
na fila, vamos desenfileirar
e, em seguida, atualizar o
dicionário de larguras incrementando
esse valor em um. Finalmente, para cada ramificação, vamos enfileirar a profundidade incrementada em
um e o próprio nó. Sempre que você passar de
pai para filho, aumentaremos
a profundidade em um. Finalmente, retornaremos a largura
máxima que vemos. Isso nos dará
a largura máxima e todas as larguras
que contamos. Vamos agora executar isso
e garantir que ele passe em todos os nossos
testes. Lá vamos nós. A falta de resultados significa que
todos os nossos testes de documentação foram aprovados. Você finalmente concluiu todos os exercícios
desta lição. Para todos esses slides, soluções
completas e mais exercícios
práticos, visite este site. Isso é tudo para nossa
prática para árvores, largura versus profundidade
versus travessia. Você já viu
muitos problemas aqui. Você também viu
muitos problemas em aulas práticas
anteriores. Espero que
tenham sido muito úteis. Vamos agora para
nossa última lição onde vamos encerrar tudo isso.
13. Conclusão: Parabéns por
terminar o curso. Abordamos muitos
tópicos, ordens de crescimento, pilhas e filas, listas vinculadas, mapas de
hash e árvores. Esse foi um curso muito
difícil, com conteúdo e algumas perguntas
realmente brutais. Você concluiu 20
exercícios em profundidade, 20 dicas para entrevistas e praticou o
método de três etapas para resolver quebra-cabeças
repetidamente. Era muito conteúdo e os slides resumidos são
ótimas ferramentas para memorizar. No entanto, a conclusão mais
importante é, na verdade, o processo
de três etapas. No que diz respeito às entrevistas, essa é a chave. Aqui está o processo de três etapas uma única vez: projete
algoritmos sem código, reporte complexidades de tempo de execução e
memória
e, finalmente, codifique o algoritmo. Agora, para realmente solidificar sua compreensão por três
dias após o curso, crie uma
pergunta sobre estrutura de dados todos os dias. Também recomendo que você publique sua pergunta na seção de
discussão. Você só precisa dormir um
pouco pensando em estruturas de dados. Não precisa ser o melhor trabalho da
sua vida. Qualquer pergunta servirá e
publicará na seção de discussão. Eu realmente estou ansioso para
vê-los e pronto. Trabalho fantástico. Este é o
início de sua preparação para a entrevista e você está
em uma base sólida. Confira meu Skillshare para ver
mais cursos sobre ciência de dados, aprendizado
de máquina e outros conceitos
importantes de programação. Para mais preparação para a entrevista, siga-me no Skillshare para
obter mais atualizações, pois abordaremos quebra-cabeças de
codificação
mais usados e truques específicos para entrevistas. Parabéns
mais uma vez por chegar ao final do curso
e até a próxima vez.
Alvin Wan, Research Scientist
