ARTES #020

ARTS28 de diciembre de 2018 a las 04:521 min read

ARTES #020

简体中文 العربية English Español Bahasa Indonesia Português

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 020 este es el articulo 20

Pregunta sobre el algoritmo del algoritmo

637. Promedio de niveles en el árbol binario

Dificultad Fácil

Ejemplo 1:

Nota:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11\. Hence return [3, 14.5, 11].

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().
 */
void masprin (double *mas, int nums);
int Depf_tree(struct TreeNode *root);
double Diver (struct TreeNode *root, int depf, int cur_depf);
int Diver_2 (struct TreeNode *root, int depf, int cur_depf);
/**
 * 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().
 */

Método 1: Este debería ser el método más fácil de imaginar: calcular capa por capa; mientras calcula la capa actual, almacene los nodos en la capa inferior.

//计算深度
int LevelsTree(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    }
    int lefLevels =  LevelsTree(root->left);
    int rightLevels =  LevelsTree(root->right);
    return lefLevels > rightLevels ? lefLevels + 1 : rightLevels + 1 ;
}

double* averageOfLevels(struct TreeNode* root, int* returnSize) {
    *returnSize = LevelsTree(root);//树的深度
    if (* returnSize == 0) {
        return NULL;
    }
    
    
    double* averageOfLevels = (double*)malloc(sizeof(double) * (*returnSize));
    struct TreeNode** levels = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1);
    levels[0] = root;
    
    int index = 0;
    int preindex = index;
    
    for(int i =0;i< *returnSize;i++){
        int j = 0;
        double sum = 0;
        int count = 0;

        struct TreeNode** tempLevels  = NULL;
        struct TreeNode*  t = levels[j];;
    
        while (t != NULL) {
            sum = sum + t->val;
            count++;
            
            if (t->left) {
                if (tempLevels == NULL) {
                     tempLevels = (struct TreeNode**)malloc(sizeof(struct TreeNode*) *  1);
                     tempLevels[index] = t->left;
                }
                else{
                    ++index;
                    tempLevels = (struct TreeNode**)realloc(tempLevels,sizeof(struct TreeNode*)*(index+1));
                    tempLevels[index] = t->left;
                }
            }
            
            if (t->right) {
                if (tempLevels == NULL) {
                    tempLevels = (struct TreeNode**)malloc(sizeof(struct TreeNode*) *  1);
                    tempLevels[index] = t->right;
                }
                else{
                    ++index;
                    tempLevels = (struct TreeNode**)realloc(tempLevels,sizeof(struct TreeNode*)*(index+1));
                    tempLevels[index] = t->right;
                }
            }
            
            //
            ++j;
            if (j<=preindex) {
                t = levels[j];
            }
            else{
                t = NULL;
            }
        }
        
        preindex = index;
        index = 0;
       
        averageOfLevels[i] = sum/count;
        
        if (levels != NULL) {
            free(levels);
            levels = NULL;
        }
        levels = tempLevels;
    }
    if (levels != NULL) {
        free(levels);
        levels = NULL;
    }
    
    return averageOfLevels;
}

La siguiente es la implementación de otras personas, puedes aprender de ella. Método 2: esta implementación también se calcula capa por capa, pero la implementación es un poco más simple que la mía. Calcula directamente la suma de nodos en cada capa mientras calcula la profundidad. La desventaja es que utiliza valores fijos y variables globales.

double lv[10000];
int lc[10000];
int size;

void dfs(struct TreeNode* root, int level) {
    if(root == 0) return;
    if(level > size) {
        size = level;
    }
    lv[level] += (double)root->val;
    lc[level]++;
    dfs(root->left, level+1);
    dfs(root->right, level+1);
}

double* averageOfLevels(struct TreeNode* root, int* returnSize) {
    for(int i = 0; i < 10000; i++) {
        lv[i] = lc[i] = 0;
    }
    size = -1;
    dfs(root, 0);
    if(size == -1) return 0;
    double* res = (double *)malloc(sizeof(double) * size+1);
    for(int i = 0; i <= size; i++) {
        res[i] = lv[i] / lc[i];
    }
    *returnSize = size+1;
    return res;
}

Método 3: Esta implementación tiene la misma idea que la anterior, pero creo que es más elegante que la implementación anterior.

int GetTreeDepth(struct TreeNode* root){
    int LDepth, RDepth;
    LDepth = 0;
    RDepth = 0;
    if(!root) return 0;
    if(root->left) LDepth = GetTreeDepth(root->left);
    if(root->right) RDepth = GetTreeDepth(root->right);
    return (LDepth > RDepth ? LDepth : RDepth) + 1;
}
void GetPerLevel(struct TreeNode* root, double* sum, int *num, int Level) {
    if(!root) return;
    sum[Level] += (double)(root->val);
    num[Level]++;
    Level++;
    if(root->left) GetPerLevel(root->left, sum, num, Level);
    if(root->right) GetPerLevel(root->right, sum, num, Level);
    return;
}
double* averageOfLevels(struct TreeNode* root, int* returnSize) {
    int Level = 0;
    *returnSize = GetTreeDepth(root);
    double *sum = (double *)malloc(sizeof(double) * *returnSize);
    int *num = (int *)malloc(sizeof(int) * *returnSize);
    memset(sum, 0, sizeof(double) * *returnSize);
    memset(num, 0, sizeof(int) * *returnSize);
    GetPerLevel(root, sum, num, Level);
    for(int i = 0; i < *returnSize; i++) sum[i] /= num[i];
    return sum;
}

Revisión

Optimice el tiempo de inicio de la aplicación iOS: https://dandan2009.github.io/2018/12/18/optimizing-app-startup-time/

CONSEJOS

Los dos métodos de escritura siguientes ejecutan la animación después de 5 segundos, pero los efectos son diferentes. La primera forma de escritura será interrumpida por la actualización de la vista de tabla, lo que provocará una ejecución temprana y cambiará directamente al estado después de la animación. La última forma no lo hará, ¿por qué? Más tarde, descubrí que si hay una operación de redibujo de la interfaz de usuario durante la ejecución de la animación, la animación también se interrumpirá. ¿Por qué?

[UIView animateWithDuration:0.5 delay:5.0 options:(UIViewAnimationOptionAllowUserInteraction) animations:^{
    weakSelf.coverView.frame = (CGRect){0,5,weakSelf.width,weakSelf.height};
    weakSelf.loadImg.frame = (CGRect){weakSelf.width/4,weakSelf.height,weakSelf.width/2,weakSelf.width/2/16*7};
} completion:^(BOOL finished) {
}];

dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(5 * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
    [UIView animateWithDuration:0.5 delay:0 options:(UIViewAnimationOptionAllowUserInteraction) animations:^{
        weakSelf.coverView.frame = (CGRect){0,5,weakSelf.width,weakSelf.height};
        weakSelf.loadImg.frame = (CGRect){weakSelf.width/4,weakSelf.height,weakSelf.width/2,weakSelf.width/2/16*7};
        
    } completion:^(BOOL finished) {
    }];
});

Muchas empresas han estado despidiendo empleados recientemente, incluidas Sina Chengdu, Meituan Shenzhen, Philips Technology y Dianrong Chengdu. Se dice que nuestra empresa va a despedir al 10% de sus empleados. ¿Está realmente Internet en declive?

FAQ