الفنون رقم 020

ARTS هو نشاط بدأه 由左耳朵耗子--陈皓: قم بإجراء سؤال واحد على الأقل عن خوارزمية leetcode كل أسبوع، واقرأ مقالًا تقنيًا واحدًا على الأقل باللغة الإنجليزية وعلق عليه، وتعلم مهارة فنية واحدة على الأقل، وشارك المقالة مع الآراء والأفكار. (أي أن الخوارزمية والمراجعة والنصائح والمشاركة يشار إليها باسم ARTS) وتستمر لمدة عام واحد على الأقل.

الفنون 020

هذه المادة 20

سؤال خوارزمية الخوارزمية

637. متوسط المستويات في الشجرة الثنائية

الصعوبة ** السهل **

مثال 1:

ملاحظة:

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

الحل

اللغة: ج

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

الطريقة الأولى: يجب أن تكون هذه هي الطريقة الأسهل للتفكير فيها، وهي حساب طبقة تلو الأخرى؛ أثناء حساب الطبقة الحالية، قم بتخزين العقد في الطبقة السفلية.

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

ما يلي هو تنفيذ الآخرين، يمكنك التعلم منه الطريقة الثانية: يتم حساب هذا التنفيذ أيضًا طبقة تلو الأخرى، لكن التنفيذ أبسط قليلاً من تطبيقي. يقوم مباشرة بحساب مجموع العقد في كل طبقة أثناء حساب العمق. العيب هو أنه يستخدم قيمًا ثابتة ومتغيرات عالمية.

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

الطريقة الثالثة: هذا التنفيذ له نفس فكرة التنفيذ السابق، لكنني أعتقد أنه أكثر أناقة من التنفيذ السابق.

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

مراجعة

تحسين وقت بدء تشغيل تطبيق iOS: https://dandan2009.github.io/2018/12/18/optimizing-app-startup-time/

نصائح

تقوم طريقتا الكتابة التاليتان بتنفيذ الرسوم المتحركة بعد 5 ثوانٍ، لكن التأثيرات مختلفة. ستتم مقاطعة الطريقة الأولى للكتابة عن طريق تحديث عرض الجدول، مما يتسبب في التنفيذ المبكر والتغيير المباشر إلى الحالة بعد الرسوم المتحركة. الطريقة الأخيرة لن تفعل ذلك، لماذا؟ اكتشفت لاحقًا أنه إذا كانت هناك عملية إعادة رسم لواجهة المستخدم أثناء تنفيذ الرسوم المتحركة، فسيتم مقاطعة الرسوم المتحركة أيضًا. لماذا؟

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

شارك

قامت العديد من الشركات بتسريح موظفيها مؤخرًا، بما في ذلك Sina Chengdu وMeituan Shenzhen وPhilips Technology وDianrong Chengdu. يقال إن شركتنا ستقوم بتسريح 10٪ من موظفيها. هل الإنترنت في تراجع حقاً؟