ARTES #015

ARTES es una actividad iniciada por 由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.

##ARTES 015

este es el articulo 15

Pregunta sobre el algoritmo del algoritmo

Las preguntas sobre algoritmos que hicimos esta semana fueron recorrido de preorden, recorrido de orden y recorrido de postorden de un árbol binario. Cada tipo de recorrido se implementa de forma recursiva e iterativa, respectivamente. Las implementaciones recursivas de los tres recorridos son básicamente las mismas, pero las implementaciones iterativas de los tres recorridos son diferentes. Entre ellos, la implementación iterativa del recorrido posterior al pedido es la más difícil.

La diferencia entre recursividad e iteración: Recursividad: la técnica de programación en la que un programa se llama a sí mismo se llama recursividad. Iteración: utilice el valor original de la variable para calcular un nuevo valor de la variable. La iteración significa que A sigue llamando a B.

Ejemplos de historias de películas: Iteración: “Al filo del mañana” Recursión - “Inicio”

参见：
https://blog.csdn.net/laoyang360/article/details/7855860
Google：递归 迭代
斐波那契数列为:0,1,1,2,3,5...
//迭代实现斐波那契数列  
long fab_iteration(int index)  
{  
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        long f1 = 1L;  
        long f2 = 1L;  
        long f3 = 0;  
        for(int i = 0; i < index-2; i++)  
        {     
            f3 = f1 + f2; //利用变量的原值推算出变量的一个新值  
            f1 = f2;  
            f2 = f3;  
        }  
         return f3;  
    }  
}  
  
//递归实现斐波那契数列  
 long fab_recursion(int index)  
 {      
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        return fab_recursion(index-1)+fab_recursion(index-2);    //递归求值  
    }  
} 

Recorrido de pedido anticipado: nodo raíz —> subárbol izquierdo —> subárbol derecho Recorrido en orden: subárbol izquierdo —> nodo raíz —> subárbol derecho Recorrido posterior al pedido: subárbol izquierdo —> subárbol derecho —> nodo raíz

94. Recorrido en orden del árbol binario

Dificultad: Media

Dado un árbol binario, devuelve el recorrido inorder de los valores de sus nodos.

Ejemplo:

**Input:** [1,null,2,3]
   1
    \
     2
    /
   3

**Output:** [1,3,2]```

**Seguimiento:** La solución recursiva es trivial, ¿podrías hacerlo de forma iterativa?



#### Solución

Idioma: **C**

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
 

// solución recursiva implementación recursiva

int* inorderTraversal(struct TreeNode* root, int* returnSize) {

    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    //左子树
    int returnSizeLeft = 0;
    int *left = NULL;
    if(root->left != NULL){
        left= inorderTraversal(root->left, &returnSizeLeft);
    }
    
    //根结点
    
    //右子树
    int returnSizeRight = 0;
    int *right = NULL;
    if(root->right!= NULL){
        right = inorderTraversal(root->right, &returnSizeRight);
    }
    
    *returnSize = returnSizeLeft + returnSizeRight + 1;
    int* traversalResult=(int*)malloc((*returnSize)*sizeof(int));
    
    int index = 0;
    for (int i =0; i<returnSizeLeft; i++) {
        traversalResult[index++] = left[i];
    }
    free(left);
    
    traversalResult[index++] = root->val;
    
    for (int i =0; i<returnSizeRight; i++) {
        traversalResult[index++] = right[i];
    }
    free(right);

    return traversalResult;
}

// solución iterativa implementación iterativa

//迭代算法 iteratively
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
   struct TreeNode** traversalResult=(struct TreeNode**)malloc(1000*sizeof(struct TreeNode*));
   if (root == NULL) {
       *returnSize = 0;
       return NULL;
   }
   int *result=(int*)malloc(1000*sizeof(int));
   *returnSize = 0;
   
   int index = 0;
   struct TreeNode* p = root;
   
   while (p != NULL || index>0) {
       printf("%d",index);
       while (p != NULL) {
               traversalResult[index++] = p;
               p = p->left;
       }
       if (index >= 1) {
           p = traversalResult[--index];
           result[(*returnSize )++] = p->val;
           p = p->right;
       }
   }
   return result;
}

144. Recorrido de reserva del árbol binario

Dificultad: Media

Dado un árbol binario, devuelve el recorrido preorder de los valores de sus nodos.

Ejemplo:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[1,2,3]`

Seguimiento: La solución recursiva es trivial, ¿podrías hacerlo de forma iterativa?

Solución

Idioma: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

//iteratively solution 迭代解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
        if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int * result = (int *)malloc(sizeof(int) * (1000));
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
   
    struct TreeNode* p=root;
    *returnSize = 0;
    int stackIndex = 0;
   
    while (p || stackIndex > 1) {
    
        result[(*returnSize)++] = p->val;
        
        if (p->right) {
            stack[stackIndex++]=p->right;
        }
        
        p = p->left;
        
        if (stackIndex > 0&&!p) {
             p = stack[--stackIndex];
        }
    }
    
    
    return result;
}

//recursive solution 递归解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        * returnSize = 0;
        return NULL;
    }
    
    //左节点
    int leftSize =  0;
    int *left = NULL;
    if(root->left){
       left =  preorderTraversal(root->left, &leftSize);
    }
    
    //右节点
    int rightSize =  0;
    int *right = NULL;
    if(root->right){
       right =  preorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize + 1;
    int * result = (int *)malloc(sizeof(int) * (*returnSize));
    
    
    int index = 0;
    
    //根节点
    result[index++] = root->val;
    
    //左节点
    for (int i =0; i<leftSize; i++) {
        result[index++] = left[i];
    }
    free(left);
    
    //右节点
    for (int i =0; i<rightSize; i++) {
        result[index++] = right[i];
    }
    free(right);
    
    return result;
}

145. Recorrido de orden posterior del árbol binario

Dificultad: Difícil

Dado un árbol binario, devuelve el recorrido postorder de los valores de sus nodos.

Ejemplo:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[3,2,1]`

Seguimiento: La solución recursiva es trivial, ¿podrías hacerlo de forma iterativa?

Solución

Idioma: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

////迭代实现 iteratively solution
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int *)malloc(sizeof(int) * 1000);
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    
    * returnSize  = 0;
    int stackIndex = 0;
    int *flag = (int *)malloc(sizeof(int) * 1000);//用来标记是否是第二次访问这个节点
    
    struct TreeNode* p = root;

    while (p || stackIndex > 1) {
        if (p) {
            int dex = stackIndex++;
            stack[dex] = p;
            flag[dex] = 1;
            
        }
        
        if (p->right) {
            int dex = stackIndex++;
            stack[dex] = p->right;
            flag[dex] = 0;
        }
        
        p = p->left;
        if (!p && stackIndex > 0) {
            int loop =1;
            while (loop && stackIndex>0) {
                int index = --stackIndex;
                p = stack[index];
                if (flag[index] == 1) {
                    result[(*returnSize)++] = p->val;
                    loop = 1;
                }
                else{
                    loop =0;
                }
            }
            if (stackIndex==0) {
                return result ;
            }
        }
    }
    return result;
}

//递归实现 Recursive solution
int* postorderTraversal_1(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int *left = NULL;
    int leftSize = 0;
    if (root->left) {
        left = postorderTraversal(root->left, &leftSize);
    }
    
    int *right = NULL;
    int rightSize = 0;
    if (root->right) {
        right = postorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize  + 1;
    int *result =  (int *)malloc(sizeof(int) * (*returnSize));
    int index = 0;
   
    for (int i = 0; i < leftSize; i++) {
        result[index++] = left[i];
    }
    
    for (int i = 0; i < rightSize; i++) {
        result[index++] = right[i];
    }
    
    result[index] = root->val;
    
    free(left);
    free(right);
    
    
    return result;
}

Revisión

Reseña como artículo solo: https://dandan2009.github.io/2018/11/17/accelerating-your-coding-skills/

CONSEJOS

Esta semana, aclaremos los conceptos relacionados con los árboles binarios.

Algunos conceptos relacionados de árboles binarios:

Un árbol binario es una estructura de árbol en la que cada nodo tiene como máximo dos ramas (es decir, no hay nodos con un grado de rama mayor que 2). Por lo general, las ramas se denominan “subárbol izquierdo” o “subárbol derecho”. Las ramas de un árbol binario tienen orden de izquierda y derecha y no se pueden revertir a voluntad. El i-ésimo nivel del árbol binario tiene como máximo 2^i-1 nodos

diferente de los árboles comunes El número de nodos de un árbol ordinario es al menos 1, mientras que el número de nodos de un árbol binario puede ser 0; No hay límite para el grado máximo de ramificación de un nodo de árbol normal, mientras que el grado máximo de ramificación de un nodo de árbol binario es 2; Los nodos de un árbol ordinario no tienen orden izquierdo o derecho, mientras que los nodos de un árbol binario tienen orden izquierdo o derecho.

Los árboles binarios se suelen utilizar como estructuras de datos. Un uso típico es definir una función de etiquetado para los nodos y asociar algunos valores con cada nodo. El árbol binario marcado de esta manera puede implementar árbol de búsqueda binaria y montón binario y usarse para búsqueda y clasificación eficientes.

Los árboles binarios no son un caso especial de árboles Aunque existen muchas similitudes entre los conceptos de árboles y árboles binarios, son dos estructuras de datos diferentes. Porque de la definición: Un árbol binario no es un árbol con sólo dos subárboles ni un árbol con como máximo dos subárboles. La principal diferencia entre un árbol y un árbol binario es que el subárbol de un nodo en un árbol binario debe distinguir entre el subárbol izquierdo y el subárbol derecho. Incluso si el nodo tiene solo un subárbol, se debe indicar claramente si el subárbol es el subárbol izquierdo o el subárbol derecho. En cuanto a un árbol, no importa cuántos subárboles tenga, el estado de cada subárbol es el mismo, a diferencia de un árbol binario donde se distingue izquierda y derecha.

Un árbol binario es un árbol ordenado especial: cada nodo tiene como máximo dos ramas (nodos secundarios), y las ramas tienen orden izquierdo y derecho y no se pueden revertir. Dos árboles binarios especiales: Árbol binario completo: excepto la última capa, si todas las demás capas están llenas y la última capa está llena o le faltan varios nodos consecutivos a la derecha (tenga en cuenta que está a la derecha, no a la izquierda). Árbol binario completo: cada nivel está lleno (excepto el último nivel, donde el último nivel se refiere al nodo hoja).

Los árboles binarios se pueden almacenar usando matrices o listas enlazadas. Si el árbol binario está lleno, se puede organizar de forma compacta sin desperdiciar espacio. Si el índice de un nodo es i (suponiendo que el índice del nodo raíz sea 0), entonces el índice de su nodo secundario izquierdo será 2i+1 y el índice de su nodo secundario derecho será 2i+2; y su nodo padre (si lo hay) tendrá el índice $\frac{i-1}{2}$. Este enfoque es más propicio para un almacenamiento compacto y una mejor localidad de acceso, especialmente en el recorrido previo al pedido. Sin embargo, requiere espacio de almacenamiento continuo, por lo que se desperdiciará mucho espacio al almacenar un árbol general compuesto por n nodos con altura h. En el peor de los casos, si cada nodo de un árbol binario con profundidad h tiene solo un hijo derecho, la estructura de almacenamiento debe ocupar 2^h - 1 espacio. De hecho, existen nodos h, lo que desperdicia mucho espacio y es una deficiencia importante de la estructura de almacenamiento secuencial.

Un árbol binario completo almacenado en una matriz.

Primer recorrido en profundidad En prioridad de profundidad, queremos acceder al nodo más alejado del nodo raíz. A diferencia de la búsqueda en profundidad del gráfico, no es necesario recordar cada nodo visitado, porque no habrá ciclos en el árbol. Los recorridos de preorden, en orden y post-orden son casos especiales de recorrido en profundidad primero. Ver búsqueda en profundidad.

Recorrido primero en amplitud A diferencia del recorrido en profundidad, el recorrido en amplitud visita primero los nodos más cercanos al nodo raíz. Véase búsqueda en amplitud. El recorrido en amplitud de un árbol binario también se denomina recorrido nivel por nivel. El algoritmo se implementa con la ayuda de colas.

árbol binario Definición: El árbol binario t es un conjunto de elementos finitos (puede estar vacío). Cuando el árbol binario no está vacío, hay un elemento llamado raíz, y los elementos restantes (si los hay) se componen de dos árboles binarios, llamados subárbol izquierdo y subárbol derecho de t respectivamente.

La diferencia fundamental entre un árbol binario y un árbol es:

Los árboles binarios pueden estar vacíos, pero los árboles no pueden estar vacíos. Cada elemento de un árbol binario tiene exactamente dos subárboles (uno o ambos pueden estar vacíos). Cada elemento del árbol puede tener varios subárboles. En un árbol binario, los subárboles de cada elemento están ordenados, es decir, se pueden distinguir por los subárboles izquierdo y derecho. Los subárboles del árbol están desordenados. La siguiente figura muestra un árbol binario que representa una expresión matemática. Hay un total de 3 expresiones matemáticas. Cada operador puede tener uno o dos operandos, el operando izquierdo es el subárbol izquierdo del operador y el operando derecho es el subárbol derecho. Los nodos de hoja en el árbol son constantes o variables.

Características de los árboles binarios. Característica 1: El número de aristas de un árbol binario que contiene n (n>0) elementos es n-1.

Demuestre que cada elemento de un árbol binario (excepto el nodo raíz) tiene exactamente un nodo padre. Solo hay un borde entre el nodo secundario y el nodo principal, por lo que el número de bordes es n-1.

La altura o profundidad de un árbol binario se refiere al número de niveles del árbol binario.

Característica 2: Si la altura de un árbol binario es h, h≥0, entonces el árbol binario tiene al menos h elementos y como máximo 2h−1 elementos.

Prueba: dado que cada nivel debe tener al menos 1 elemento, el número de elementos es al menos h. Cada elemento tiene como máximo 2 nodos secundarios, por lo que los elementos del nodo de la i-ésima capa son como máximo 2i-1, i>0. Cuando h = 0, el número total de elementos es 0, que es 20 −1. Cuando h>0, el número total de elementos no excederá ∑hi=12i−1=2h−1.

Característica 3: La altura máxima de un árbol binario que contiene n elementos es n, y la altura mínima es ⌈log2 (n+1)⌉.

Prueba Dado que hay al menos un elemento en cada nivel, la altura no puede exceder n. De la propiedad 2, podemos saber que un árbol binario con altura h tiene como máximo 2h−1 elementos. Porque n≤2h−1, por lo tanto h≥log2(n+1). Como h es un número entero, h≥⌈log2(n+1)⌉.

Cuando un árbol binario con altura h tiene exactamente 2h−1 elementos, se le llama árbol binario completo. La siguiente imagen es un árbol binario completo con una altura de 4.

Supongamos que los elementos de un árbol binario completo de altura h están numerados del 1 al 2h−1 en orden de arriba a abajo y de izquierda a derecha, como se muestra en la figura anterior. Supongamos que k elementos se eliminan del árbol binario completo y su número es 2h−i, 1≤i≤k. El árbol binario resultante se denomina árbol binario completo. Los tres árboles binarios completos se muestran en la siguiente figura. Tenga en cuenta que un árbol binario completo es un caso especial de un árbol binario completo, y la profundidad de un árbol binario completo con n elementos es ⌈log2(n+1)⌉.

En un árbol binario completo, un elemento tiene muy buena correspondencia con el número de sus hijos. La relación se da en la Propiedad 4 a continuación.

Característica 4: Suponga que el número de secuencia de un elemento en un árbol binario completo es i, 1≤i≤n. Entonces se establece la siguiente relación:

1. Cuando i = 1, el elemento es la raíz del árbol binario. Si i>1, el número del nodo padre del elemento es ⌊i/2⌋.
2. Cuando 2i>n, el elemento no tiene subárbol izquierdo; de lo contrario, el número de su subárbol izquierdo es 2i.
3. Si 2i+1>n, el elemento no tiene subárbol derecho; de lo contrario, el número de su subárbol derecho es 2i+1.

árbol binario

1. Forma básica de árbol binario:

Los árboles binarios también se definen de forma recursiva y sus nodos se dividen en subárboles izquierdo y derecho. Lógicamente, los árboles binarios tienen cinco formas básicas:

(1) árbol binario vacío (2) Árbol binario con un solo nodo raíz (3) Solo el subárbol derecho (4) Solo el subárbol izquierdo (5) Árbol binario completo

Nota: Aunque los árboles binarios tienen muchas similitudes con los árboles, los árboles binarios no son un caso especial de árboles.

2. Dos conceptos importantes:(1) Árbol binario completo: un árbol binario en el que solo los grados de los nodos de los dos niveles inferiores son menores que 2 y los nodos del nivel inferior están concentrados en varias posiciones en el lado más izquierdo del nivel; (2) Árbol binario completo: un árbol binario en el que cada nodo, excepto los nodos de hoja, tiene cotiledones izquierdo y derecho, y todos los nodos de hoja están en la parte inferior.

3. Propiedades de los árboles binarios (1) En un árbol binario, el número total de nodos en el nivel i no excede 2 ^ (i-1); (2) Un árbol binario con profundidad h tiene como máximo 2^h-1 nodos (h>=1) y al menos h nodos; (3) Para cualquier árbol binario, si el número de nodos de hoja es N0 y el número total de nodos con grado 2 es N2, Entonces N0=N2+1; (4) La profundidad de un árbol binario completo con n nodos es int(log2n)+1 (5) Si los nodos de un árbol binario completo con N nodos se almacenan de manera secuencial, los nodos tienen la siguiente relación: Si I es el número de nodo, entonces si I <> 1, entonces el número de su nodo padre es I/2; Si 2I<=N, entonces el número de su hijo izquierdo (es decir, el nodo raíz del subárbol izquierdo) es 2I; si 2I>N, no queda ningún hijo; Si 2I+1<=N, entonces el número de nodo de su hijo derecho es 2I+1; si 2I+1>N, no existe un hijo correcto. (6) Dados N nodos, se pueden formar h (N) diferentes árboles binarios. h(N) es el enésimo término del número de Cattelan. h(n)=C(n,2*n)/(n+1).

árbol binario completo Un árbol binario con profundidad k y 2 elevado a (k) - 1 nodo. Características: La cantidad de nodos en cada nivel es la cantidad máxima de nodos.

La definición de un árbol binario completo: Un árbol binario con profundidad k y n nodos se llama árbol binario completo si y solo si cada uno de sus nodos corresponde a un nodo numerado del 1 al n en un árbol binario completo con profundidad k. Características: Los nodos hoja sólo pueden aparecer en los dos niveles más grandes; para cualquier nodo, si el nivel máximo de sus descendientes bajo la rama derecha es l, entonces el nivel máximo de sus descendientes bajo la rama izquierda debe ser l o l+1. Árbol binario completo: un árbol binario con una profundidad de k y 2 elevado a 1 - 1 nodos. Características: La cantidad de nodos en cada capa es la cantidad máxima de nodos. Un árbol binario completo es definitivamente un árbol binario completo. Un árbol binario completo no es necesariamente un árbol binario completo.

Pero el árbol de búsqueda binaria tiene un problema muy problemático. Si se insertan datos aleatorios en el árbol, el efecto de ejecución es muy bueno, pero si se insertan datos ordenados o en orden inverso, la velocidad de ejecución del árbol de búsqueda binaria se vuelve muy lenta. Porque cuando se ordenan los valores insertados, el árbol binario se desequilibra y se pierde su capacidad para buscar, insertar y eliminar rápidamente elementos de datos específicos.

Para resolver este problema, podemos utilizar árboles múltiples.

Un árbol 2-3-4 es un árbol múltiple, en el que cada nodo tiene hasta cuatro nodos secundarios y tres elementos de datos. El árbol 2-3-4, al igual que el árbol rojo-negro, también es un árbol equilibrado. Su eficiencia es ligeramente peor que la del árbol rojo-negro, pero es más fácil de programar. Los significados de 2, 3 y 4 en el nombre del árbol 2-3-4 se refieren a la cantidad de nodos secundarios que puede contener un nodo. Hay tres situaciones posibles para nodos que no son hoja:

Un nodo con un elemento de datos siempre tiene dos nodos secundarios; Un nodo con dos elementos de datos siempre tiene tres nodos secundarios; Un nodo con tres elementos de datos siempre tiene cuatro puntos de bytes.

Árbol de búsqueda binaria, árbol 2-3-4, árbol rojo-negro

árbol binario

Referencia; https://zh.wikipedia.org/wiki/二叉树 https://www.cnblogs.com/myjavascript/articles/4092746.html

Compartir

¿Cómo aprender estructuras de datos y algoritmos? Ya compartí esto una vez y recientemente vi un artículo que coincide mucho con mis pensamientos. Aquí hay un resumen:

Lo básico que necesitas antes de responder preguntas

1. Estructuras de datos comunes: listas vinculadas, árboles (como árboles binarios).
2. Ideas de algoritmos comunes: método codicioso, método de dividir y conquistar, método exhaustivo, programación dinámica, método de retroceso.
3. Algoritmos de clasificación comunes

Si ni siquiera sabes estas cosas más básicas, te resultará difícil resolver las preguntas y tendrás relativamente pocas ideas. Se puede decir que para muchas preguntas solo utilizarás métodos de fuerza bruta, por lo que aún debes dominar estos aspectos básicos antes de resolver las preguntas.

También debes leer libros y estudiar sistemáticamente.

Este último hay que practicarlo más. Durante el proceso de práctica, debes aprender las excelentes soluciones de otras personas. No lo hagas tú mismo y todo estará bien. Debe observar las implementaciones de otras personas y analizarlas usted mismo cuidadosamente.

Además de leetcode, también existen nuke.com y los siguientes sitios web para escribir preguntas. 18 sitios web para practicar tus habilidades de programación https://blog.csdn.net/lyn167/article/details/52134859 [codificador superior] https://www.topcoder.com/ HackerEarth http://www.hackerearth.com/ Coderbyte https://coderbyte.com/ Proyecto Euler: https://projecteuler.net/

Referencia: ¿Cómo aprendí estructuras de datos y algoritmos? :https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ El contenido de WeChat a menudo se pierde, aquí hay una copia: Enlace original: https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ

El estado de las estructuras de datos y los algoritmos es evidente para un programador. El artículo de hoy no está aquí para aconsejarle que aprenda estructuras de datos y algoritmos, ni tampoco para decirle lo importantes que son las estructuras de datos y los algoritmos.

Principalmente porque en los últimos días, los lectores me han preguntado cómo aprendí estructuras de datos y algoritmos, si hay atajos, si ver videos o leer libros, dónde estudiar preguntas, etc. Y algunos de ellos son juniors y seniors, así que estoy ansioso y preocupado por ustedes…

Así que hoy les compartiré cómo estudio habitualmente.

El atajo para aprender algoritmos es responder más preguntas Para ser honesto, cuando se trata de atajos, creo que se trata de tener los pies en la tierra, practicar más preguntas y responder más preguntas.

Sin embargo, si es un novato, es decir, ni siquiera ha aprendido estructuras de datos comunes, como listas vinculadas, árboles e ideas de algoritmos comunes, como recursividad, enumeración y programación dinámica, entonces no le recomiendo que estudie las preguntas. En su lugar, busque un libro para aprenderlos primero y luego responda las preguntas.

En otras palabras, si desea ir a un sitio web como leetcode para responder preguntas, primero debe tener una cierta base. Estas fundaciones incluyen:

1. Estructuras de datos comunes: listas vinculadas, árboles (como árboles binarios).

2. Ideas de algoritmos comunes: método codicioso, método de dividir y conquistar, método exhaustivo, programación dinámica, método de retroceso.

Los enumerados anteriormente son los más básicos. Es decir, antes de responder las preguntas, debe repasarlas nuevamente y luego responderlas. Si ni siquiera sabes estas cosas más básicas, te resultará difícil responder las preguntas y tendrás relativamente pocas ideas.

En definitiva, no tengas prisa. Primero, repase estos conceptos básicos y trate de comprenderlos antes de responder las preguntas. Aprendí estas estructuras de datos y algoritmos básicos en el segundo semestre de mi primer año. No vi los videos. Los aprendí leyendo libros. Los libros que leí en ese momento fueron:

1. Análisis de algoritmos y conceptos básicos del análisis: este libro es relativamente simple y se recomienda para principiantes.

2. Estructura de datos y análisis de algoritmos: descripción del lenguaje C: el código está escrito en C. Se recomienda leerlo.

3. Concurso de programación de desafíos (segunda edición): este también es un muy buen libro, recomendado.

Para obtener más información, puede leer mi otro artículo, que presenta estos libros: Libros sobre algoritmos y estructura de datos y beneficios en vídeo.

Para ser honesto, dediqué casi todo mi tiempo en ese semestre a estructuras de datos y algoritmos, pero hubo muy pocas preguntas, solo algunos ejemplos del libro. Entonces, después de repasar estos conceptos básicos, todavía era muy difícil ir a algunos sitios web para responder preguntas.

Así que no espere pensar que será bueno respondiendo preguntas después de aprender estas ideas. Sólo respondiendo más preguntas y practicando más se podrá mejorar tu sensibilidad.

Permítanme hablar sobre una columna muy popular hace un tiempo: [La belleza de las estructuras y algoritmos de datos]

No compré esta columna. Lo que quiero decir es que si lo compras, debes leerlo y no desperdiciarlo. No creas que te volverás más asombroso después de aprender esta columna. Si simplemente sigue el progreso del aprendizaje de esta columna, no perderá tiempo respondiendo preguntas ni haciendo prácticas. Entonces puedo garantizarte que seguirás siendo bueno en eso después de que termines de estudiar.

Para resumir:

No hay atajos para mejorar las estructuras de datos y los algoritmos. El mejor atajo es responder más preguntas. Sin embargo, el requisito previo para resolver las preguntas es que primero debe aprender algunas estructuras de datos básicas e ideas de algoritmos.

búsqueda de la perfección ¿Cómo responder preguntas? ¿Cómo afrontar un problema de algoritmo?

Creo que al hacer preguntas hay que buscar la perfección. Nunca termines una pregunta, envíala, pásala y luego pasa rápidamente a la siguiente.

Existe una cierta relación entre la mejora de las capacidades algorítmicas y el número de preguntas, pero no es una relación lineal. En otras palabras, al resolver un problema, debes esforzarte por resolver múltiples problemas. Si realmente no se te ocurre otra manera, puedes ir y ver cómo lo hacen otros. No sientan que es vergonzoso imitar lo que hacen los demás.

Cuando estoy haciendo una pregunta, cuando veo una pregunta, mi primer pensamiento puede ser resolverla de una manera muy burda, porque muchas preguntas son fáciles de resolver usando el método de fuerza bruta, pero la complejidad del tiempo es muy alta. Después de eso, lo pensaré lentamente y veré si hay otras formas de reducir la complejidad del tiempo o del espacio. Finalmente, miraré lo que otros han hecho. Por supuesto, no todas las preguntas se ejecutarán de esta manera.

Medir la calidad de un problema de algoritmo no es más que complejidad temporal y complejidad espacial. Por tanto, si queremos luchar por la perfección, debemos minimizar estos dos y hacer que se complementen.

Déjame darte un ejemplo:

Pregunta: Una rana puede saltar 1 o 2 escalones a la vez. ¿De cuántas maneras puede la rana saltar una escalera de n niveles?

He analizado esta cuestión en capítulos anteriores. Si no lo entiende, puede leer lo que escribí antes: Programación recursiva y dinámica — Capítulo básico 1

Método 1: Recursión violenta

Esta pregunta no es difícil. Quizás adopte el siguiente enfoque:

público estático int resolver (int n) { si(n == 1 || n == 2){ devolver n; }si no (n <= 0){ devolver 0; }más{ devolver resolver(n-1) + resolver(n-2); } }

La complejidad temporal de este enfoque es muy alta, exponencial. Pero si afortunadamente apruebas después de enviarla y luego pasas a la siguiente pregunta, entonces debes pensarlo detenidamente.

Método 2: intercambiar espacio por tiempo

Para luchar por la perfección, podemos considerar intercambiar espacio por tiempo: si piensas en esta pregunta detenidamente, encontrarás que muchas de ellas se repiten. Entonces puedes adoptar el siguiente enfoque:

//Utiliza un HashMap para guardar el estado calculado Mapa estático<Integer,Integer> mapa = nuevo HashMap(); público estático int resolver (int n) { si (n <= 0) devuelve 0; de lo contrario si(n <= 2){ devolver n; }else{//Si se ha calculado if(mapa.contieneClave(n)){ devolver mapa.get(n); }más{ int m = resolver(n-1) + resolver(n-2); mapa.put(n, m); devolver m; } } }

De esta forma, el tiempo se puede acortar considerablemente. En otras palabras, después de resolver un problema y descubrir que la complejidad del tiempo es muy alta, puede considerar si existe un método mejor y si puede intercambiar espacio por tiempo.

Método 3: secuencia de Fibonacci

De hecho, podemos reducir aún más la complejidad del espacio y no necesitamos un HashMap para guardar el estado:

público estático int resolver (int n) { si(n <= 0) devolver 0; si(n <= 2){ devolver n; }entero f1 = 0; entero f2 = 1; suma int = 0; para(int i = 1; i<= n; i++){ suma = f1 + f2; f1 = f2; f2 = suma; } suma de devolución; }

Te muestro esta pregunta no para enseñarte cómo hacerlo, sino para los siguientes propósitos:

1. Al responder preguntas, debemos esforzarnos por alcanzar la perfección.

2. No se me ocurren estos métodos, ¿qué debo hacer? Entonces podrás ver lo que otros han hecho. Más adelante, cuando encuentre problemas similares, tendrá más ideas y sabrá en qué dirección pensar.

3. Puedes comenzar con violencia simple para resolver un problema y optimizarlo poco a poco considerando la medida entre el espacio y el tiempo.

Recomendar algunos sitios web sobre cepillado de preguntas. Normalmente estudio preguntas en Leetcode y Niuke.com y me parecen bastante bien. Las preguntas no son muy difíciles.

En Niuke.com, estudié principalmente la oferta de Jianzhi, pero también hay un programa en línea llamado Leetcode, pero la cantidad de preguntas que contiene es relativamente pequeña. Un lugar muy conveniente para resolver preguntas en Niuke.com es el área de discusión. Habrá muchos grandes compartiendo sus métodos de resolución de problemas, por lo que no tenemos que ir a Baidu para encontrar la solución. Entonces, después de que lo termines y realmente no puedas pensar en nada más, puedes ir fácilmente y ver cómo lo hicieron otros.

En cuanto a leetcode, la mayoría de las preguntas tienen respuestas oficiales y también es un buen sitio web para repasar las preguntas. Puedes elegir uno de los dos o hacer ambos.

Por supuesto, hay otros sitios web que eliminan las preguntas, pero como no he eliminado los otros sitios web, no sé cómo borrarlas.

Hablemos de estructura de datos Anteriormente hablé principalmente sobre cómo suelo aprender algoritmos. En términos de métodos de estructura de datos, acabo de enumerar que debes aprender las listas vinculadas y los árboles (montones binarios), pero estos son los más básicos y deben dominarse antes de responder preguntas. Para las estructuras de datos, enumeraré algunas de las más importantes:

1. Lista enlazada (como lista enlazada unidireccional, lista enlazada bidireccional).

2. Árboles (como árboles binarios, árboles equilibrados, árboles rojo-negro).

3. Gráfico (como varios algoritmos para caminos más cortos).

4. Cola, pila, matriz.

Para estos, debes implementarlo tú mismo. Puedes leer libros o ver vídeos. Los novatos pueden ver videos primero, pero usted puede verlos en la etapa inicial. Después de eso, te sugiero que leas libros.

He recomendado videos y libros antes: Libros sobre algoritmos y estructura de datos y beneficios en vídeo.

Por ejemplo, para el árbol equilibrado, es posible que lo olvide después de un tiempo después de seguir el código del libro, pero no importa. Aunque lo haya olvidado, si lo implementó con código antes y lo entendió, cuando lo vea nuevamente, lo recordará rápidamente y comprenderá la idea rápidamente, y su capacidad de abstracción mejorará inconscientemente. Más adelante, si aprende sobre árboles rojo-negro y otras estructuras de datos, los aprenderá muy rápidamente.

lo mas importante Hazlo, hazlo, hazlo. Di cosas importantes tres veces.

No busques un montón de recursos, haz un plan de estudio y deja hasta un día determinado para hacerlo…

No hagas esto, pero cuando llegue tu pasión, hazlo de inmediato. No lo dejes hasta un día festivo o lo que sea. Mucha gente que piensa así acabará sin hacer nada.

No sientas que hay mucho que aprender y no sabes por dónde empezar. Como dije anteriormente, primero puedes aprender las más básicas y luego estudiar las preguntas. Estudiar las preguntas es una cuestión que requiere una perseverancia a largo plazo, uno o dos años. En el proceso de resolución de las preguntas, se puede intercalar el aprendizaje de otras estructuras de datos.