ARTES #018

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 018 este es el articulo 18

Pregunta sobre el algoritmo del algoritmo

107. Recorrido de orden de nivel de árbol binario II (Recorrido de orden de nivel de árbol binario II)

Dificultad de la pregunta: Fácil

Dado un árbol binario, devuelve un recorrido jerárquico ascendente de sus valores de nodo. (Es decir, atravesar de izquierda a derecha capa por capa desde la capa donde está el nodo hoja hasta la capa donde está el nodo raíz)

Por ejemplo: Dado un árbol binario [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Devuelve su recorrido jerárquico ascendente como:

[
  [15,7],
  [9,20],
  [3]
]

Solución

Idioma: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    
}

/**

• Definición de un nodo de árbol binario.
• estructura NodoÁrbol {
• valor int;
• estructura TreeNode *izquierda;
• estructura TreeNode *derecha;
• }; / /*
• Devuelve una matriz de matrices de tamaño *returnSize.
• Los tamaños de las matrices se devuelven como *matriz columnSizes.
• Nota: Tanto la matriz devuelta como la matriz columnSizes deben estar mal asignadas, se supone que la persona que llama llama gratis(). / int ordendenivel(struct TreeNode* root, int** columnSizes, int* returnSize) {

}

Método 1

int getLevelOrderBottom(struct TreeNode* root, int*** ArrayRet, int** columnSizes, int length, int level) {
    if (root == NULL) return length;
    int size = length;
    if (level>size - 1) {
        *ArrayRet = realloc(*ArrayRet, sizeof(int*)*(size + 1));
        (*ArrayRet)[level]= calloc(0, sizeof(int));
        *columnSizes = realloc(*columnSizes, sizeof(int)*(size + 1));
        (*columnSizes)[level] = 0;
        size++;
    }
    (*ArrayRet)[level] = realloc((*ArrayRet)[level], sizeof(int)*((*columnSizes)[level] + 1));
    (*ArrayRet)[level][(*columnSizes)[level]] = root->val;
    (*columnSizes)[level] += 1;
    size = getLevelOrderBottom(root->left, ArrayRet, columnSizes, size, level + 1);
    size = getLevelOrderBottom(root->right, ArrayRet, columnSizes, size, level + 1);
    return size;
}
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    int **ArrayRet = calloc(0, sizeof(int *));
    *returnSize = getLevelOrderBottom(root, &ArrayRet, columnSizes, 0, 0);

    //reverse the array
    int **ret = calloc(*returnSize, sizeof(int *));
    for(int i=0;i<*returnSize;i++){
        ret[i]=calloc((* columnSizes)[*returnSize-i-1],sizeof(int));
        memcpy(ret[i],ArrayRet[*returnSize-i-1],sizeof(int)*(* columnSizes)[*returnSize-i-1]);
    }
    int k=0,j=* returnSize-1;
    while(k<j){
        int tmp=(* columnSizes)[k];
        (* columnSizes)[k++]=(* columnSizes)[j];
        (* columnSizes)[j--]=tmp;
    }
    return ret;
}

Método 2, del registro de envío de LeetCode:

int GetdepthofTree(struct TreeNode* root){
    if (!root) return 0;
    int left = GetdepthofTree(root->left);
    int right = GetdepthofTree(root->right);
    if (left > right)
        return left+1;
    else
        return right+1;
}
 
 
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    if (!root){
        return NULL;
    }
    //获取二叉树的深度，最大层数或者说
    int depth = *returnSize = GetdepthofTree(root);
    
    //ret是一个指向一个二维数组的指针，这一块地址是我们自己开辟的，需要malloc
    int** ret = (int**)malloc(depth*sizeof(int*));
    
    //columnSizes是一个指向指针的指针，这个地址已经指定了，就是说这个地址了存放的下一个地址已经确定了，但是下一个地址里存放的还是地址，这个地址任然不确定，那么就需要malloc了
    //*columnSizes是一个指向一个一维数组的指针，数组的大小也是depth
    
    *columnSizes = (int*)malloc(depth*sizeof(int));
    int front = 0, back = 0;
    struct TreeNode* queue[10000];
    queue[back++] = root;
    while (front < back){
        int start = front, end = back;
        (*columnSizes)[--depth] = end - start;
        front = end;
        //开始的时候我们只给了ret的地址，因为ret是一个二维数组的起始地址，但是这个二维数组里面的一维数组的地址并没有确定，就需要malloc来确定
        ret[depth] = (int*)malloc((end - start)*sizeof(int));
        for (int i=start; i<end; i++){
            ret[depth][i-start] = queue[i]->val;
            if (queue[i]->left) queue[back++] = queue[i]->left;
            if (queue[i]->right) queue[back++] = queue[i]->right;
        }
    }
    return ret;
}

Revisión

Ver también: Estructuras de datos y algoritmos comunes: https://dandan2009.github.io/2018/11/28/data-structures-part3-language-support/

CONSEJOS

Una guía para principiantes sobre la codificación de sombreadores de gráficos.

https://gamedevelopment.tutsplus.com/series/a-beginners-guide-to-coding-graphics-shaders--cms-834

Esta serie es bastante buena. Puede consultarlo como tutorial introductorio sobre Graphics Shaders.

iOS simula un método de red débil:

1. Utilice un dispositivo real. Hay una opción en desarrollo y una opción de Acondicionador de enlace de red en la configuración del dispositivo real.

Seleccione uno de los tipos de redes para configurar la velocidad de la red

2. Configure el simulador en un entorno de red débil: Método 1: vaya al Centro de desarrolladores de Apple para descargar herramientas adicionales para Xcode

   Abra Preferencias del sistema, busque Network Link Conditioner y haga doble clic para abrirlo.

Los acondicionadores de enlace de red son efectivos para todo el sistema y la velocidad del acceso normal a Internet también será limitada, por lo que cuando finalice la prueba, recuerde detener el acondicionador de enlace de red.

Método 2: Carlos

Compartir

Herramientas de aprendizaje visual y sitios web que delimitan varios algoritmos:

Algoritmos y estructuras de datos de la Universidad de San Francisco http://hao.jobbole.com/visualizing-algorithms-and-data-structure/

VisuAlgo: Aprende algoritmos y estructuras de datos a través de animación http://hao.jobbole.com/visualgo/

Algomation: una plataforma de aprendizaje para ver, crear y compartir algoritmos http://hao.jobbole.com/algomation/

Visualizador de algoritmos: http://algorithm-visualizer.org Algorithm Visualizer tiene más de 10,6k estrellas en GitHub: https://github.com/algorithm-visualizer/algorithm-visualizer

Comparta un sitio web de aprendizaje de inglés: https://learnamericanenglishonline.com/Red Level/R1 Do.html