ARTS #020

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.

ARTS 020

This is article 20

Algorihm algorithm question

637. Average of Levels in Binary Tree

Difficulty Easy

Example 1:

Note:

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

Solution

Language: 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().
 */

Method 1: This should be the easiest method to think of, calculating layer by layer; while calculating the current layer, store the nodes in the lower layer.

//计算深度
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;
}

The following is other people’s implementation, you can learn from it Method 2: This implementation is also calculated layer by layer, but the implementation is a little simpler than mine. It directly calculates the sum of nodes in each layer while calculating the depth. The disadvantage is that it uses fixed values ​​and global variables.

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;
}

Method 3: This implementation has the same idea as the previous one, but I think it is more elegant than the previous implementation.

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;
}

Review

Optimize iOS App startup time: https://dandan2009.github.io/2018/12/18/optimizing-app-startup-time/

TIPS

The following two writing methods execute the animation after 5 seconds, but the effects are different. The first way of writing will be interrupted by tableview refresh, causing early execution and directly changing to the state after animation. The latter way will not, why? Later, I discovered that if there is a UI redrawing operation during the execution of the animation, the animation will also be interrupted. Why?

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

and

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

Share

Many companies have been laying off employees recently, including Sina Chengdu, Meituan Shenzhen, Philips Technology, and Dianrong Chengdu. Our company is said to be laying off 10% of its employees. Is the Internet really in decline?