ARTES #020

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 020

Este é o artigo 20

Pergunta sobre algoritmo de algoritmo

637. Média dos níveis na árvore binária

Dificuldade Fácil

Exemplo 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].

Solução

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 deve ser o método mais fácil de imaginar, calculando camada por camada; ao calcular a camada atual, armazene os nós na camada 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;
}

A seguir está a implementação de outras pessoas, você pode aprender com ela Método 2: Esta implementação também é calculada camada por camada, mas a implementação é um pouco mais simples que a minha. Ele calcula diretamente a soma dos nós em cada camada enquanto calcula a profundidade. A desvantagem é que utiliza valores fixos e variáveis ​​globais.

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 implementação tem a mesma ideia da anterior, mas acho que é mais elegante que a implementação 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;
}

Revisão

Otimize o tempo de inicialização do aplicativo iOS: https://dandan2009.github.io/2018/12/18/optimizing-app-startup-time/

DICAS

Os dois métodos de escrita a seguir executam a animação após 5 segundos, mas os efeitos são diferentes. A primeira forma de escrita será interrompida pela atualização da tableview, causando execução antecipada e mudança direta para o estado após a animação. A última forma não, por quê? Posteriormente, descobri que se houver uma operação de redesenho da UI durante a execução da animação, a animação também será interrompida. Por que?

[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) {
}];

e

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

Compartilhar

Muitas empresas têm demitido funcionários recentemente, incluindo Sina Chengdu, Meituan Shenzhen, Philips Technology e Dianrong Chengdu. Diz-se que nossa empresa está demitindo 10% de seus funcionários. A Internet está realmente em declínio?