SENI #020

SENI adalah kegiatan yang diprakarsai oleh 由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI) dan bertahan setidaknya selama satu tahun.

SENI 020

Ini adalah pasal 20

Pertanyaan algoritma algoritma

637. Rata-rata Level di Pohon Biner

Kesulitan Mudah

Contoh 1:

Catatan:

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

Solusi

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

Metode 1: Ini seharusnya menjadi metode termudah untuk dipikirkan, menghitung lapis demi lapis; saat menghitung lapisan saat ini, simpan node di lapisan bawah.

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

Berikut ini adalah implementasi orang lain, Anda bisa mengambil pelajaran darinya Metode 2: Implementasi ini juga dihitung lapis demi lapis, namun implementasinya sedikit lebih sederhana dari saya. Ini secara langsung menghitung jumlah node di setiap lapisan sambil menghitung kedalamannya. Kerugiannya adalah menggunakan nilai tetap dan variabel global.

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

Cara 3: Implementasi ini mempunyai ide yang sama dengan implementasi sebelumnya, namun menurut saya lebih elegan dari implementasi sebelumnya.

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

Ulasan

Optimalkan waktu startup Aplikasi iOS: https://dandan2009.github.io/2018/12/18/optimizing-app-startup-time/

TIPS

Dua metode penulisan berikut mengeksekusi animasi setelah 5 detik, namun efeknya berbeda. Cara penulisan pertama akan terganggu oleh penyegaran tampilan tabel, menyebabkan eksekusi awal dan langsung berubah ke keadaan setelah animasi. Cara terakhir tidak akan berhasil, kenapa? Belakangan, saya menemukan bahwa jika ada operasi menggambar ulang UI selama eksekusi animasi, animasinya juga akan terganggu. Mengapa?

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

dan

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

Bagikan

Banyak perusahaan yang memberhentikan karyawannya baru-baru ini, termasuk Sina Chengdu, Meituan Shenzhen, Philips Technology, dan Dianrong Chengdu. Perusahaan kami dikabarkan akan memberhentikan 10% karyawannya. Apakah Internet benar-benar mengalami kemunduran?