Algoritmos e estruturas de dados
Pretendo usar esse repositório como um playground prático (KATA), bem como um lembrete de alguns algoritmos comuns, simples e poderosos. Onde elegante usarei transdutores de clojure, que são ótimas ferramentas elétricas para processar sequências. Embora este documento possa parecer exaustivo, pretendo usá -lo como uma lista para a qual posso voltar a qualquer momento, quando precisar estudar. Não implementei tudo listado aqui.
Estilo de escrita
O código aqui não é moldado no estilo que eu usaria para codificação profissional. Toda equipe tem alguma cultura e opiniões sobre o estilo de código e é melhor manter essas diretrizes comuns. Além disso, o código é escrito principalmente para ser lido por outras pessoas, ou todos nós codificaríamos a montagem para obter o máximo desempenho se tivéssemos como alvo apenas um leitores de máquinas. Código que escrevo como parte de uma equipe deve ter sido escrito por qualquer outra pessoa nesta equipe.
O código aqui está escrito em programação litiária graças ao EMACS e ao modo de organização. Isso significa que o código escrito no Clojure é derivado dos arquivos de texto que explicam o raciocínio por trás dele. Espero que facilite a leitura.
Python
Preparando -se para um novo problema
./dev-resources/new-problem.sh
--problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups
Veja --help .
Quando o script de inicialização é concluído, um comando sugerido para testes aparecerá no final:
poetry run ptw -- --
src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py
tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py
Interagindo com poesia e pytest
Por exemplo, para assistir aos testes durante o desenvolvimento:
poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip
A pequena dança por perto -- -- provavelmente poderia ser evitada, mas eu prefiro ser muito explícito sobre o que funciona, então mantenho poetry como o argumento frontal mais esquerdo.
Para obter um FlameGraph de memória:
poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin
Para obter um CPU FlameGraph (ou outros gráficos):
poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof
Para executar benchmarks e obter um resumo gráfico:
poetry run pytest --benchmark-only --benchmark-histogram
Lista de estudos
Algoritmos de classificação
- Implemente do zero: classificação de bolhas, classificação de mesclagem, classificação rápida, classificação de heap.
- Dada uma variedade de números inteiros, encontre o Kth Menor Element usando o algoritmo de seleção rápida.
- Implemente o algoritmo de classificação de contagem para classificar uma variedade de números inteiros com uma gama conhecida de valores.
- Resolva o problema da "partição de três vias" usando classificação rápida para classificar com eficiência uma matriz com valores duplicados.
Algoritmos de pesquisa
- Implementar do zero: pesquisa binária (por uma matriz classificada), pesquisa linear.
- Dada uma matriz classificada rotacionada, encontre o elemento de destino usando a pesquisa binária modificada.
Gráfico, árvore e algoritmos de travessia
- Implementar do zero: pesquisa de largura (BFS), Pesquisa Primeira Profundidade (DFS), algoritmo de Dijkstra, algoritmo Bellman-Ford.
- Implementar representações diferentes: matriz de adjacência, lista de adjacência.
- Encontre o caminho mais curto entre dois nós em um gráfico ponderado usando o algoritmo de Dijkstra.
- Implemente uma árvore de pesquisa binária e execute operações básicas como inserção, exclusão e pesquisa.
- Dado um gráfico direcionado, verifique se existe uma rota entre dois nós.
- Encontre o número de componentes conectados em um gráfico não direcionado.
- Implemente a classificação topológica para um gráfico aciclico direcionado (DAG).
- Encontre o ancestral comum mais baixo (LCA) de dois nós em uma árvore binária.
- Dada uma árvore binária, verifique se é uma árvore de pesquisa binária válida (BST).
- Dado um gráfico, encontre todos os componentes fortemente conectados (SCCs) usando o algoritmo de Kosaraju ou o algoritmo de Tarjan.
- Implemente o algoritmo Floyd-Warshall para encontrar os caminhos mais curtos de todos os pares em um gráfico ponderado.
- Dada uma árvore n-ara, faça uma travessia de ordem de nível ou uma traseira de profundidade (por exemplo, pré-venda, pós-ordem).
Programação dinâmica
- Compreendendo o conceito de quebrar um problema em subproblemas menores sobrepostos e usar memórias ou tabulação.
- Resolva o problema clássico de "Fibonacci" usando abordagens de programação recursiva e dinâmica.
- Dado um conjunto de itens com pesos e valores, encontre o valor máximo que pode ser obtido com um determinado peso máximo usando um problema de mochila de 0-1.
Algoritmos gananciosos
- Compreender os problemas em que fazer escolhas ideais localmente leva a uma solução globalmente ótima.
- Implemente uma solução para o "problema de seleção de atividades", onde você precisa selecionar o número máximo de atividades que não se sobrepõem.
- Dado um conjunto de moedas com diferentes denominações e uma quantidade, encontre o número mínimo de moedas necessárias para fazer essa quantidade usando a abordagem gananciosa.
Algoritmos de volta
- Resolva o problema "N-Queens" para colocar N Queens em um tabuleiro de xadrez N × N sem se atacar.
- Implemente um solucionador sudoku para resolver um quebra -cabeça sudoku parcialmente cheio.
Algoritmos de manipulação de string
- Correspondência de string
- Reversão da string
- Verificações de palíndroma
- Dadas duas cordas, verifique se uma é uma permutação do outro.
- Implemente o algoritmo "Rabin-Karp" para encontrar um padrão em um determinado texto.
Algoritmos de manipulação de bits
- Operações bitwise, encontrando o elemento único único em uma matriz.
- Dada uma matriz em que todos os números ocorrem duas vezes, exceto por um número, encontre o único número exclusivo.
- Implemente uma função para contar o número de bits definidos como 1 em um número inteiro.
Dividir e conquistar algoritmos
- Pesquisa binária, encontrando a soma máxima de subarray.
- Implemente o algoritmo Karatsuba para multiplicação rápida de números inteiros grandes.
- Encontre o par mais próximo de pontos entre um conjunto de pontos no espaço 2D usando a abordagem de divisão e conquista.
Algoritmos randomizados
- Embaralhar uma matriz aleatoriamente no local.
- Implemente o algoritmo "selecione randomizado" para encontrar o Kth Menor Element em uma matriz.
Técnica de janela deslizante
- Dada uma matriz de números inteiros, encontre a soma máxima de qualquer subarray contígua do tamanho k.
- Encontre a substring mais longa com os caracteres distintos na maioria dos k em uma determinada string.
Problemas de intervalo
- Dada uma lista de intervalos, mescla intervalos sobrepostos.
- Encontre o número mínimo de salas de reunião necessárias para agendar uma lista de intervalos.
Tenta
- Implementar uma estrutura de dados Trie para pesquisa e recuperação de string eficientes.
- Dada uma lista de palavras, encontre o prefixo comum mais longo usando um trie.
- Implemente um recurso de preenchimento automático usando um trie para um determinado conjunto de palavras.
- Dada uma lista de palavras, encontre todos os pares de palavras, de modo que a concatenação forma um palíndromo.
Hashing
- Implementando funções de hash, técnicas de resolução de colisão e casos de uso.
- Implementar uma tabela de hash com resolução de colisão (por exemplo, encadeamento ou endereçamento aberto).
- Encontre o primeiro caractere não repetido em uma string usando um mapa de hash.
- Implemente o algoritmo Rabin-Karp para correspondência de cordas com vários padrões.
- Encontre a substring mais longa sem repetir caracteres usando um mapa de hash para frequência do caractere.
Pilhas
- Implementando miniários e max-heaps e seus aplicativos (por exemplo, filas prioritárias).
- Implemente um min-heap ou max-heap do zero.
- Dada uma variedade de elementos, encontre o maior elemento KTH usando uma abordagem baseada em heap.
Manipulação da matriz
- Dada uma matriz M × N, gire-a em 90 graus no local.
- Dada uma matriz de 0s e 1s, encontre o maior quadrado de 1s (sub-matriz quadrada de tamanho máximo) e retorne sua área.
Árvores-negras-pretas ou árvores AVL
- Implementar operações de inserção e exclusão para uma árvore em preto vermelho ou uma árvore AVL.
- Execute rotações para equilibrar uma árvore de pesquisa binária desequilibrada.
Implementações da estrutura de dados
- Matrizes e listas: implementando matrizes, listas vinculadas e suas operações.
- Pilhas e filas: implementando estruturas de dados de pilha e fila e suas aplicações.
- Mapas de hash: implementando mapas de hash e compreensão de sua complexidade de tempo.
Ferramentas
Algoritmos e estruturas de dados são expostos por uma API RESTful simples para configurações mais realistas e para testes mais robustos:
(As ferramentas listadas aqui podem ser específicas para alguns idiomas)
