Soluciones LeetCode con buen estilo

Este documento proporciona una descripción general completa de LeetCode-Solutions-in-Good-Style, un recurso que ofrece tutoriales para principiantes y soluciones en vídeo para problemas de algoritmos y estructuras de datos. Presenta un enfoque estructurado con código claro, explicaciones detalladas y se centra en la construcción. una sólida comprensión de los conceptos fundamentales en lugar de una codificación competitiva.

Soluciones LeetCode con buen estilo

Explicación: Como la mayoría de mis compañeros, estudio y resumo al mismo tiempo. Intentaré compartir más y brindarles algunos conocimientos útiles. Gracias por su continuo apoyo.

Hola a todos, este es un tutorial de nivel básico sobre "Algoritmos y estructuras de datos". Es adecuado para estudiantes sin conocimientos básicos de algoritmos y estudiantes que han cambiado de carrera. No es adecuado para prepararse para competencias de algoritmos. El punto que quiero transmitir es: escribir código con una lógica clara, por lo que el código que escribo debe haber pasado por un pensamiento estricto. El formato es muy estándar, sin estilo personal, y no escribiré una línea en blanco ni comentaré para reducirlo. el número de líneas de código. Aquí lo tienes:

Puedes llamarme weiwei. Haré todo lo posible para responder las preguntas que conozco dentro de mi capacidad y si el tiempo lo permite. Si tiene alguna pregunta que no pueda responderse a tiempo, puede deberse a que no vi la notificación en el sitio. Puede enviarme un correo electrónico a [email protected].

Solución de video que grabé.

Comencé a grabar soluciones de video en septiembre de 2019. Al principio grababa el material del que quería hablar varias veces. Ahora escriba borradores palabra por palabra cuando explique los puntos de conocimiento. Se han acumulado muchos videos, que en realidad son un pequeño curso sistemático. Ahora se enumeran aquí, espero que pueda ser útil para todos.

0. ¿Cómo puede un usuario novato de algoritmos utilizar LeetCode? 【Compartir información útil】

1. Complejidad del tiempo y complejidad del espacio.

Este video menciona que la complejidad del tiempo es un concepto asintótico y debe entenderse desde una perspectiva dinámica. Y se explica la definición estricta (forma límite) de complejidad del tiempo para que todos puedan comprender las reglas de cálculo de la complejidad del tiempo. También señaló: la complejidad del tiempo no es el tiempo de ejecución del programa; se debe utilizar "espacio por tiempo" y se debe prestar más atención a optimizar la "complejidad del tiempo".

2. Búsqueda binaria

Este video presenta cómo escribir un algoritmo de búsqueda binaria. Aunque hay muchos detalles sobre la búsqueda binaria, siempre que dominemos las ideas correctas para la resolución de problemas, practiquemos más, pensemos con diligencia y hagamos más resúmenes, el problema de la búsqueda binaria no desaparecerá. ya no habrá dificultad.

El siguiente video explica varios ejemplos de preguntas de búsqueda binaria. Nos centramos en analizar el significado de la pregunta y cómo utilizar las condiciones dadas en la pregunta para reducir gradualmente el rango de búsqueda.

A través del análisis de la pregunta 4 de "Likou" (encontrar la mediana de dos matrices de orden positivo), le presentamos esta técnica: si las propiedades del elemento objetivo que está buscando son más complejas, puede invertir esta propiedad. y luego escriba declaraciones lógicas que puedan reducir fácilmente el rango del problema.

3. Problemas relacionados con la clasificación

La "clasificación por fusión" y la "clasificación rápida" son algoritmos de clasificación muy importantes. Una comprensión profunda de ellos es muy útil para comprender el mecanismo operativo de las funciones "recursivas". Al mismo tiempo, también son aplicaciones típicas del pensamiento de "divide y vencerás". ". El "par de orden inverso" y el "problema de la bandera holandesa (clasificación de colores)" también son problemas de algoritmos muy clásicos.

El cálculo de "pares de orden inverso" se basa enteramente en la idea de "ordenación por fusión".

En la explicación del problema de la "clasificación de colores", presentamos "invariantes de bucle" a todos. En el proceso de escritura del código, siempre debemos cumplir con la semántica de las variables utilizadas, "antes de la ejecución del programa" y "durante la ejecución". permanece sin cambios después de que "finaliza la ejecución". Adherirnos a nuestra propia definición de "invariantes de bucle" es una forma importante para que podamos escribir código correcto.

"El primer número positivo que falta" es un problema de algoritmo clásico. La idea utilizada es "hash in situ", que puede entenderse como una aplicación especial del algoritmo de "clasificación de cubos": una zanahoria, un hoyo y un cubo. Almacenar un elemento. Quiero enfatizar que el hecho de que puedas hacer esto está estrechamente relacionado con el valor de los elementos de la matriz de entrada.

4. Ventana corredera

El problema de la "ventana deslizante" es un problema típico que se resuelve aplicando "invariantes de bucle", que pone a prueba nuestras capacidades de codificación y depuración.

5. Problemas relacionados con la pila

Los problemas resueltos usando "pilas" requieren que usemos ejemplos específicos para encontrar que resolverlos coincide con la regla de "el último en entrar, el primero en salir":

Dominar las dos preguntas siguientes es inseparable del estudio de ejemplos específicos y luego de resumir las reglas generales.

Una de las aplicaciones más utilizadas de "pila" es como soporte de estructura de datos para "recursión", "recorrido en profundidad primero" y "algoritmo de divide y vencerás".

6. Búsqueda combinada

La estructura de datos "Union Search Set" rara vez se utiliza en las entrevistas. Si se está preparando para una entrevista de algoritmo, puede omitirla.

7. árbol

Muchos problemas de árboles se pueden resolver utilizando "recorrido primero en profundidad" o "recorrido primero en anchura".

8. Algoritmo de retroceso

El "algoritmo de retroceso" es en realidad un recorrido en profundidad de la "estructura de árbol" contenida en la pregunta. Al resolver este tipo de problemas, es importante dibujar un diagrama de estructura de árbol en papel borrador.

9. Programación dinámica

10. Recorrido en amplitud y clasificación topológica

11. tabla hash

12. Operaciones de bits relacionadas

Mi sitio web personal y notas de estudio de algoritmos.

Grupo WeChat y grupo QQ

Si necesita amigos para trabajar juntos en las preguntas, puede unirse al grupo WeChat y al grupo QQ.

MiLeetBook

Aquí hay una promoción para mí. Recientemente lancé mi propio LeetBook en "LeetBook": Algoritmos de aprendizaje desde cero (anteriormente conocido como "Algoritmos de aprendizaje y estructuras de datos con" LeetCoin "), que es principalmente para amigos que han cambiado de carrera y tienen. fundamento cero. Explicar los conocimientos básicos de algoritmos y estructuras de datos.

ilustrar:

Los dos primeros capítulos de LeetBook (Time Complexity, Binary Search) se pueden leer de forma gratuita. Los siguientes capítulos requieren un pago para leer. El precio para no miembros es de 99 yuanes y el precio para miembros es de 69 yuanes. lo mismo que LeetBook sólo que la parte extra, no menos;

Los títulos de los cursos, ejemplos, ejercicios y el repositorio de códigos de soporte de LeetBook (el repositorio que está viendo actualmente) son completamente públicos. Si ya domina el contenido (incluidos los ejercicios) diseñado en LeetBook, no se recomienda comprarlo;

La energía invertida es la misma que para escribir la solución normalmente, excepto que LeetBook será más detallado al crear gráficos. El contenido pago es: el tiempo y la energía dedicados a realizar tutoriales y la participación del personal y expertos de "Likou" en la producción y revisión, la experiencia de lectura será mejor. No se descarta que suelo escribir más puntos de conocimiento sobre resolución de problemas que LeetBook;

Los usuarios intermedios y avanzados deben comprar con precaución;

Puedes consultarme sobre el contenido del curso en el sitio "Likou" o en mis otras cuentas sociales, o puedes enviar un problema a este almacén. Independientemente de si compro el curso o no, haré todo lo posible para responder las preguntas que conozco (si el tiempo lo permite y dentro de mis posibilidades). Gracias a todos por su continuo apoyo hacia mí. Todos son bienvenidos a comunicarse conmigo si tienen sugerencias y opiniones;

El conocimiento que explico está en los libros que he recomendado a todos, los blogs, las soluciones de problemas y las notas que he escrito. Las soluciones de problemas, los blogs y las notas publicados siempre se compartirán, y mientras tenga tiempo y energía, Continuaré haciéndolo. Compartir y preguntas y respuestas;

Estoy muy agradecido con "Likou" por darme la oportunidad de realizar cursos y ayudarme a cumplir un pequeño deseo.

Directorio de clasificación y solución de problemas "Lekou" (organizado según los capítulos de LeetBook, el capítulo 16 en adelante son capítulos que actualmente no están incluidos en LeetBook)

Nota: Las categorías de preguntas corresponden a mis capítulos de LeetBook.

Capítulo 1 Complejidad del tiempo

Esta parte presenta el concepto de complejidad del tiempo. Puede ver [Explicación en video], que es completamente gratuito. No hay ejercicios para este capítulo.

Capítulo 2 Búsqueda binaria

Tipo de pregunta 1: busque subíndices en dos puntos

ilustrar:

práctica:

Tipo de pregunta 2: Determinar un número entero con un rango de dos puntos (respuesta de dos puntos)

Pensamiento algorítmico: reducir y conquistar. Si la pregunta requiere que encontremos un número entero, y este número entero tiene un cierto rango, podemos reducir gradualmente el rango mediante la búsqueda binaria y finalmente acercarlo a un número.

Tipo de pregunta 3: Función discriminante compleja (problema de maximización)

Nota: Este tipo de pregunta es esencialmente "Pregunta tipo 2" (respuesta de dos puntos), pero puede resultar un poco confuso cuando la aprenda por primera vez. Las preguntas de este tipo se formulan de la misma manera. Las palabras clave son "continua" y "entero positivo". Preste atención a capturar dicha información clave en la pregunta.

Capítulo 3 Algoritmos de clasificación básicos

Esta parte contiene cuatro algoritmos de clasificación básicos: clasificación por selección, clasificación por inserción, clasificación Hill y clasificación por burbuja.

Pregunta 912 de "Likou": Solución a la matriz ordenada: resume algunos puntos clave y materiales de aprendizaje para problemas de clasificación. Puede comenzar a aprender algoritmos a partir de problemas de clasificación.

Los problemas de matriz se pueden utilizar como un "campo de novatos" en algoritmos, porque estos problemas sólo pueden resolverse si se dominan los conocimientos básicos de los lenguajes de programación. Es fácil pensar en soluciones a los siguientes problemas, incluso si no ha adquirido conocimientos relevantes sobre estructuras de datos y algoritmos.

Punto de conocimiento: invariantes de bucle

Capítulo 4 Algoritmos de clasificación avanzados (importante)

Esta parte debe centrarse en dominar tres algoritmos de clasificación avanzados: clasificación por combinación, clasificación rápida y clasificación en montón.

ilustrar:

Capítulo 5 Clasificación no comparativa (opcional)

Esta parte contiene tres tipos de clasificación sin comparación: clasificación por conteo, clasificación por base y clasificación por cubo. Resolver estos problemas requiere comprender el concepto de hash in situ.

Capítulo 6 Ventana deslizante y punteros dobles

1. Ventana corredera

Método de escritura de referencia de la ventana deslizante (no es una plantilla, no la copie tal como está, es solo como referencia, es más importante comprender la idea de diseño del algoritmo):

Recordatorio amistoso: las preguntas 3 y 76 son preguntas básicas que debe poder responder. Una vez que comprenda a fondo las preguntas anteriores, podrá responder las siguientes preguntas más fácilmente.

Preguntas clave:

ilustrar:

práctica:

ilustrar:

Pregunta 209: La información clave proporcionada en la pregunta: Todos los elementos de la matriz son números enteros positivos. Hay un total de 3 métodos de la siguiente manera.

Método 1: solución violenta

Método 2: ventana corredera (analice las razones por las que se pueden utilizar ventanas correderas)

Método 3: construir el prefijo y la matriz, y luego usar la búsqueda binaria

Pregunta 438: Igual que la pregunta 76;

Pregunta 567: Igual que la pregunta 76, excepto que la colección de oraciones calificadas es diferente.

2. Dobles punteros

El problema del "doble puntero" es en realidad una optimización del algoritmo ingenuo. Muchas soluciones que no cumplen con el significado del problema se resuelven a la vez. Lo mismo ocurre con la técnica de la "ventana deslizante". Es aún más importante analizar por qué se pueden utilizar punteros dobles.

El algoritmo de búsqueda binaria utilizado para encontrar subíndices también puede considerarse una solución de doble puntero.

Capítulo 7 Lista enlazada

Una técnica muy práctica para resolver problemas de listas enlazadas es el "dibujo". Lo mismo ocurre con el análisis y explicación de otros problemas algorítmicos (explicando al entrevistador).

Puede escribir funciones de prueba para listas vinculadas para facilitar la depuración. Los métodos de implementación recomendados son: ① Crear una lista enlazada individualmente a través de una matriz ② Imprimir el nodo actual y los nodos posteriores según el nodo actual. Estos dos métodos pueden ayudarnos muy cómodamente a depurar programas relacionados con listas enlazadas.

Tipo de pregunta 1: problema básico de señalización de punteros de listas vinculadas

Nota: Algunos problemas requieren el uso de "nodos principales virtuales" para evitar una lógica de discusión de clasificación compleja para el primer nodo de la lista vinculada. Hemos visto esta idea en formaciones, llamadas "centinelas".

Utilice funciones recursivas para evitar operaciones complejas de cambio de variables de puntero, simplificando la resolución de problemas.

ilustrar:

Tipo de pregunta 2: Habilidades de puntero rápido y lento

Para ser precisos, sería mejor llamarlo "puntero sincronizado".

Usando dos variables de puntero, ambas se ubican en el primer nodo de la lista vinculada al principio. Una siempre solo da un paso a la vez y la otra siempre solo da dos pasos a la vez, uno al frente y otro al final. atrás, al mismo tiempo. De esta forma, cuando el puntero rápido termine de caminar, el puntero lento alcanzará la posición media de la lista enlazada.

La característica común para resolver estos problemas es utilizar dos variables de puntero para moverse sincrónicamente. Los punteros rápido y lento se mueven en la misma dirección y la "diferencia" entre sus pasos es constante. En base a esta certeza, se pueden resolver algunos problemas en la lista vinculada. Usar esta idea también puede resolver los siguientes problemas de listas enlazadas:

ilustrar:

Pregunta tipo tres: estructura de datos de diseño

Capítulo 8 Apilar y poner en cola

1. pila

Tipo de pregunta 1: Problemas básicos resueltos usando la pila

Las siguientes preguntas son muy básicas y deben dominarse:

práctica:

Tipo de pregunta 2: pila monótona

Una pila monótona es una pila ordinaria, que cumple con el principio de "último en entrar, primero en salir" durante el uso, y los elementos de la pila son monótonos. Los problemas de "pila monótona" y "cola monótona" suelen ser muy especiales. Simplemente domine los ejemplos y algunos ejercicios.

Experiencia: los subíndices generalmente se almacenan en pilas monótonas.

ilustrar:

práctica:

2. Cola

Tipo de pregunta 1: Problemas básicos resueltos mediante colas

Todos los problemas se resuelven utilizando colas de uso transversal primero en amplitud.

Tipo de pregunta 2: cola monótona

Una cola monótona es simplemente una cola ordinaria. Este problema se encuentra actualmente en la cola monótona de "Likou". La clave es analizar claramente por qué el algoritmo diseñado hace que la cola sea monótona. Además, hay ejemplos del uso de colas monótonas para la optimización en el "Problema de la mochila". Los amigos interesados ​​pueden aprender sobre esto, que es conocimiento de la competencia.

Experiencia: los subíndices generalmente se almacenan en colas monótonas.

Capítulo 9 Cola de prioridad

Nota: Es necesario comprender la implementación de "montón" como una "cola de prioridad". Esto ayudará a comprender los detalles de codificación de eliminar () y reemplazar (), para que sea más efectivo al usar el montón.

Aplicación: seleccione dinámicamente el elemento de mayor prioridad en la cola actual, centrándose en comprender el significado de "dinámico".

Capítulo 10: Búsqueda combinada

Y consulte la [explicación en video] de los puntos de conocimiento en la solución en video a la pregunta 990. Las preguntas básicas y comunes incluyen:

Preguntas opcionales:

Capítulo 11 Árboles (árboles binarios y árboles de búsqueda binaria)

Capítulo 12 Algoritmo de retroceso

Tipo de pregunta 1: problema básico de retroceso

A través de estas preguntas, puede comprender la idea del algoritmo de retroceso. Los puntos de conocimiento del algoritmo de retroceso se explican en la solución en video y en el texto de la pregunta 46 de "Likou".

El retroceso consiste en utilizar un recorrido en profundidad primero para buscar todas las soluciones del árbol (gráfico). El recorrido en profundidad primero tiene una estructura recursiva obvia.

Consejos para resolver los siguientes problemas: ① Dibujar, dibujar, dibujar; ② Comprender el recorrido en profundidad y la recursividad ③ Depurar más, depurar más;

Tipo de pregunta 2: Problema de retroceso en cadenas

Puntos clave a entender: dado que la cadena genera nuevos caracteres cada vez, no es necesario restablecer el estado.

Pregunta tipo tres: Relleno por inundación

Tipo de pregunta 4: algunas preguntas del juego

ilustrar:

Capítulo 13 Programación dinámica (Parte 1)

Dos ideas importantes de programación dinámica:

Dos direcciones de pensamiento en programación dinámica:

Se deben cumplir tres condiciones para resolver el problema mediante programación dinámica:

Dos conceptos importantes de programación dinámica:

Referencia de clasificación de preguntas:

Nota: Se agregarán las preguntas típicas que se detallan a continuación (2 de diciembre de 2020).

1. Empezando

Comprenda los dos métodos de programación dinámica: la recursividad de la memoria "de arriba hacia abajo" y la recursividad "de abajo hacia arriba".

2. Subproblemas repetidos

Esta parte requiere el uso del "principio de multiplicación de conteo de pasos" y el "principio de suma de conteo categórico".

Pregunta 70: Esta es la misma pregunta que los números de Fibonacci. Los problemas de conteo utilizarán el principio de conteo de clasificación y el principio de conteo de pasos.

3. Subestructura óptima

ilustrar:

Pregunta 377: Tenga en cuenta que el examen no es un problema de mochila.

4. Sin secuelas

práctica:

Los siguientes son algunos problemas clásicos de "programación dinámica". Debido a que estos temas son tan importantes, se incluyen en una categoría separada.

5. Suma máxima del subsegmento

práctica:

6. Subsecuencia ascendente más larga

Nota: La pregunta 300 es un problema de programación dinámica muy clásico. La solución de $O(N log N)$ define el estado de acuerdo con las características del problema en sí y demuestra que la matriz de estados es una matriz ordenada, lo que reduce la complejidad del tiempo.

práctica:

7. La subcadena común más larga.

8. DP de intervalo y DP particionado

Intervalo DP:

DP particionado:

9. Árbol DP

Capítulo 14 Programación dinámica (Parte 2)

1. Problema con la mochila

Nueve conferencias sobre mochilas: https://github.com/tianyicui/pack

("Se agregarán Tipo de juego DP", "Compresión de estado DP", "DP digital", etc.)

Otras preguntas

Capítulo 15 Algoritmo codicioso

Capítulo 17 Tablas hash

Capítulo 18 Sumas de prefijos y tablas hash

Capítulo 19 Recorrido primero en amplitud

Algunos problemas con el recorrido de árboles en anchura y algunos problemas en LeetBook.

Capítulo 20 Algoritmo de teoría de grafos (árbol de expansión mínimo)

Capítulo 21 Algoritmo de teoría de grafos (ruta más corta de fuente única)

Capítulo 22 Algoritmo de divide y vencerás

La idea de divide y vencerás divide un problema más grande en varios subproblemas más pequeños del mismo tipo y luego resuelve estos subproblemas de forma recursiva. Una vez completado cada subproblema, se resuelve. Se obtiene el problema original.

El algoritmo de divide y vencerás se puede ejecutar en paralelo, pero en el campo de los algoritmos básicos, el algoritmo de divide y vencerás se ejecuta primero en profundidad.

Algoritmos típicos que aplican la idea de divide y vencerás: clasificación por fusión, clasificación rápida.

Problemas típicos del pensamiento divide y vencerás: "Pregunta 51 de los puntos de la espada a la oferta": "Pregunta 51 de los puntos de la espada a la oferta" 51. Pares en orden inverso en una matriz (explicación en video).

Otras preguntas típicas (por añadir)

¡Continuará actualizándose y los amigos pueden brindar comentarios valiosos!