SENI #018

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 018

Ini adalah pasal 18

Pertanyaan algoritma algoritma

107. Traversal Urutan Tingkat Pohon Biner II (Traversal Urutan Tingkat Pohon Biner II)

Kesulitan Pertanyaan: Mudah

Dengan adanya pohon biner, kembalikan traversal hierarki bottom-up dari nilai simpulnya. (Yaitu, melintasi dari kiri ke kanan lapis demi lapis dari lapisan tempat simpul daun berada ke lapisan tempat simpul akar berada)

Misalnya: Diberikan pohon biner [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Kembalikan traversal hierarki bottom-up sebagai:

[
  [15,7],
  [9,20],
  [3]
]

Solusi

Bahasa: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    
}

/**

• Definisi untuk simpul pohon biner.
• struct TreeNode {
• ke dalam nilai;
• struct TreeNode *kiri;
• struct TreeNode *kanan;
• }; / /*
• Mengembalikan larik larik dengan ukuran *returnSize.
• Ukuran array dikembalikan sebagai array *columnSizes.
• Catatan: Array yang dikembalikan dan array columnSizes harus di malloced, asumsikan panggilan pemanggil gratis(). / int levelOrder(struct TreeNode* root, int** ukuran kolom, int* ukuran kembalian) {

}

Metode 1

int getLevelOrderBottom(struct TreeNode* root, int*** ArrayRet, int** columnSizes, int length, int level) {
    if (root == NULL) return length;
    int size = length;
    if (level>size - 1) {
        *ArrayRet = realloc(*ArrayRet, sizeof(int*)*(size + 1));
        (*ArrayRet)[level]= calloc(0, sizeof(int));
        *columnSizes = realloc(*columnSizes, sizeof(int)*(size + 1));
        (*columnSizes)[level] = 0;
        size++;
    }
    (*ArrayRet)[level] = realloc((*ArrayRet)[level], sizeof(int)*((*columnSizes)[level] + 1));
    (*ArrayRet)[level][(*columnSizes)[level]] = root->val;
    (*columnSizes)[level] += 1;
    size = getLevelOrderBottom(root->left, ArrayRet, columnSizes, size, level + 1);
    size = getLevelOrderBottom(root->right, ArrayRet, columnSizes, size, level + 1);
    return size;
}
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    int **ArrayRet = calloc(0, sizeof(int *));
    *returnSize = getLevelOrderBottom(root, &ArrayRet, columnSizes, 0, 0);

    //reverse the array
    int **ret = calloc(*returnSize, sizeof(int *));
    for(int i=0;i<*returnSize;i++){
        ret[i]=calloc((* columnSizes)[*returnSize-i-1],sizeof(int));
        memcpy(ret[i],ArrayRet[*returnSize-i-1],sizeof(int)*(* columnSizes)[*returnSize-i-1]);
    }
    int k=0,j=* returnSize-1;
    while(k<j){
        int tmp=(* columnSizes)[k];
        (* columnSizes)[k++]=(* columnSizes)[j];
        (* columnSizes)[j--]=tmp;
    }
    return ret;
}

Metode 2, dari catatan pengiriman LeetCode:

int GetdepthofTree(struct TreeNode* root){
    if (!root) return 0;
    int left = GetdepthofTree(root->left);
    int right = GetdepthofTree(root->right);
    if (left > right)
        return left+1;
    else
        return right+1;
}
 
 
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    if (!root){
        return NULL;
    }
    //获取二叉树的深度，最大层数或者说
    int depth = *returnSize = GetdepthofTree(root);
    
    //ret是一个指向一个二维数组的指针，这一块地址是我们自己开辟的，需要malloc
    int** ret = (int**)malloc(depth*sizeof(int*));
    
    //columnSizes是一个指向指针的指针，这个地址已经指定了，就是说这个地址了存放的下一个地址已经确定了，但是下一个地址里存放的还是地址，这个地址任然不确定，那么就需要malloc了
    //*columnSizes是一个指向一个一维数组的指针，数组的大小也是depth
    
    *columnSizes = (int*)malloc(depth*sizeof(int));
    int front = 0, back = 0;
    struct TreeNode* queue[10000];
    queue[back++] = root;
    while (front < back){
        int start = front, end = back;
        (*columnSizes)[--depth] = end - start;
        front = end;
        //开始的时候我们只给了ret的地址，因为ret是一个二维数组的起始地址，但是这个二维数组里面的一维数组的地址并没有确定，就需要malloc来确定
        ret[depth] = (int*)malloc((end - start)*sizeof(int));
        for (int i=start; i<end; i++){
            ret[depth][i-start] = queue[i]->val;
            if (queue[i]->left) queue[back++] = queue[i]->left;
            if (queue[i]->right) queue[back++] = queue[i]->right;
        }
    }
    return ret;
}

Ulasan

Lihat juga: Struktur dan algoritma data umum: https://dandan2009.github.io/2018/11/28/data-structures-part3-language-support/

TIPS

Panduan Pemula untuk Mengkodekan Shader Grafis.

https://gamedevelopment.tutsplus.com/series/a-beginners-guide-to-coding-graphics-shaders--cms-834

Seri ini cukup bagus. Anda dapat memeriksanya sebagai tutorial pengantar tentang Graphics Shaders.

iOS mensimulasikan metode jaringan lemah:

1. Gunakan perangkat asli. Ada opsi yang sedang dikembangkan dan opsi Network Link Conditioner di pengaturan perangkat sebenarnya.

Pilih salah satu jenis jaringan untuk mengatur kecepatan jaringan

2. Atur simulator ke lingkungan jaringan yang lemah: Metode 1: Buka Pusat Pengembang Apple untuk mengunduh Alat Tambahan untuk Xcode

   Buka System Preferences, temukan Network Link Conditioner, dan klik dua kali untuk membukanya.

Network Link Conditioner efektif untuk seluruh sistem, dan kecepatan akses Internet biasa juga akan dibatasi, jadi ketika pengujian selesai, ingatlah untuk menghentikan Network Link Conditioner.

Metode 2: Charles

Bagikan

Alat pembelajaran visual dan situs web yang membatasi beberapa algoritma:

Struktur dan Algoritma Data Universitas San Francisco http://hao.jobbole.com/visualizing-algorithms-and-data-structure/

VisuAlgo: Pelajari algoritma dan struktur data melalui animasi http://hao.jobbole.com/visualgo/

Algomation: platform pembelajaran untuk melihat, membuat dan berbagi algoritma http://hao.jobbole.com/algomation/

Visualisasi Algoritma: http://algorithm-visualizer.org Algorithm Visualizer memiliki 10,6k+ bintang di GitHub: https://github.com/algorithm-visualizer/algorithm-visualizer

Bagikan situs web pembelajaran bahasa Inggris: https://learnamericanenglishonline.com/Red Level/R1 Do.html