ARTES #018

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

ARTES 018

Este é o artigo 18

Pergunta sobre algoritmo de algoritmo

107. Traversal de ordem de nível de árvore binária II (Traversal de ordem de nível de árvore binária II)

Dificuldade da pergunta: Fácil

Dada uma árvore binária, retorne um percurso hierárquico de baixo para cima dos valores de seus nós. (Ou seja, atravesse da esquerda para a direita, camada por camada, da camada onde está o nó folha até a camada onde está o nó raiz)

Por exemplo: Dada uma árvore binária [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Retorne sua travessia hierárquica de baixo para cima como:

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

Solução

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) {
    
}

/**

• Definição para um nó de árvore binária.
• estrutura TreeNode {
• valor interno;
• struct TreeNode *esquerda;
• struct TreeNode *direita;
• }; / /*
• Retorna um array de arrays de tamanho *returnSize.
• Os tamanhos das matrizes são retornados como matriz *columnSizes.
• Nota: Tanto a matriz retornada quanto a matriz columnSizes devem ser mallocadas, suponha que o chamador chame free(). / int levelOrder(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, do registro de envio do 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;
}

Revisão

Veja também: Estruturas de dados e algoritmos comuns: https://dandan2009.github.io/2018/11/28/data-structures-part3-language-support/

DICAS

Um guia para iniciantes na codificação de shaders gráficos.

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

Essa série é muito boa. Você pode conferir como um tutorial introdutório sobre Graphics Shaders.

iOS simula método de rede fraca:

1. Use um dispositivo real. Existe uma opção em desenvolvimento e uma opção Network Link Conditioner nas configurações do dispositivo real.

Selecione um dos tipos de redes para definir a velocidade da rede

2. Configure o simulador para um ambiente de rede fraco: Método 1: acesse o Apple Developer Center para baixar ferramentas adicionais para Xcode

   Abra as Preferências do Sistema, encontre Network Link Conditioner e clique duas vezes para abri-lo.

Os condicionadores de link de rede são eficazes para todo o sistema e a velocidade do acesso normal à Internet também será limitada; portanto, quando o teste for concluído, lembre-se de interromper o condicionador de link de rede.

Método 2: Carlos

Compartilhar

Ferramentas de aprendizagem visual e sites que demarcam diversos algoritmos:

Estruturas de dados e algoritmos da Universidade de São Francisco http://hao.jobbole.com/visualizing-algorithms-and-data-structure/

VisuAlgo: Aprenda algoritmos e estruturas de dados por meio de animação http://hao.jobbole.com/visualgo/

Algomation: uma plataforma de aprendizagem para visualizar, criar e compartilhar algoritmos http://hao.jobbole.com/algomation/

Visualizador de algoritmo: http://algorithm-visualizer.org Algorithm Visualizer tem mais de 10,6 mil estrelas no GitHub: https://github.com/algorithm-visualizer/algorithm-visualizer

Compartilhe um site de aprendizagem de inglês: https://learnamericanenglishonline.com/Red Level/R1 Do.html