Soluções LeetCode em bom estilo

Este documento fornece uma visão geral abrangente de LeetCode-Solutions-in-Good-Style, um recurso que oferece tutoriais e soluções de vídeo para iniciantes para problemas de algoritmos e estrutura de dados. Ele apresenta uma abordagem estruturada com código claro, explicações detalhadas e se concentra na construção. uma forte compreensão de conceitos fundamentais em vez de codificação competitiva.

Soluções LeetCode em bom estilo

Explicação: Como a maioria dos meus colegas, estudo e resumo ao mesmo tempo. Tentarei compartilhar mais e trazer alguns conhecimentos úteis. Obrigado por seu apoio contínuo.

Olá a todos, este é um tutorial básico sobre "Algoritmos e estruturas de dados". É adequado para alunos com base zero em algoritmos e alunos que mudaram de carreira. Não é adequado para preparação para competições de algoritmos. O ponto que quero transmitir é: escreva código com lógica clara, então o código que escrevo deve ter passado por um pensamento rigoroso. O formato é muito padronizado, sem estilo pessoal, e não vou escrever uma linha em branco ou comentário para reduzir. o número de linhas de código. Aqui está:

Você pode me chamar de weiwei. Farei o meu melhor para responder às perguntas que sei dentro de minha capacidade e tempo permitir. Se você tiver alguma dúvida que não possa ser respondida a tempo, pode ser porque não vi a notificação no site. Você pode me enviar um e-mail para [email protected].

Solução de vídeo que gravei

Comecei a gravar soluções de vídeo em setembro de 2019. No início eu gravava várias vezes o material que queria falar. Agora escreva rascunhos literais ao explicar os pontos de conhecimento. Muitos vídeos foram acumulados, o que na verdade é um pequeno curso sistemático. Agora eles estão listados aqui, espero que possam ser úteis para todos.

0. Como um usuário novato em algoritmo pode usar LeetCode? 【Compartilhando informações úteis】

1. Complexidade do tempo e complexidade do espaço

Este vídeo mencionou que a complexidade do tempo é um conceito assintótico e precisa ser entendido de uma perspectiva dinâmica. E a definição estrita (forma limite) da complexidade do tempo é explicada para que todos possam entender as regras de cálculo da complexidade do tempo. Apontou também: A complexidade do tempo não é o tempo de execução do programa;

2. Pesquisa binária

Este vídeo apresenta como escrever um algoritmo de pesquisa binária Embora haja muitos detalhes sobre a pesquisa binária, desde que dominemos as ideias corretas de resolução de problemas, pratiquemos mais, pensemos diligentemente e façamos mais resumos, o problema da pesquisa binária não existirá. não será mais dificuldade.

O vídeo a seguir explica vários exemplos de questões de pesquisa binária. Nós nos concentramos em analisar o significado da questão e como usar as condições fornecidas na questão para restringir gradualmente o intervalo de pesquisa.

Através da análise da questão 4 do "Likou" (encontrar a mediana de duas matrizes de ordem positiva), apresentamos esta técnica a você: Se as propriedades do elemento alvo que você está procurando forem mais complexas, você pode inverter esta propriedade. e, em seguida, escreva declarações lógicas que possam facilmente reduzir o intervalo do problema.

3. Questões relacionadas à classificação

"Classificação por mesclagem" e "classificação rápida" são algoritmos de classificação muito importantes. Uma compreensão profunda deles é muito útil para compreender o mecanismo operacional das funções "recursivas". ". "Par de ordem reversa" e "Problema da bandeira holandesa (classificação de cores)" também são problemas de algoritmos muito clássicos.

O cálculo de "pares de ordem reversa" é inteiramente baseado na ideia de "classificação por mesclagem".

Na explicação do problema de "classificação de cores", introduzimos "invariantes de loop" para todos. No processo de escrita do código, devemos sempre respeitar a semântica das variáveis ​​utilizadas, "antes da execução do programa" e "durante a execução". permanece inalterado após o "término da execução". Aderir à nossa própria definição de "invariantes de loop" é uma maneira importante de escrevermos o código correto.

"O primeiro número positivo ausente" é um problema de algoritmo clássico. A ideia usada é "hashing no local", que pode ser entendida como uma aplicação especial do algoritmo de "classificação de balde": uma cenoura, um caroço e um balde. Armazene um elemento. Quero enfatizar que o fato de você poder fazer isso está intimamente relacionado ao valor dos elementos do array de entrada.

4. Janela deslizante

O problema da "janela deslizante" é um problema típico resolvido pela aplicação de "invariantes de loop", que testa nossas habilidades de codificação e depuração.

5. Problemas relacionados à pilha

Os problemas resolvidos usando "pilhas" exigem que usemos exemplos específicos para descobrir que resolvê-los coincide com a regra "último a entrar, primeiro a sair":

Dominar as duas questões a seguir é inseparável do estudo de exemplos específicos e do resumo das regras gerais.

Uma das aplicações de "pilha" mais amplamente utilizadas é como suporte de estrutura de dados para "recursão", "travessia em profundidade" e "algoritmo de divisão e conquista".

6. Pesquisa combinada

A estrutura de dados "Union Search Set" raramente é usada em entrevistas. Se você estiver se preparando para uma entrevista de algoritmo, poderá ignorá-la.

7. árvore

Muitos problemas de árvore podem ser resolvidos usando "travessia em profundidade" ou "travessia em largura".

8. Algoritmo de retrocesso

O "algoritmo de retrocesso" é na verdade uma travessia em profundidade da "estrutura em árvore" contida na questão. Ao resolver esse tipo de problema, é importante desenhar um diagrama de estrutura em árvore em um papel de rascunho.

9. Programação dinâmica

10. Travessia em largura e classificação topológica

11. Tabela hash

12. Operações de bits relacionadas

Meu site pessoal e notas de estudo de algoritmo

Grupo WeChat e grupo QQ

Se precisar que amigos trabalhem juntos nas questões, você pode ingressar no grupo WeChat e no grupo QQ.

MeuLeetBook

Aqui está uma promoção para mim. Recentemente lancei meu próprio LeetBook no "LeetBook": Learning Algorithms from Zero (anteriormente conhecido como "Learning Algorithms and Data Structures with" LeetCoin ")", que é principalmente para amigos que mudaram de carreira e mudaram de carreira. base zero. Explicar o conhecimento básico de algoritmos e estruturas de dados.

ilustrar:

Os dois primeiros capítulos do LeetBook (Time Complexity, Binary Search) são gratuitos para leitura. Os capítulos seguintes exigem pagamento para leitura. O preço para não-membros é de 99 yuans e o preço para membros é de 69 yuans. o mesmo que LeetBook Apenas a parte extra, não menos;

Os títulos dos cursos, exemplos, exercícios e repositório de código de suporte do LeetBook (o repositório que você está vendo atualmente) são totalmente públicos. Se você já domina o conteúdo (incluindo exercícios) desenvolvido no LeetBook, não é recomendado comprá-lo;

A energia investida é a mesma de escrever a solução normalmente, exceto que o LeetBook será mais detalhado na confecção dos gráficos. O conteúdo pago é: o tempo e a energia despendidos na confecção dos tutoriais, e a participação da equipe do “Likou” e especialistas na produção e revisão, a experiência de leitura será melhor. Não está descartado que eu costumo escrever mais pontos de conhecimento sobre resolução de problemas do que o LeetBook;

Usuários intermediários e avançados comprem com cautela;

Você pode me consultar sobre o conteúdo do curso no site "Likou" ou em minhas outras contas sociais, ou pode enviar um problema para este armazém. Independentemente de eu adquirir o curso ou não, tentarei o meu melhor para responder às perguntas que conheço (se o tempo permitir e dentro da minha capacidade). Obrigado a todos por seu apoio contínuo para mim. Todos são bem-vindos para se comunicarem comigo se tiverem sugestões e opiniões;

O conhecimento que explico está nos livros que recomendei a todos, nos blogs, soluções de problemas e notas que escrevi. As soluções de problemas publicadas, blogs e notas serão sempre compartilhadas, e enquanto eu tiver tempo e energia, Continuarei fazendo isso. Compartilhando e fazendo perguntas e respostas;

Estou muito grato ao “Likou” por me dar a oportunidade de fazer cursos e me ajudar a realizar um pequeno desejo.

Classificação "Lekou" e diretório de solução de problemas (organizados de acordo com os capítulos do LeetBook, o Capítulo 16 em diante são capítulos atualmente não incluídos no LeetBook)

Nota: As categorias de perguntas correspondem aos capítulos do meu LeetBook.

Capítulo 1 Complexidade de Tempo

Esta parte apresenta o conceito de complexidade de tempo. Você pode assistir ao [Vídeo Explicação], que é totalmente gratuito. Não há exercícios para este capítulo.

Capítulo 2 Pesquisa Binária

Pergunta tipo 1: Encontre subscritos em dois pontos

ilustrar:

prática:

Pergunta tipo 2: Determine um número inteiro com intervalo de dois pontos (resposta de dois pontos)

Pensamento algorítmico: reduzir e conquistar. Se a questão exigir que encontremos um número inteiro, e esse número inteiro tiver um determinado intervalo, podemos estreitar gradualmente o intervalo por meio da pesquisa binária e, finalmente, aproximá-lo de um número.

Pergunta tipo 3: Função discriminante complexa (problema de maximização)

Observação: esse tipo de pergunta é essencialmente a "Pergunta Tipo 2" (resposta de dois pontos), mas pode parecer um pouco confusa quando você a aprende pela primeira vez. Perguntas deste tipo são feitas da mesma maneira. As palavras-chave são "contínuo" e "número inteiro positivo".

Capítulo 3 Algoritmos Básicos de Classificação

Esta parte contém quatro algoritmos básicos de classificação: classificação por seleção, classificação por inserção, classificação por colina e classificação por bolha.

Pergunta "Likou" 912: Solução para matriz classificada: Isso resume alguns pontos-chave e materiais de aprendizagem para classificação de problemas.

Problemas de array podem ser usados ​​como um "campo para iniciantes" em algoritmos, porque esses problemas só podem ser resolvidos com o domínio do conhecimento básico de linguagens de programação. É fácil pensar em soluções para os problemas a seguir, mesmo que você não tenha aprendido estruturas de dados relevantes e conhecimentos de algoritmos.

Ponto de conhecimento: invariantes de loop

Capítulo 4 Algoritmos de classificação avançados (importante)

Esta parte precisa se concentrar no domínio de três algoritmos de classificação avançados: classificação por mesclagem, classificação rápida e classificação por heap.

ilustrar:

Capítulo 5 Classificação Não Comparativa (Opcional)

Esta parte contém três tipos de classificação sem comparação: classificação por contagem, classificação por base e classificação por intervalo. Resolver esses problemas requer a compreensão do conceito de hashing local.

Capítulo 6 Janela deslizante e ponteiros duplos

1. Janela deslizante

Método de escrita de referência da janela deslizante (não é um modelo, não copie como está, é apenas para referência, é mais importante entender a ideia de design do algoritmo):

Lembrete amigável: as perguntas 3 e 76 são perguntas básicas que você deve ser capaz de responder. Depois de compreender completamente as perguntas acima, você poderá responder às seguintes perguntas com mais facilidade.

Perguntas principais:

ilustrar:

prática:

ilustrar:

Pergunta 209: As principais informações fornecidas na pergunta: Todos os elementos da matriz são números inteiros positivos. Há um total de 3 métodos como segue.

Método 1: solução violenta

Método 2: Janela deslizante (analisar as razões pelas quais janelas deslizantes podem ser usadas)

Método 3: Construa o prefixo e a matriz e, em seguida, use a pesquisa binária

Pergunta 438: Igual à pergunta 76;

Questão 567: Igual à questão 76, exceto que o conjunto de sentenças qualificadas é diferente.

2. Ponteiros duplos

O problema do "ponteiro duplo" é na verdade uma otimização do algoritmo ingênuo. Muitas soluções que não atendem ao significado do problema são resolvidas de uma só vez. O mesmo se aplica à técnica da "janela deslizante". É ainda mais importante analisar por que os ponteiros duplos podem ser usados.

O algoritmo de busca binária usado para encontrar subscritos também pode ser considerado uma solução de ponteiro duplo.

Capítulo 7 Lista Vinculada

Uma técnica muito prática para resolver problemas de listas encadeadas é o “desenho”. O mesmo se aplica à análise e explicação de outros problemas algorítmicos (explicando ao entrevistador).

Você pode escrever funções de teste para listas vinculadas para facilitar a depuração. Os métodos de implementação recomendados são: ① Criar uma lista vinculada individualmente por meio de um array ② Imprimir o nó atual e os nós subsequentes com base no nó atual; Esses dois métodos podem nos ajudar de maneira muito conveniente a depurar programas relacionados a listas vinculadas.

Tipo de pergunta 1: problema básico de ponteiro de lista vinculada

Nota: Alguns problemas requerem o uso de "nós principais virtuais" para evitar lógica complexa de discussão de classificação para o primeiro nó da lista vinculada. Vimos essa ideia em arrays, chamados de “sentinelas”.

Use funções recursivas para evitar operações complexas de alteração de variáveis ​​de ponteiro, simplificando a resolução de problemas.

ilustrar:

Pergunta tipo 2: habilidades de ponteiro rápido e lento

Para ser mais preciso, talvez seja melhor chamá-lo de "ponteiro sincronizado".

Usando duas variáveis ​​​​de ponteiro, ambas estão localizadas no primeiro nó da lista vinculada no início. Uma sempre dá apenas um passo de cada vez e a outra sempre dá apenas duas etapas de cada vez, uma na frente e outra no final. de volta, ao mesmo tempo. Desta forma, quando o ponteiro rápido terminar de andar, o ponteiro lento alcançará a posição intermediária da lista vinculada.

O recurso comum para resolver esses problemas é usar duas variáveis ​​de ponteiro para se mover de forma síncrona. Os ponteiros rápidos e lentos movem-se na mesma direção, e a “diferença” entre seus passos é constante. Com base nessa certeza, alguns problemas da lista vinculada podem ser resolvidos. Usar essa ideia também pode resolver os seguintes problemas de listas vinculadas:

ilustrar:

Pergunta tipo três: Projetar estrutura de dados

Capítulo 8 Pilha e Fila

1. Pilha

Pergunta tipo 1: Problemas básicos resolvidos usando a pilha

As seguintes questões são muito básicas e devem ser dominadas:

prática:

Pergunta tipo 2: pilha monótona

Uma pilha monotônica é uma pilha comum, que obedece ao princípio "último a entrar, primeiro a sair" durante o uso, e os elementos da pilha são monotônicos. Os problemas de "pilha monótona" e "fila monótona" geralmente são muito especiais. Basta dominar os exemplos e alguns exercícios.

Experiência: os subscritos geralmente são armazenados em pilhas monotônicas.

ilustrar:

prática:

2. Fila

Pergunta tipo 1: Problemas básicos resolvidos por meio de filas

Todos os problemas resolvidos usando filas de uso de travessia em largura.

Pergunta tipo 2: fila monótona

Uma fila monotônica é apenas uma fila comum. Este problema é encontrado atualmente na fila monotônica no "Likou". A chave é analisar claramente por que o algoritmo projetado torna a fila monotônica. Além disso, há exemplos de utilização de filas monotônicas para otimização no “Problema da Mochila”. Amigos interessados ​​​​podem aprender sobre isso, que é conhecimento de competição.

Experiência: Os subscritos geralmente são armazenados em filas monotônicas.

Capítulo 9 Fila Prioritária

Nota: É necessário entender a implementação de "heap" como uma "fila de prioridade". Isso ajudará a entender os detalhes de codificação de remove() e replace(), para que você seja mais eficaz ao usar o heap.

Aplicação: Selecione dinamicamente o elemento de maior prioridade na fila atual, com foco na compreensão do significado de "dinâmico".

Capítulo 10: Pesquisa Combinada

E confira a [explicação em vídeo] dos pontos de conhecimento na solução em vídeo para a questão 990. Perguntas básicas e comuns incluem:

Perguntas opcionais:

Capítulo 11 Árvores (Árvores Binárias e Árvores Binárias de Pesquisa)

Capítulo 12 Algoritmo de retrocesso

Pergunta tipo 1: problema básico de retrocesso

Através dessas questões, você pode entender a ideia do algoritmo de retrocesso. Os pontos de conhecimento do algoritmo de retrocesso são explicados na solução de vídeo e na solução de texto da questão 46 do "Likou".

Retrocesso é usar travessia em profundidade para pesquisar todas as soluções da árvore (gráfico). A travessia em profundidade tem uma estrutura recursiva óbvia.

Dicas para resolver os seguintes problemas: ① Desenhar, desenhar, desenhar ② Compreender a travessia e a recursão em profundidade ③ Depurar mais, depurar mais;

Pergunta tipo 2: Problema de retrocesso em strings

Pontos principais a serem entendidos: Como a string sempre gera novos caracteres, não há necessidade de redefinir o estado.

Pergunta tipo três: Flood Fill

Pergunta tipo 4: algumas questões do jogo

ilustrar:

Capítulo 13 Programação Dinâmica (Parte 1)

Duas ideias importantes de programação dinâmica:

Duas direções de pensamento em programação dinâmica:

Três condições precisam ser atendidas para resolver o problema usando programação dinâmica:

Dois conceitos importantes de programação dinâmica:

Referência de classificação de perguntas:

Nota: As perguntas típicas abaixo serão adicionadas (2 de dezembro de 2020).

1. Primeiros passos

Compreenda os dois métodos de programação dinâmica: recursão de memória "de cima para baixo" e recursão de memória "de baixo para cima".

2. Subproblemas repetidos

Esta parte requer o uso do "princípio da multiplicação da contagem em etapas" e do "princípio da adição da contagem categórica".

Pergunta 70: Esta é a mesma pergunta dos números de Fibonacci. Os problemas de contagem usarão o princípio da contagem por classificação e o princípio da contagem por etapas.

3. Subestrutura ideal

ilustrar:

Pergunta 377: Observe que a triagem não é um problema de mochila.

4. Sem efeitos colaterais

prática:

A seguir estão alguns problemas clássicos de "programação dinâmica". Por serem tão importantes, essas questões são incluídas em uma categoria separada.

5. Soma máxima do subsegmento

prática:

6. Subsequência crescente mais longa

Nota: A questão 300 é um problema de programação dinâmica muito clássico. A solução de $O(N log N)$ define o estado de acordo com as características do próprio problema e prova que a matriz de estados é uma matriz ordenada, o que reduz a complexidade do tempo.

prática:

7. A substring comum mais longa

8. Intervalo DP e DP particionado

Intervalo DP:

DP particionado:

9. Árvore DP

Capítulo 14 Programação Dinâmica (Parte 2)

1. Problema na mochila

Nove palestras sobre mochilas: https://github.com/tianyicui/pack

("Game Type DP", "State Compression DP", "Digital DP", etc. serão adicionados.)

Outras perguntas

Capítulo 15 Algoritmo Ganancioso

Capítulo 17 Tabelas Hash

Capítulo 18 Somas de Prefixos e Tabelas Hash

Capítulo 19 Travessia em Largura

Alguns problemas com a travessia de árvores em largura e alguns problemas no LeetBook.

Capítulo 20 Algoritmo da Teoria dos Grafos (Árvore Geradora Mínima)

Capítulo 21 Algoritmo da Teoria dos Grafos (Caminho Mais Curto de Fonte Única)

Capítulo 22 Algoritmo de Divisão e Conquista

A ideia de dividir e conquistar (dividir e conquistar) divide um problema maior em vários subproblemas menores do mesmo tipo e, em seguida, resolve esses subproblemas recursivamente. o problema original é obtido.

O algoritmo de dividir e conquistar pode ser executado em paralelo, mas no campo dos algoritmos básicos, o algoritmo de dividir e conquistar é executado de maneira transversal em profundidade.

Algoritmos típicos que aplicam a ideia de dividir e conquistar: classificação por mesclagem, classificação rápida.

Problemas típicos de pensamento de dividir para conquistar: "Pergunta 51 da Espada aponta para a oferta": "Pergunta 51 da Espada aponta para a oferta" 51. Pares de ordem inversa em uma matriz (explicação em vídeo).

Outras perguntas típicas (a serem adicionadas)

Ele continuará a ser atualizado e amigos são bem-vindos para fornecer comentários valiosos!