Gráfico, raramente testado
definição
Nós conectados entre si na forma de uma rede
O termo
Borda: borda, um par de nós
Algoritmo transversal
Amplitude da primeira pesquisa DFS
Primeira pesquisa em profundidade TFS
Relacionado à entrevista
Implementar primeira pesquisa ampla e profunda
Verifique se o gráfico é uma árvore
Conte o número de arestas em um gráfico
Encontre a distância mais curta entre dois vértices
Pilha monótona Pilha monótona raramente é testada
Fila dupla Deque, raramente testada
Union Find raramente é testado
Árvores de segmentos de linha raramente são testadas
Árvore indexada binária de matriz de árvore, BIT, raramente testada
Árvore de dicionário Trie, raramente testada
definição
Também conhecida como: árvore de prefixos, uma estrutura de dados especial semelhante a uma árvore
usar
Muito eficaz na resolução de problemas relacionados a strings
Pesquise uma palavra em um dicionário
Sugestões automáticas em motores de busca
entrevista
Conte o número total de palavras na árvore do dicionário
Imprima todas as palavras armazenadas na árvore do dicionário
Classifique os elementos em uma matriz usando uma árvore de dicionário
Forme palavras de um dicionário usando uma árvore de dicionário
Construir dicionário T9: árvore de dicionário DFS
Tabela hash/Mapa de hash Tabela hash, frequentemente testada
definição
Armazene objetos identificados exclusivamente na forma de pares de valores-chave
Dicionário: uma coleção de pares de valores-chave
Pesquise o valor do objeto usando a chave-chave
HashSet/HashMap em Java, unordered_map em C, dict em Python
Operações suportadas: O(1) Inserir / O(1) Localizar / O(1) Excluir
Como funcionam as tabelas hash
<br>Princípio de funcionamento: Para conjunto. A chave obtém um índice por meio da função hash e então o valor é armazenado no array. <br>Para obter, encontre o índice por meio das funções chave e hash e obtenha o valor.
Por que a complexidade de tempo de várias operações em hash não pode ser simplesmente considerada O(1)?
A chave pode ser uma string, um número inteiro ou algo de comprimento desconhecido. Portanto, é apropriado usar O(L) em sentido estrito, a complexidade de tempo de qualquer operação é O(keySize) em vez de O(1)<br>
Como implementar a função hash
Como resolver colisão de hash (colisão)
Colisão significa que duas chaves diferentes obtêm dois valores idênticos após cálculo pela função hash. Existem duas maneiras principais de resolver conflitos:<br>Hashing aberto. Isso significa que no array no qual a tabela hash se baseia, cada posição é o nó principal de uma lista vinculada. Dessa forma, tuplas <chave, valor> conflitantes são colocadas na mesma lista vinculada. <br>Hashing fechado. Isso significa que quando ocorre um conflito, os elementos subsequentes irão para a próxima posição para encontrar um espaço vazio<br>
Como fazer a tabela hash se expandir continuamente?
fatores de desempenho
Método de tratamento de colisão
entrevista
Encontre pares de valores-chave simétricos em uma matriz
A tabela hash será usada de forma flexível para resolver o problema?
Você é proficiente nos princípios básicos de tabelas hash?
Acompanhe o caminho completo por conveniência
Descubra se um array é um subconjunto de outro array
Verifica se as matrizes fornecidas são disjuntas
526. Balanceador de carga<br>
134. Estratégia de cache LRU<br>657. Inserir Excluir GetRandom O(1)<br>954.
Problemas de classe de fluxo de dados<br>960. Primeiro número exclusivo em um fluxo II<br>138. Copiando uma lista vinculada com ponteiros aleatórios<br>171. 124. sequência contínua mais longa
Classificar pesquisa
organizar
classificação por mesclagem
Encontrar
tabela de pesquisa estática
tabela de pesquisa dinâmica
Definição de estrutura de dados: Uma estrutura de dados pode ser pensada como uma coleção de armazenamento de dados e diversas operações (funções) definidas nesta coleção.
Método de teste 1: Pergunte sobre os princípios básicos de uma determinada estrutura de dados e solicite sua implementação
Exemplo: Fale sobre o princípio do Hash e implemente uma tabela Hash
Método de teste 2: use algum tipo de estrutura de dados para completar as coisas
Exemplo: mesclar matrizes ordenadas K
Método de teste 3: Implemente uma estrutura de dados para fornecer algumas funções específicas
Exemplo: O problema do item K de frequência mais alta
complexidade de tempo:
Descreva a complexidade de tempo de múltiplas interfaces<br>
Por exemplo, você precisa projetar uma estrutura de dados definida
Algoritmo 1:O(n) limite inferior O(1) adicionar
Método de implementação: use armazenamento de array, compare cada vez e insira diretamente no final do array
Algoritmo 2:O(logn) limite inferior O(logn) adicionar
Método de implementação: use armazenamento Red-black Tree, TreeSet em Java, mapa em C
Array Array, mais comumente testado
tipo
Matrizes multidimensionais
submatriz
Questões de entrevista
41. 42,43, Submatriz máxima<br>44. Submatriz mínima<br>138.
Problema de intervalo de array
Questões de entrevista
30. Inserindo intervalos<br>793. Interseção de vários arrays<br>156.
problema de classificação externa
Definição: Algoritmo de classificação externa refere-se a um algoritmo para classificar dados armazenados em um ou mais arquivos grandes quando não há memória suficiente. <br>
Duas etapas básicas:<br>Corte o arquivo grande em vários arquivos pequenos e use a memória para classificá-los respectivamente<br>Use o algoritmo de mesclagem K-way (mesclagem k-way) para classificar vários arquivos pequenos mesclados em um arquivo grande
Questões de entrevista
486. Mesclar K Arrays Classificados<br>104.
Operações de bits
Definição: Operações em bits binários
Questões de entrevista
365. Quantos 1 existem em binário<br>
Matrizes de árvores raramente são consideradas
Também conhecido como: Fenwick Tree Nome em inglês: Binary Indexed Tree Abreviatura: BIT é implementado com base em prefixo e informações<br>
Embora o nome seja Árvore, ele é armazenado em uma matriz (Array)<br>BIT é uma árvore múltipla e o relacionamento pai-filho representa o relacionamento de inclusão<br>Use getPrefixSum(k) para implementar getRangeSum(x, y )
complexidade de tempo
Log(n) Modifica o valor em qualquer posição<br>Log(n) Consulta a soma de qualquer intervalo
Características
Para um array com N números, as seguintes funções são suportadas:<br>update(index, val) //Atualiza o valor em uma posição no array dentro do tempo logN getPrefixSum(k) //Obtém-no dentro do tempo log(K) A soma dos primeiros K números da matriz
Questões de entrevista
817. Variável de soma do elemento da matriz de intervalo<br>249. Conte o número de números anteriores menores que ele mesmo.
Relacionado à entrevista
Encontre o segundo menor elemento em uma matriz
Encontre o primeiro número inteiro não repetido
Reorganizar valores positivos e negativos em uma matriz
65. Mediana de duas matrizes classificadas, problema difícil<br>
6. Mesclar matrizes classificadas II<br>64. Mesclar matrizes classificadas<br>839. Mesclar matrizes classificadas K<br>577. duas matrizes<br>548. Intersecção de duas matrizes II<br>793. Compra e venda de ações esparsas<br>931. tempo<br>405. Submatriz cuja soma é zero<br>944. Submatriz máxima<br>943. Soma de intervalo de variável imutável<br>665.
Stack Stack, nem sempre testado
definição
LIFO. Por exemplo, no carregamento logístico, as mercadorias carregadas posteriormente são descarregadas primeiro.
Operações suportadas: O(1) Push / O(1) Pop / O(1) Top
aplicativo
Usado para travessia não recursiva de árvores binárias, cálculo de expressões polonesas reversas, etc.
A principal estrutura de dados da implementação não recursiva do DFS
Na busca em largura (BFS), os nós a serem expandidos são registrados.
As filas podem ser usadas para implementar filas de mensagens para concluir tarefas assíncronas.
Quando a velocidade de produção e consumo de mensagens é inconsistente, é necessária uma fila de mensagens para armazenar temporariamente as mensagens que foram enviadas, mas não recebidas.
Implementar modo de pilha
Use uma estrutura de armazenamento (matrizes comumente usadas, ocasionalmente listas vinculadas) para armazenar elementos
Usar uma matriz para implementar três pilhas?
Implementar uma pilha usando duas filas? <br>
a diferença
Arrays têm melhor desempenho para acesso aleatório. <br>As listas vinculadas possuem melhor desempenho para inserção e exclusão de elementos.
Exercícios<br>
lintcode: 495. Pilha de implementos
494. Pilha de implementação de fila dupla<br>
224. Use um array para implementar três pilhas<br>
operar
empurre, insira o elemento na parte superior
pop retorna e remove o elemento superior da pilha
isEmptyA pilha está vazia e retorna verdadeiro
top retorna o elemento superior sem removê-lo
Java usa java.util.Stack, que se estende da classe Vector e suporta operações como push(), pop(), peek(), empty() e search().
C, basta usar a pilha em <stack>. O método é semelhante ao Java, exceto que peek() em C é chamado top(), e quando pop(), o valor de retorno está vazio.
Python, use list diretamente, use operações de fatiamento como [-1] para visualizar o topo da pilha, use list.pop() ao abrir o topo da pilha e use list.append() ao empurrar o topo da pilha . <br>
Relacionado à entrevista
Usando a pilha para avaliar expressões postfix
Classifique os elementos da pilha
Determinar se uma expressão está balanceada entre parênteses
QueueQueue, frequentemente testado
definição
Estrutura de dados linear de armazenamento sequencial FIFO, primeiro a entrar, primeiro a sair, caixa de supermercado
Operações suportadas: O(1) Push / O(1) Pop / O(1) Top
aplicativo
Usado como estrutura de dados principal para o algoritmo BFS
operar
Inserir elementos no final da fila de enfileiramento
dequeue remove o elemento principal da fila
A coluna isEmpty está vazia e retorna verdadeiro
top retorna o primeiro elemento da fila
Método para realizar
Implementar fila usando lista vinculada?
Implementar uma fila com duas pilhas? <br>
Implementar fila usando array circular?
Exercício: 955. Implementar fila por matriz circular<br>
entrevista
Use fila para representar a pilha
Inverta os primeiros k elementos da fila
Use uma fila para gerar números binários de 1 a n
642. Média móvel do fluxo de dados<br>
955. Implementar fila por matriz circular<br>
Lista vinculada, frequentemente testada
definição
Cadeia de nós: cada nó contém dados e ponteiros para nós subsequentes
usar
Implementar sistema de arquivos, tabela hash, lista de adjacências
tipo
lista vinculada unilateral
Lista duplamente vinculada
operar
isEmpty, está vazio, retorna verdadeiro
entrevista
Lista vinculada inversamente
Detectar ciclos em listas vinculadas
Retorna o enésimo nó do último na lista vinculada
Remover duplicatas da lista vinculada
ÁrvoreÁrvore
definição
estrutura de dados hierárquica
Composto por vértices e arestas
Não há ciclos na árvore conforme mostrado no gráfico
tipo
As árvores de segmento de linha basicamente não são testadas, elas são universais.
Árvore binária, frequentemente testada
árvore de pesquisa binária
Definição: A subárvore esquerda é menor que o nó raiz e o nó raiz é menor que a subárvore direita. O efeito é: o lado esquerdo é sempre menor que o lado direito
árvore binária balanceada
Árvore balanceada (árvore AVL)
definição:
É uma árvore vazia ou o valor absoluto da diferença de altura entre suas subárvores esquerda e direita não excede 1, e as subárvores esquerda e direita são árvores binárias balanceadas.
Implementação
Árvore rubro-negra, AVL, árvore bode expiatório, Treap, árvore espalhadora
amontoar
Definição: um heap é uma árvore binária balanceada. O nó pai é menor que o nó filho. Os nós filhos em excesso são colocados no nó filho esquerdo, tanto quanto possível. Pode ser implementado usando arrays<br>
Operações suportadas: O(log N) Adicionar / O(log N) Remover / O(1) Mín ou Máx.
Heap máximo vs heap mínimo
Características de valor: para o heap mínimo, o nó pai é menor que o nó filho e não há relação de tamanho entre os nós filhos esquerdo e direito para o heap do tipo máximo, o nó pai é maior que o nó filho e existe; não há relação de tamanho entre os nós filhos esquerdo e direito;
Características estruturais: É uma árvore binária com altura logN
Complexidade de tempo: complexidade de exclusão e pop são todas logN, encontre complexidade mínima ou máxima O(1)<br>
Método de inserção: Sempre insira da esquerda, garantindo uma árvore binária balanceada. Se o número inserido for pequeno, mova-o para cima e o nó pai desce. Portanto, a complexidade máxima é logN<br>
O método de exclusão é semelhante a
Método de implementação: Exercício: lintcode 130 heapify<br>
Perguntas práticas para entrevistas
104. Mesclar K listas classificadas<br>612. Mesclar K pontos mais próximos<br>545 No fluxo de dados Número de. dígitos<br>544. Principais K números grandes<br>401.
Árvore de segmento<br>
Definição: A árvore de segmento de linha é uma estrutura de dados avançada e uma estrutura em árvore, para ser mais preciso, é uma árvore binária. Ele pode lidar com problemas como consultas de modificação de intervalo com eficiência. <br>
Nota: Basicamente não foi testado, mas se você conseguir dominá-lo, poderá resolver muitos problemas de uma só vez. A árvore de segmento de linha é implementada com base no método de divisão e conquista e pode ser usada como uma boa prática para a divisão. e método de conquista.
entrevista
Encontre a altura de uma árvore binária
Encontre o k-ésimo valor máximo em uma árvore de pesquisa binária
Encontre o nó que está a distância k do nó raiz
Encontre os nós ancestrais de um determinado nó em uma árvore binária
104. Mesclar K listas classificadas<br>
3 maneiras
Método 1: usar PriorityQueue
Método 2: algoritmo de divisão e conquista semelhante à classificação por mesclagem
Método 3: algoritmo de fusão de pares de baixo para cima
A complexidade do tempo é O (NlogK)
Combinado com: algoritmo Jiuzhang
As questões práticas são todas questões de lintcode
Wondershare EdrawMind
