Gráfico, no probado a menudo
definición
Nodos conectados entre sí en forma de red.
el término
Borde: borde, un par de nodos
Algoritmo transversal
Primera búsqueda en amplitud DFS
Primera búsqueda en profundidad TFS
Relacionado con la entrevista
Implementar primera búsqueda en amplitud y profundidad
Comprueba si el gráfico es un árbol.
Contar el número de aristas en un gráfico.
Encuentra la distancia más corta entre dos vértices.
Pila monótona La pila monótona rara vez se prueba
Cola de doble extremo Deque, rara vez probada
Union Find rara vez se prueba
Los árboles de segmentos de línea rara vez se prueban
Matriz de árbol Árbol indexado binario, BIT, rara vez probado
Árbol de diccionario Trie, rara vez probado
definición
También conocido como: árbol de prefijos, una estructura de datos especial en forma de árbol
usar
Muy eficaz para resolver problemas relacionados con cuerdas.
Proporcionar búsqueda rápida
Buscar una palabra en un diccionario
Sugerencias automáticas en buscadores
entrevista
Cuente el número total de palabras en el árbol del diccionario.
Imprime todas las palabras almacenadas en el árbol del diccionario.
Ordenar elementos en una matriz usando un árbol de diccionario
Formar palabras a partir de un diccionario usando un árbol de diccionario
Construir diccionario T9: árbol de diccionario DFS
Tabla hash/tabla hash de mapa hash, a menudo probada
definición
Almacene objetos identificados de forma única en forma de pares clave-valor
Diccionario: una colección de pares clave-valor
Buscar valor de objeto usando clave clave
HashSet/HashMap en Java, unordered_map en C, dict en Python
Operaciones admitidas: O(1) Insertar / O(1) Buscar / O(1) Eliminar
Cómo funcionan las tablas hash
<br>Principio de funcionamiento: Para set. La clave obtiene un índice a través de la función hash y luego el valor se almacena en la matriz. <br>Para obtener, busque el índice a través de la clave y las funciones hash y obtenga el valor.
¿Por qué no se puede considerar simplemente que la complejidad temporal de varias operaciones en hash es O (1)?
La clave puede ser una cadena, un número entero o algo de longitud desconocida. Por lo tanto, es apropiado usar O(L) en sentido estricto, la complejidad temporal de cualquier operación es O(keySize) en lugar de O(1)<br>;
Cómo implementar la función hash
Cómo resolver la colisión de hash (Colisión)
Colisión significa que dos claves diferentes obtienen dos valores idénticos después del cálculo mediante la función hash. Hay dos formas principales de resolver conflictos:<br>Open Hashing. Significa que en la matriz en la que se basa la tabla hash, cada posición es el nodo principal de una Lista Enlazada. De esta manera, las tuplas <clave, valor> en conflicto se colocan en la misma lista enlazada. <br>Hashing cerrado. Significa que cuando ocurre un conflicto, los elementos siguientes irán a la siguiente posición para encontrar un espacio vacío<br>
¿Cómo hacer que la tabla hash se expanda continuamente?
factores de rendimiento
Método de manejo de colisiones
entrevista
Encuentre pares clave-valor simétricos en una matriz
¿Se utilizará la tabla hash de manera flexible para resolver el problema?
¿Domina los principios básicos de las tablas hash?
Realice un seguimiento de la ruta completa para mayor comodidad
Encuentre si una matriz es un subconjunto de otra matriz
Comprueba si las matrices dadas están separadas
526. Equilibrador de carga<br>
134. Estrategia de caché LRU<br>657. Insertar Eliminar GetRandom O(1)<br>954. Insertar Eliminar GetRandom O(1) - Se permiten duplicados<br>209.
Problemas de clase de flujo de datos<br>960. Primer número único en un flujo II<br>138. Suma de subarreglos<br>105. Copia de una lista vinculada con punteros aleatorios<br>171. 124. secuencia continua más larga
Ordenar búsqueda
clasificar
clasificación de selección
Encontrar
tabla de búsqueda estática
tabla de búsqueda dinámica
Definición de estructura de datos: una estructura de datos puede considerarse como una colección de almacenamiento de datos y varias operaciones (funciones) definidas en esta colección.
Método de prueba 1: preguntar sobre los principios básicos de una determinada estructura de datos y preguntar por su implementación
Ejemplo: hablar sobre el principio de Hash e implementar una tabla Hash
Método de prueba 2: utilizar algún tipo de estructura de datos para completar cosas
Ejemplo: fusionar K matrices ordenadas
Método de prueba 3: implementar una estructura de datos para proporcionar algunas funciones específicas
Ejemplo: el problema de elementos K de mayor frecuencia
complejidad del tiempo:
Describe la complejidad temporal de múltiples interfaces<br>
Por ejemplo, necesita diseñar una estructura de datos establecida.
Algoritmo 1: O (n) límite inferior O (1) agregar
Método de implementación: use almacenamiento de matriz, compare cada vez e insértelo directamente al final de la matriz
Algoritmo 2: O (logn) límite inferior O (logn) agregar
Método de implementación: utilice almacenamiento de árbol rojo-negro, TreeSet en Java, mapa en C
Array Array, más comúnmente probado
tipo
Matrices multidimensionales
submatriz
Preguntas de entrevista
41. 42,43, Subarreglo máximo<br>44. Subarreglo mínimo<br>138.
Problema de intervalo de matriz
Preguntas de entrevista
30. Insertar rangos<br>793. Intersección de múltiples matrices<br>156.
problema de clasificación externa
Definición: El algoritmo de clasificación externa se refiere a un algoritmo para ordenar datos almacenados en uno o más archivos grandes cuando no hay suficiente memoria. <br>
Dos pasos básicos:<br>Corte el archivo grande en varios archivos pequeños y use la memoria para ordenarlos respectivamente<br>Utilice el algoritmo de combinación K-way (fusión k-way) para ordenar varios archivos pequeños y fusionarlos en un archivo grande
Preguntas de entrevista
486. Fusionar K matrices ordenadas<br>104. Fusionar K listas ordenadas
Operaciones de bits
Definición: Operaciones con bits binarios
Preguntas de entrevista
365. ¿Cuántos unos hay en binario?<br>
Rara vez se consideran los conjuntos de árboles
También conocido como: Fenwick Tree Nombre en inglés: Binary Indexed Tree Abreviatura: BIT se implementa en función del prefijo y la información<br>
Aunque el nombre es Árbol, se almacena en una matriz (Array)<br>BIT es un árbol múltiple y la relación padre-hijo representa la relación de inclusión<br>Use getPrefixSum(k) para implementar getRangeSum(x, y )
complejidad del tiempo
Log(n) Modifica el valor en cualquier posición<br>Log(n) Consulta la suma de cualquier intervalo
Características
Para una matriz con N números, se admiten las siguientes funciones:<br>update(index, val) //Actualiza el valor en una posición en la matriz dentro del tiempo logN getPrefixSum(k) //Obténlo dentro del tiempo log(K) La suma de los primeros K números de la matriz.
Preguntas de entrevista
817. Variable de suma del elemento de matriz de rango<br>249 Cuente el número de números anteriores más pequeños que él mismo.
Relacionado con la entrevista
Encuentra el segundo elemento más pequeño en una matriz
Encuentra el primer número entero que no se repite
Reorganizar valores positivos y negativos en una matriz
65. Mediana de dos matrices ordenadas, problema difícil<br>
6. Fusionar matrices ordenadas II<br>64. Fusionar matrices ordenadas<br>839. Fusionar dos listas de intervalos ordenados<br>486. Fusionar K matrices ordenadas<br>577. dos matrices<br>548. Intersección de dos matrices II<br>793. Intersección de múltiples matrices<br>654. Multiplicación de matrices dispersas<br>931 Mediana de K matrices ordenadas<br>149. tiempo<br>405. Submatriz cuya suma es cero<br>944. Submatriz máxima<br>943. Suma de rango variable inmutable<br>665.
Stack Stack, no se prueba con frecuencia
definición
LIFO. Por ejemplo, en la carga logística, las mercancías cargadas más tarde se descargan primero.
Operaciones admitidas: O(1) Push / O(1) Pop / O(1) Arriba
solicitud
Se utiliza para recorrido no recursivo de árboles binarios, cálculo de expresiones polacas inversas, etc.
La principal estructura de datos de la implementación no recursiva de DFS.
En la búsqueda en amplitud (BFS), se registran los nodos que se van a expandir.
Las colas se pueden utilizar para implementar colas de mensajes para completar tareas asincrónicas.
Cuando la velocidad de producción y consumo de mensajes es inconsistente, se necesita una cola de mensajes para almacenar temporalmente los mensajes que se enviaron pero no se recibieron.
Implementar el modo de pila
Utilice una estructura de almacenamiento (matrices de uso común, ocasionalmente listas vinculadas) para almacenar elementos
¿Usar una matriz para implementar tres pilas?
¿Implementar una pila usando dos colas? <br>
la diferencia
Las matrices tienen un mejor rendimiento para el acceso aleatorio. <br>Las listas enlazadas tienen un mejor rendimiento para insertar y eliminar elementos.
Ejercicios<br>
código de pelusa: 495. Implementar pila
494. Pila de implementación de cola dual<br>
224. Utilice una matriz para implementar tres pilas<br>
funcionar
empujar, insertar el elemento en la parte superior
pop regresa y elimina el elemento superior de la pila
isEmptyLa pila está vacía y devuelve verdadero
top devuelve el elemento superior sin eliminarlo
Java usa java.util.Stack, que se extiende desde la clase Vector y admite operaciones como push(), pop(), peek(), vacío() y search().
C, solo use la pila en <stack>. El método es similar a Java, excepto que peek () en C se llama top (), y cuando pop (), el valor de retorno está vacío.
Python, use list directamente, use operaciones de corte como [-1] para ver la parte superior de la pila, use list.pop() cuando abra la parte superior de la pila y use list.append() cuando empuje la parte superior de la pila . <br>
Relacionado con la entrevista
Usando la pila para evaluar expresiones postfix
Ordenar los elementos de la pila.
Determinar si una expresión está equilibrada entre paréntesis
QueueQueue, a menudo probado
definición
Estructura de datos lineales de almacenamiento secuencial FIFO, primero en entrar, primero en salir, caja de supermercado
Operaciones admitidas: O(1) Push / O(1) Pop / O(1) Arriba
solicitud
Utilizado como estructura de datos principal para el algoritmo BFS.
funcionar
Insertar elementos al final de la cola de puesta en cola.
dequeue elimina el elemento principal de la cola
La columna isEmpty está vacía y devuelve verdadero
top devuelve el primer elemento de la cola
Método para realizar
¿Implementar cola usando lista vinculada?
¿Implementar una cola con dos pilas? <br>
¿Implementar cola usando una matriz circular?
Ejercicio: 955. Implementar cola mediante matriz circular<br>
entrevista
Utilice colas para representar pilas
Invertir los primeros k elementos de la cola.
Utilice una cola para generar números binarios del 1 al n
642. Promedio móvil del flujo de datos<br>
955. Implementar cola mediante matriz circular<br>
Lista enlazada, a menudo probada
definición
Cadena de nodos: cada nodo contiene datos y punteros a los nodos posteriores.
usar
Implementar sistema de archivos, tabla hash, lista de adyacencia
tipo
lista enlazada unidireccional
lista doblemente enlazada
funcionar
isEmpty, está vacío, devuelve verdadero
entrevista
Detectar ciclos en listas enlazadas
Devuelve el enésimo nodo desde el último en la lista vinculada
Eliminar duplicados de la lista vinculada
ÁrbolÁrbol
definición
estructura de datos jerárquica
Formado por vértices y aristas.
No hay ciclos en el árbol como se muestra en el gráfico.
tipo
Los árboles de segmentos de línea básicamente no se prueban, son universales.
Árbol binario, a menudo probado
árbol de búsqueda binaria
Definición: el subárbol izquierdo es más pequeño que el nodo raíz y el nodo raíz es más pequeño que el subárbol derecho. El efecto es: el lado izquierdo siempre es más pequeño que el lado derecho.
árbol binario equilibrado
Árbol equilibrado (árbol AVL)
definición:
Es un árbol vacío o el valor absoluto de la diferencia de altura entre sus subárboles izquierdo y derecho no excede 1, y los subárboles izquierdo y derecho son árboles binarios equilibrados.
Implementación
Árbol rojo-negro, AVL, árbol chivo expiatorio, Treap, árbol en expansión
montón
Definición: un montón es un árbol binario equilibrado. El nodo principal es más pequeño que el nodo secundario. Los nodos secundarios sobrantes se colocan en el nodo secundario izquierdo tanto como sea posible. No existe una relación de tamaño entre los nodos secundarios izquierdo y derecho. Se puede implementar usando matrices<br>
Operaciones admitidas: O(log N) Agregar / O(log N) Eliminar / O(1) Mín. o Máx.
Montón máximo frente a montón mínimo
Características del valor: para el montón mínimo, el nodo principal es más pequeño que el nodo secundario y no existe una relación de tamaño entre los nodos secundarios izquierdo y derecho. Para el montón de tipo máximo, el nodo principal es más grande que el nodo secundario; no existe una relación de tamaño entre los nodos secundarios izquierdo y derecho;
Características estructurales: Es un árbol binario con altura logN
Complejidad del tiempo: la complejidad de eliminación y pop son todas logN, encontrar complejidad mínima o máxima O (1) <br>
Método de inserción: inserte siempre desde la izquierda, asegurando un árbol binario equilibrado. Si el número insertado es pequeño, muévalo hacia arriba y el nodo principal se moverá hacia abajo. Entonces la complejidad máxima es logN<br>
El método de eliminación es similar a
Método de implementación: Ejercicio: lintcode 130 heapify<br>
Preguntas de práctica de la entrevista
104. Fusionar K listas ordenadas<br>612. K puntos más cercanos<br>545. Top K Big Numbers II<br>613. Excelentes resultados<br>486. dígitos<br>544. Top K números grandes<br>401. El k-ésimo número de pequeño a grande en la matriz de clasificación.
Árbol de segmentos<br>
Definición: el árbol de segmentos de línea es una estructura de datos avanzada y una estructura de árbol; para ser precisos, es un árbol binario. Puede manejar de manera eficiente problemas como consultas de modificación de intervalos. <br>
Nota: Básicamente no está probado, pero si puedes dominarlo, puedes resolver muchos problemas de una sola vez. El árbol de segmentos de línea se implementa según el método de dividir y conquistar y puede usarse como una buena práctica para dividir. y método de conquista.
entrevista
Encuentra la altura de un árbol binario.
Encuentre el k-ésimo valor máximo en un árbol de búsqueda binario
Encuentre el nodo que está a una distancia k del nodo raíz
Encuentre los nodos ancestros de un nodo determinado en un árbol binario
104. Fusionar K listas ordenadas<br>
3 maneras
Método 1: utilizar PriorityQueue
Método 2: algoritmo de divide y vencerás similar a la ordenación por fusión
Método 3: algoritmo de fusión por pares ascendente
La complejidad del tiempo es O (NlogK)
Combinado con: algoritmo de Jiuzhang
Las preguntas de práctica son todas preguntas de Lintcode.
Wondershare EdrawMind
