SENI #015

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 015

Ini adalah pasal 15

Pertanyaan algoritma algoritma

Pertanyaan algoritma yang kami lakukan minggu ini adalah preorder traversal, inorder traversal, dan postorder traversal dari pohon biner. Setiap jenis traversal diimplementasikan secara rekursif dan iteratif. Implementasi rekursif dari ketiga traversal pada dasarnya sama, namun implementasi iteratif dari ketiga traversal berbeda. Diantaranya, implementasi berulang dari post-order traversal adalah yang paling sulit.

Perbedaan antara rekursi dan iterasi: Rekursi: Teknik pemrograman di mana suatu program memanggil dirinya sendiri disebut rekursi Iterasi: Gunakan nilai asli variabel untuk menghitung nilai variabel baru. Iterasi berarti A terus memanggil B.

Contoh cerita film: Iterasi - “Tepi Masa Depan” Rekursi - “Permulaan”

参见：
https://blog.csdn.net/laoyang360/article/details/7855860
Google：递归 迭代
斐波那契数列为:0,1,1,2,3,5...
//迭代实现斐波那契数列  
long fab_iteration(int index)  
{  
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        long f1 = 1L;  
        long f2 = 1L;  
        long f3 = 0;  
        for(int i = 0; i < index-2; i++)  
        {     
            f3 = f1 + f2; //利用变量的原值推算出变量的一个新值  
            f1 = f2;  
            f2 = f3;  
        }  
         return f3;  
    }  
}  
  
//递归实现斐波那契数列  
 long fab_recursion(int index)  
 {      
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        return fab_recursion(index-1)+fab_recursion(index-2);    //递归求值  
    }  
} 

Penjelajahan praorder: simpul akar —> subpohon kiri —> subpohon kanan Penjelajahan berurutan: subpohon kiri —> simpul akar —> subpohon kanan Penjelajahan pasca pesanan: subpohon kiri —> subpohon kanan —> simpul akar

94. Traversal Inorder Pohon Biner

Kesulitan: Sedang

Diberikan pohon biner, kembalikan traversal inorder dari nilai simpulnya.

Contoh:

**Input:** [1,null,2,3]
   1
    \
     2
    /
   3

**Output:** [1,3,2]```

**Tindak lanjut:** Solusi rekursif itu sepele, dapatkah Anda melakukannya secara berulang?



#### Solusi

Bahasa: **C**

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

// solusi rekursif implementasi rekursif

int* inorderTraversal(struct TreeNode* root, int* returnSize) {

    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    //左子树
    int returnSizeLeft = 0;
    int *left = NULL;
    if(root->left != NULL){
        left= inorderTraversal(root->left, &returnSizeLeft);
    }
    
    //根结点
    
    //右子树
    int returnSizeRight = 0;
    int *right = NULL;
    if(root->right!= NULL){
        right = inorderTraversal(root->right, &returnSizeRight);
    }
    
    *returnSize = returnSizeLeft + returnSizeRight + 1;
    int* traversalResult=(int*)malloc((*returnSize)*sizeof(int));
    
    int index = 0;
    for (int i =0; i<returnSizeLeft; i++) {
        traversalResult[index++] = left[i];
    }
    free(left);
    
    traversalResult[index++] = root->val;
    
    for (int i =0; i<returnSizeRight; i++) {
        traversalResult[index++] = right[i];
    }
    free(right);

    return traversalResult;
}

// solusi iteratif implementasi iteratif

//迭代算法 iteratively
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
   struct TreeNode** traversalResult=(struct TreeNode**)malloc(1000*sizeof(struct TreeNode*));
   if (root == NULL) {
       *returnSize = 0;
       return NULL;
   }
   int *result=(int*)malloc(1000*sizeof(int));
   *returnSize = 0;
   
   int index = 0;
   struct TreeNode* p = root;
   
   while (p != NULL || index>0) {
       printf("%d",index);
       while (p != NULL) {
               traversalResult[index++] = p;
               p = p->left;
       }
       if (index >= 1) {
           p = traversalResult[--index];
           result[(*returnSize )++] = p->val;
           p = p->right;
       }
   }
   return result;
}

144. Traversal Preorder Pohon Biner

Kesulitan: Sedang

Diberikan pohon biner, kembalikan traversal preorder dari nilai simpulnya.

Contoh:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[1,2,3]`

Tindak lanjut: Solusi rekursif itu sepele, dapatkah Anda melakukannya secara berulang?

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().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

//iteratively solution 迭代解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
        if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int * result = (int *)malloc(sizeof(int) * (1000));
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
   
    struct TreeNode* p=root;
    *returnSize = 0;
    int stackIndex = 0;
   
    while (p || stackIndex > 1) {
    
        result[(*returnSize)++] = p->val;
        
        if (p->right) {
            stack[stackIndex++]=p->right;
        }
        
        p = p->left;
        
        if (stackIndex > 0&&!p) {
             p = stack[--stackIndex];
        }
    }
    
    
    return result;
}

//recursive solution 递归解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        * returnSize = 0;
        return NULL;
    }
    
    //左节点
    int leftSize =  0;
    int *left = NULL;
    if(root->left){
       left =  preorderTraversal(root->left, &leftSize);
    }
    
    //右节点
    int rightSize =  0;
    int *right = NULL;
    if(root->right){
       right =  preorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize + 1;
    int * result = (int *)malloc(sizeof(int) * (*returnSize));
    
    
    int index = 0;
    
    //根节点
    result[index++] = root->val;
    
    //左节点
    for (int i =0; i<leftSize; i++) {
        result[index++] = left[i];
    }
    free(left);
    
    //右节点
    for (int i =0; i<rightSize; i++) {
        result[index++] = right[i];
    }
    free(right);
    
    return result;
}

145. Traversal Postorder Pohon Biner

Kesulitan: Sulit

Diberikan pohon biner, kembalikan traversal postorder dari nilai simpulnya.

Contoh:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[3,2,1]`

Tindak lanjut: Solusi rekursif itu sepele, dapatkah Anda melakukannya secara berulang?

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().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

////迭代实现 iteratively solution
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int *)malloc(sizeof(int) * 1000);
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    
    * returnSize  = 0;
    int stackIndex = 0;
    int *flag = (int *)malloc(sizeof(int) * 1000);//用来标记是否是第二次访问这个节点
    
    struct TreeNode* p = root;

    while (p || stackIndex > 1) {
        if (p) {
            int dex = stackIndex++;
            stack[dex] = p;
            flag[dex] = 1;
            
        }
        
        if (p->right) {
            int dex = stackIndex++;
            stack[dex] = p->right;
            flag[dex] = 0;
        }
        
        p = p->left;
        if (!p && stackIndex > 0) {
            int loop =1;
            while (loop && stackIndex>0) {
                int index = --stackIndex;
                p = stack[index];
                if (flag[index] == 1) {
                    result[(*returnSize)++] = p->val;
                    loop = 1;
                }
                else{
                    loop =0;
                }
            }
            if (stackIndex==0) {
                return result ;
            }
        }
    }
    return result;
}

//递归实现 Recursive solution
int* postorderTraversal_1(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int *left = NULL;
    int leftSize = 0;
    if (root->left) {
        left = postorderTraversal(root->left, &leftSize);
    }
    
    int *right = NULL;
    int rightSize = 0;
    if (root->right) {
        right = postorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize  + 1;
    int *result =  (int *)malloc(sizeof(int) * (*returnSize));
    int index = 0;
   
    for (int i = 0; i < leftSize; i++) {
        result[index++] = left[i];
    }
    
    for (int i = 0; i < rightSize; i++) {
        result[index++] = right[i];
    }
    
    result[index] = root->val;
    
    free(left);
    free(right);
    
    
    return result;
}

Ulasan

Tinjau sebagai artikel saja: https://dandan2009.github.io/2018/11/17/accelerating-your-coding-skills/

TIPS

Minggu ini, mari kita memilah konsep yang berkaitan dengan pohon biner.

Beberapa konsep terkait pohon biner:

Pohon biner adalah struktur pohon yang setiap simpulnya mempunyai paling banyak dua cabang (artinya, tidak ada simpul yang derajat cabangnya lebih besar dari 2). Biasanya cabang disebut “subpohon kiri” atau “subpohon kanan”. Cabang-cabang pohon biner memiliki urutan kiri dan kanan dan tidak dapat dibalik sesuka hati. Level ke-i dari pohon biner memiliki paling banyak 2^i-1 node

berbeda dengan pohon biasa Jumlah node pada pohon biasa minimal 1, sedangkan jumlah node pada pohon biner dapat berjumlah 0; Tidak ada batasan derajat percabangan maksimum dari simpul pohon normal, sedangkan derajat percabangan maksimum dari simpul pohon biner adalah 2; Simpul pada pohon biasa tidak mempunyai urutan kiri atau kanan, sedangkan simpul pada pohon biner mempunyai urutan kiri atau kanan.

Pohon biner biasanya digunakan sebagai struktur data. Penggunaan umumnya adalah untuk mendefinisikan fungsi pelabelan untuk node dan mengaitkan beberapa nilai dengan setiap node. Pohon biner yang ditandai dengan cara ini dapat mengimplementasikan pohon pencarian biner dan tumpukan biner dan digunakan untuk pencarian dan pengurutan yang efisien.

Pohon biner bukanlah kasus pohon khusus Meskipun terdapat banyak kesamaan antara konsep pohon dan pohon biner, keduanya merupakan dua struktur data yang berbeda. Karena dari definisi: Pohon biner bukanlah pohon yang hanya memiliki dua subpohon atau pohon yang memiliki paling banyak dua subpohon. Perbedaan utama antara pohon dan pohon biner adalah bahwa subpohon dari suatu simpul dalam pohon biner harus membedakan antara subpohon kiri dan subpohon kanan. Sekalipun node hanya mempunyai satu subpohon, harus dinyatakan dengan jelas apakah subpohon tersebut merupakan subpohon kiri atau subpohon kanan. Sedangkan untuk sebuah pohon, tidak peduli berapa banyak subpohon yang dimilikinya, status setiap subpohon tetap sama, tidak seperti pohon biner yang membedakan kiri dan kanan.

Pohon biner adalah pohon terurut khusus: setiap simpul memiliki paling banyak dua cabang (simpul anak), dan cabang-cabang tersebut memiliki urutan kiri dan kanan serta tidak dapat dibalik. Dua pohon biner khusus: Pohon Biner Lengkap: Kecuali untuk lapisan terakhir, jika semua lapisan lainnya sudah penuh, dan lapisan terakhir sudah penuh, atau ada beberapa node berturut-turut yang hilang di sebelah kanan (perhatikan bahwa itu ada di sebelah kanan, bukan di sebelah kiri). Pohon Biner Penuh: Setiap level penuh (kecuali level terakhir, di mana level terakhir mengacu pada simpul daun).

Pohon biner dapat disimpan menggunakan daftar array atau tertaut. Jika pohon biner sudah penuh, maka dapat disusun secara kompak tanpa membuang ruang. Jika indeks suatu simpul adalah i, (dengan asumsi indeks simpul akar adalah 0) maka indeks simpul anak kirinya adalah 2i+1, dan indeks simpul anak kanannya adalah 2i+2; dan node induknya (jika ada) akan memiliki indeks $\frac{i-1}{2}$. Pendekatan ini lebih kondusif untuk penyimpanan kompak dan lokalitas akses yang lebih baik, terutama dalam preorder traversal. Namun memerlukan ruang penyimpanan yang terus menerus, sehingga banyak ruang yang terbuang saat menyimpan pohon umum yang terdiri dari n node dengan tinggi h. Dalam kasus terburuk, jika setiap node dari pohon biner dengan kedalaman h hanya memiliki anak yang tepat, struktur penyimpanan perlu menempati 2^h - 1 ruang. Faktanya, terdapat h node, yang membuang banyak ruang dan merupakan kelemahan utama dari struktur penyimpanan sekuensial.

Pohon biner lengkap disimpan dalam array

Traversal Kedalaman Pertama Dalam prioritas mendalam, kami ingin mengakses node terjauh dari node root. Berbeda dengan pencarian depth-first pada grafik, tidak perlu mengingat setiap node yang dikunjungi, karena tidak akan ada siklus di pohon. Pre-order, In-order dan Pasca-order traversal merupakan kasus khusus Depth-first traversal. Lihat penelusuran yang mengutamakan kedalaman.

Penjelajahan dengan luas lebih dulu Tidak seperti traversal depth-first, traversal breadth-first mengunjungi node yang paling dekat dengan node root terlebih dahulu. Lihat pencarian luasnya-pertama. Penjelajahan luas pertama pohon biner juga disebut penjelajahan tingkat demi tingkat. Algoritma ini diimplementasikan dengan bantuan antrian.

Pohon biner Definisi: Pohon biner t adalah himpunan elemen hingga (bisa kosong). Jika pohon biner tidak kosong, terdapat elemen yang disebut akar, dan elemen lainnya (jika ada) terdiri dari dua pohon biner, masing-masing disebut subpohon kiri dan subpohon kanan dari t.

Perbedaan mendasar antara pohon biner dan pohon adalah:

Pohon biner bisa saja kosong, namun pohon tidak bisa kosong. Setiap elemen dalam pohon biner mempunyai tepat dua subpohon (salah satu atau keduanya boleh kosong). Setiap elemen dalam pohon dapat memiliki beberapa subpohon. Dalam pohon biner, subpohon dari setiap elemen diurutkan, sehingga dapat dibedakan berdasarkan subpohon kiri dan kanan. Subpohon dari pohon tersebut tidak berurutan. Gambar di bawah menunjukkan pohon biner yang mewakili ekspresi matematika. Ada total 3 ekspresi matematika. Setiap operator dapat memiliki satu atau dua operan, operan kiri adalah subpohon kiri dari operator, dan operan kanan adalah subpohon kanan. Node daun di pohon adalah konstanta atau variabel.

Karakteristik pohon biner Ciri-ciri 1: Banyaknya tepi pohon biner yang mengandung n (n>0) elemen adalah n-1.

Buktikan bahwa setiap elemen dalam pohon biner (kecuali simpul akar) mempunyai tepat satu simpul induk. Hanya terdapat satu sisi antara node anak dan node induk, sehingga jumlah sisinya adalah n-1.

Ketinggian atau kedalaman pohon biner mengacu pada jumlah level pohon biner.

Ciri 2: Jika tinggi pohon biner adalah h, h≥0, maka pohon biner tersebut mempunyai paling sedikit h elemen dan paling banyak 2h−1 elemen.

Bukti: Karena setiap level harus memiliki minimal 1 elemen, maka jumlah elemennya minimal h. Setiap elemen mempunyai paling banyak 2 simpul anak, sehingga elemen simpul lapisan ke-i paling banyak 2i-1, i>0. Jika h=0, jumlah seluruh elemennya adalah 0, yaitu 20−1. Jika h>0, jumlah total elemen tidak akan melebihi ∑hi=12i−1=2h−1.

Karakteristik 3: Tinggi maksimum pohon biner yang memuat n elemen adalah n, dan tinggi minimumnya adalah ⌈log2(n+1)⌉.

Bukti Karena setidaknya ada satu elemen di setiap level, tingginya tidak boleh melebihi n. Dari sifat 2, kita dapat mengetahui bahwa pohon biner dengan tinggi h mempunyai paling banyak 2h−1 elemen. Karena n≤2h−1, maka h≥log2(n+1). Karena h bilangan bulat, h≥⌈log2(n+1)⌉.

Jika pohon biner dengan tinggi h mempunyai tepat 2h−1 elemen, maka disebut pohon biner penuh. Gambar di bawah adalah pohon biner penuh dengan tinggi 4.

Asumsikan bahwa elemen-elemen dalam pohon biner penuh dengan tinggi h diberi nomor dari 1 hingga 2h−1 secara berurutan dari atas ke bawah dan dari kiri ke kanan, seperti yang ditunjukkan pada gambar di atas. Asumsikan k elemen dihapus dari pohon biner penuh, dan jumlahnya adalah 2h−i, 1≤i≤k. Pohon biner yang dihasilkan disebut pohon biner lengkap. Tiga pohon biner lengkap ditunjukkan pada gambar di bawah. Perhatikan bahwa pohon biner penuh adalah kasus khusus dari pohon biner lengkap, dan kedalaman pohon biner lengkap dengan n elemen adalah ⌈log2(n+1)⌉.

Dalam pohon biner lengkap, suatu elemen mempunyai korespondensi yang sangat baik dengan jumlah anaknya. Hubungannya diberikan pada Properti 4 di bawah.

Ciri 4: Misalkan bilangan urut suatu elemen dalam pohon biner lengkap adalah i, 1≤i≤n. Kemudian terjalin hubungan berikut:

1. Jika i=1, elemennya adalah akar pohon biner. Jika i>1, banyaknya simpul induk elemen tersebut adalah ⌊i/2⌋.
2. Jika 2i>n, elemen tersebut tidak memiliki subpohon kiri, sebaliknya jumlah subpohon kirinya adalah 2i.
3. Jika 2i+1>n, maka elemen tersebut tidak mempunyai subpohon kanan, jika tidak, banyaknya subpohon kanannya adalah 2i+1.

Pohon biner

1. Bentuk dasar pohon biner:

Pohon biner juga didefinisikan secara rekursif, dan simpulnya dibagi menjadi subpohon kiri dan kanan. Logikanya, pohon biner memiliki lima bentuk dasar:

(1) Pohon biner kosong (2) Pohon biner dengan hanya satu simpul akar (3) Hanya subpohon kanan (4) Hanya subpohon kiri (5) Pohon biner lengkap

Catatan: Meskipun pohon biner mempunyai banyak kesamaan dengan pohon, pohon biner bukanlah kasus pohon yang khusus.

2. Dua konsep penting:(1) Pohon biner lengkap - pohon biner di mana hanya derajat simpul dari dua tingkat terbawah yang kurang dari 2, dan simpul-simpul di tingkat bawah terkonsentrasi di beberapa posisi di sisi paling kiri dari tingkat tersebut; (2) Pohon biner penuh - pohon biner yang setiap simpul kecuali simpul daun memiliki kotiledon kiri dan kanan, dan simpul daun semuanya berada di bawah.

3. Sifat-sifat pohon biner (1) Dalam pohon biner, jumlah total node pada level i tidak melebihi 2^(i-1); (2) Pohon biner dengan kedalaman h memiliki paling banyak 2^h-1 node (h>=1) dan setidaknya h node; (3) Untuk setiap pohon biner, jika jumlah simpul daun adalah N0 dan jumlah simpul berderajat 2 adalah N2, Maka N0=N2+1; (4) Kedalaman pohon biner lengkap dengan n node adalah int(log2n)+1 (5) Jika node dari pohon biner lengkap dengan N node disimpan secara berurutan, node tersebut memiliki hubungan sebagai berikut: Jika I adalah nomor simpulnya, maka jika I<>1, maka nomor simpul induknya adalah I/2; Jika 2I<=N, maka jumlah anak kirinya (yaitu simpul akar dari subpohon kiri) adalah 2I; jika 2I>N, tidak ada anak kiri; Jika 2I+1<=N, maka nomor simpul anak kanannya adalah 2I+1; jika 2I+1>N, tidak ada anak yang tepat. (6) Diketahui N node, h(N) pohon biner yang berbeda dapat dibentuk. h(N) adalah suku ke-N dari bilangan Cattelan. h(n)=C(n,2*n)/(n+1).

pohon biner penuh Pohon biner dengan kedalaman k dan 2 pangkat (k) - 1 node. Fitur: Jumlah node pada setiap level adalah jumlah maksimum node.

Definisi pohon biner lengkap: Pohon biner dengan kedalaman k dan n simpul disebut pohon biner lengkap jika dan hanya jika masing-masing simpulnya bersesuaian dengan simpul bernomor dari 1 sampai n dalam pohon biner penuh dengan kedalaman k. Fitur: Node daun hanya dapat muncul di dua level terbesar; untuk setiap node, jika tingkat maksimum keturunannya di bawah cabang kanan adalah l, maka tingkat maksimum keturunannya di bawah cabang kiri haruslah l atau l+1. Pohon biner penuh: pohon biner dengan kedalaman k dan 2 pangkat 1 - 1 node. Fitur: Jumlah node pada setiap lapisan adalah jumlah maksimum node. Pohon biner penuh jelas merupakan pohon biner lengkap. Pohon biner lengkap belum tentu merupakan pohon biner penuh.

Namun pohon pencarian biner mempunyai masalah yang sangat menyusahkan. Jika data acak dimasukkan ke dalam pohon, efek eksekusinya sangat baik, tetapi jika data diurutkan atau diurutkan terbalik, kecepatan eksekusi pohon pencarian biner menjadi sangat lambat. Karena ketika nilai yang disisipkan diurutkan, pohon biner menjadi tidak seimbang, dan kemampuannya untuk menemukan, menyisipkan, dan menghapus item data tertentu dengan cepat hilang.

Untuk mengatasi masalah ini, kita bisa menggunakan multi-pohon.

Pohon 2-3-4 adalah pohon multi, dengan setiap node memiliki hingga empat node anak dan tiga item data. Pohon 2-3-4, seperti pohon merah-hitam, juga merupakan pohon yang seimbang. Efisiensinya sedikit lebih buruk daripada pohon merah-hitam, tetapi lebih mudah diprogram. Arti 2, 3, dan 4 pada nama pohon 2-3-4 mengacu pada jumlah node anak yang mungkin terdapat dalam sebuah node. Ada tiga kemungkinan situasi untuk node non-daun:

Sebuah node dengan item data selalu memiliki dua node anak; Sebuah node dengan dua item data selalu memiliki tiga node anak; Sebuah node dengan tiga item data selalu memiliki empat titik byte.

Pohon pencarian biner, pohon 2-3-4, pohon merah-hitam

Pohon biner

Referensi; https://zh.wikipedia.org/wiki/二叉树 https://www.cnblogs.com/myjavascript/articles/4092746.html

Bagikan

Bagaimana cara mempelajari struktur data dan algoritma? Saya pernah membagikan ini sebelumnya, dan baru-baru ini saya melihat artikel yang sangat sesuai dengan pemikiran saya. Berikut ringkasannya:

Dasar-dasar yang Anda perlukan sebelum menjawab pertanyaan

1. Struktur data umum: daftar tertaut, pohon (seperti pohon biner).
2. Ide algoritma umum: metode serakah, metode membagi dan menaklukkan, metode lengkap, pemrograman dinamis, metode backtracking.
3. Algoritma pengurutan umum

Jika Anda bahkan tidak mengetahui hal-hal paling mendasar ini, Anda akan kesulitan menyelesaikan pertanyaan dan hanya memiliki sedikit ide. Bisa dikatakan untuk banyak soal hanya akan menggunakan metode brute force, jadi Anda tetap harus mahir dalam hal-hal dasar tersebut sebelum menyelesaikan soal.

Anda juga harus membaca buku dan belajar secara sistematis.

Yang terakhir harus lebih banyak dipraktekkan. Selama proses latihan, Anda harus mempelajari solusi terbaik orang lain. Jangan lakukan itu sendiri dan semuanya akan baik-baik saja. Anda harus melihat penerapan orang lain dan menganalisisnya sendiri dengan cermat.

Selain leetcode, ada juga nuke.com dan website berikut untuk menulis pertanyaan. 18 Situs Web untuk Melatih Keterampilan Pemrograman Anda https://blog.csdn.net/lyn167/article/details/52134859 [pembuat top] https://www.topcoder.com/ HackerEarth http://www.hackerearth.com/ Koderbyte https://coderbyte.com/ Proyek Euler: https://projecteuler.net/

Referensi: Bagaimana saya mempelajari struktur data dan algoritma? :https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ Konten WeChat sering hilang, berikut salinannya: Tautan asli: https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ

Status struktur data dan algoritma sudah jelas bagi seorang programmer. Artikel hari ini bukan untuk menyarankan Anda mempelajari struktur data dan algoritme, juga bukan untuk memberi tahu Anda betapa pentingnya struktur data dan algoritme.

Terutama karena dalam beberapa hari terakhir, pembaca bertanya kepada saya bagaimana saya mempelajari struktur data dan algoritma, apakah ada jalan pintas, apakah menonton video atau membaca buku, di mana mempelajari soal, dll… Dan beberapa dari mereka adalah junior dan senior, jadi saya cemas dan khawatir untuk Anda…

Jadi hari ini saya akan membagikan bagaimana biasanya saya belajar.

Jalan pintas untuk mempelajari algoritma adalah menjawab lebih banyak pertanyaan Sejujurnya, dalam hal jalan pintas, menurut saya yang terpenting adalah bersikap rendah hati dan melatih lebih banyak soal, serta menjawab lebih banyak pertanyaan.

Namun, jika Anda seorang pemula, artinya, Anda bahkan belum mempelajari struktur data umum, seperti daftar tertaut, pohon, dan ide algoritma umum, seperti rekursi, enumerasi, dan pemrograman dinamis, maka saya tidak menyarankan Anda untuk mempelajari pertanyaan-pertanyaan tersebut. Sebaliknya, carilah buku untuk mempelajarinya terlebih dahulu, lalu jawab pertanyaannya.

Dengan kata lain, jika Anda ingin membuka website seperti leetcode untuk menjawab pertanyaan, Anda harus memiliki landasan tertentu terlebih dahulu. Yayasan tersebut antara lain:

1. Struktur data umum: daftar tertaut, pohon (seperti pohon biner).

2. Ide algoritma umum: metode serakah, metode membagi dan menaklukkan, metode lengkap, pemrograman dinamis, metode backtracking.

Yang tercantum di atas adalah yang paling mendasar. Artinya, sebelum Anda menjawab pertanyaan, Anda harus mengulanginya lagi dan kemudian menjawab pertanyaan tersebut. Jika Anda bahkan tidak mengetahui hal-hal paling mendasar ini, maka Anda akan kesulitan menjawab pertanyaan-pertanyaan dan ide-ide Anda relatif sedikit.

Singkatnya, jangan terburu-buru. Pelajari dasar-dasar ini terlebih dahulu dan cobalah memahaminya sebelum menjawab pertanyaan. Saya mempelajari struktur data dasar dan algoritma ini pada semester kedua tahun pertama saya. Saya tidak menonton videonya. Saya mempelajarinya dengan membaca buku. Buku-buku yang saya baca saat itu adalah:

1. Analisis Algoritma dan Dasar-Dasar Analisis: Buku ini relatif sederhana dan direkomendasikan untuk pemula.

2. Struktur data dan analisis algoritma—Deskripsi bahasa C: Kode ditulis dalam C. Disarankan untuk membacanya.

3. Kompetisi Pemrograman Tantangan (Edisi Kedua): Ini juga buku yang sangat bagus, direkomendasikan.

Untuk lebih jelasnya, Anda dapat membaca artikel saya yang lain, yang memperkenalkan buku-buku ini: Buku algoritma dan struktur data dan manfaat video

Sejujurnya, saya menghabiskan hampir seluruh waktu saya di semester itu pada struktur data dan algoritma, tetapi pertanyaannya sangat sedikit, hanya beberapa contoh dari buku. Jadi setelah saya mempelajari dasar-dasar ini, masih sangat sulit untuk membuka beberapa situs web untuk menjawab pertanyaan.

Jadi jangan berharap untuk berpikir bahwa Anda akan pandai menjawab pertanyaan setelah mempelajari ide-ide ini. Hanya dengan menjawab lebih banyak pertanyaan dan berlatih lebih banyak, kepekaan Anda dapat ditingkatkan.

Izinkan saya berbicara tentang kolom yang sangat populer beberapa waktu lalu - [Keindahan Struktur Data dan Algoritma]

Saya tidak membeli kolom ini. Yang ingin saya sampaikan adalah, jika membelinya wajib dibaca dan jangan disia-siakan. Jangan berpikir bahwa Anda akan menjadi lebih hebat setelah mempelajari kolom ini. Jika Anda hanya mengikuti perkembangan pembelajaran kolom ini, Anda tidak akan menghabiskan waktu untuk menjawab pertanyaan dan melakukan praktik langsung. Maka saya jamin Anda akan tetap pandai setelah selesai belajar.

Untuk meringkas:

Tidak ada jalan pintas untuk meningkatkan struktur data dan algoritma. Jalan pintas terbaik adalah menjawab lebih banyak pertanyaan. Namun, prasyarat untuk menyelesaikan pertanyaan ini adalah Anda harus terlebih dahulu mempelajari beberapa struktur data dasar dan ide algoritma.

mengejar kesempurnaan Bagaimana menjawab pertanyaan? Bagaimana cara mengatasi masalah algoritma?

Menurut saya, saat mengerjakan soal, Anda harus mengejar kesempurnaan. Jangan pernah menyelesaikan sebuah pertanyaan, kirimkan dan sampaikan, lalu buru-buru ke pertanyaan berikutnya.

Terdapat hubungan tertentu antara peningkatan kemampuan algoritmik dan jumlah pertanyaan, namun hubungan tersebut tidak linier. Dengan kata lain, ketika memecahkan suatu masalah, Anda harus berusaha untuk memecahkan banyak masalah. Jika Anda benar-benar tidak dapat memikirkan cara lain, Anda dapat pergi dan melihat bagaimana orang lain melakukannya. Jangan merasa memalukan jika meniru apa yang dilakukan orang lain.

Ketika saya sedang mengerjakan sebuah soal, ketika saya melihat sebuah soal, pikiran pertama saya mungkin adalah menyelesaikannya dengan cara yang sangat kasar, karena banyak soal yang mudah diselesaikan dengan menggunakan metode brute force, tetapi kompleksitas waktunya sangat tinggi. Setelah itu, saya akan memikirkannya secara perlahan dan melihat apakah ada cara lain untuk mengurangi kompleksitas waktu atau kompleksitas ruang. Terakhir, saya akan melihat apa yang telah dilakukan orang lain. Tentu saja, tidak semua pertanyaan akan dieksekusi dengan cara ini.

Mengukur kualitas suatu masalah algoritma tidak lebih dari kompleksitas waktu dan kompleksitas ruang. Oleh karena itu, jika kita ingin mengupayakan kesempurnaan, kita harus meminimalkan keduanya dan menjadikan keduanya saling melengkapi.

Izinkan saya memberi Anda sebuah contoh:

Pertanyaan: Seekor katak dapat melompat 1 langkah atau 2 langkah sekaligus. Berapa banyak cara katak dapat melompati tangga tingkat n?

Saya telah menganalisis pertanyaan ini di bab-bab sebelumnya. Jika belum paham, Anda bisa membaca apa yang saya tulis sebelumnya: Rekursi dan Pemrograman Dinamis — Dasar Bab 1

Metode 1:: Rekursi dengan kekerasan

Pertanyaan ini tidak sulit. Mungkin Anda akan mengambil pendekatan berikut:

penyelesaian int statis publik(int n){ jika(n == 1 || n == 2){ kembali n; }lainnya jika(n <= 0){ kembali 0; }lainnya{ kembali memecahkan(n-1) + memecahkan(n-2); } }

Kompleksitas waktu dari pendekatan ini sangat tinggi, eksponensial. Namun jika Anda beruntung lulus setelah mengirimkan, dan kemudian Anda melanjutkan ke pertanyaan berikutnya, maka Anda perlu memikirkannya dengan matang.

Metode 2: Tukarkan ruang dengan waktu

Untuk mengupayakan kesempurnaan, kita dapat mempertimbangkan untuk menukar ruang dengan waktu: Jika Anda memikirkan pertanyaan ini dengan cermat, Anda akan menemukan bahwa banyak pertanyaan yang berulang. Jadi, Anda dapat mengambil pendekatan berikut:

//Gunakan HashMap untuk menyimpan status terhitung peta statis<Bilangan Bulat,Bilangan Bulat> peta = HashMap baru(); penyelesaian int statis publik(int n){ jika(n <= 0)mengembalikan 0; lain jika(n <= 2){ kembali n; }else{//Apakah sudah dihitung if(peta.berisiKey(n)){ kembali peta.dapatkan(n); }lainnya{ int m = selesaikan(n-1) + selesaikan(n-2); peta.put(n, m); kembalikan m; } } }

Dengan cara ini, waktunya bisa dipersingkat. Dengan kata lain, setelah Anda memecahkan masalah dan menemukan bahwa kompleksitas waktu sangat tinggi, Anda dapat mempertimbangkan apakah ada metode yang lebih baik dan apakah Anda dapat menukar ruang dengan waktu.

Metode 3: Deret Fibonacci

Faktanya, kita dapat membuat kompleksitas ruang menjadi lebih kecil dan tidak memerlukan HashMap untuk menyimpan status:

penyelesaian int statis publik(int n){ jika(n <= 0) kembali 0; jika(n <= 2){ kembali n; }int f1 = 0; int f2 = 1; int jumlah = 0; untuk(int saya = 1; saya<= n; saya++){ jumlah = f1 + f2; f1 = f2; f2 = jumlah; } jumlah pengembalian; }

Saya menunjukkan kepada Anda pertanyaan ini bukan untuk mengajari Anda cara melakukannya, tetapi untuk tujuan berikut:

1. Saat menjawab pertanyaan, kita harus mengupayakan kesempurnaan.

2. Saya tidak dapat memikirkan metode ini, apa yang harus saya lakukan? Kemudian Anda dapat melihat apa yang telah dilakukan orang lain. Nantinya, ketika Anda menghadapi masalah serupa, Anda akan memiliki lebih banyak ide dan tahu arah berpikir yang mana.

3. Anda bisa memulai dengan kekerasan sederhana untuk menyelesaikan suatu masalah, dan mengoptimalkannya sedikit demi sedikit dengan tetap mempertimbangkan ukuran antara ruang dan waktu.

Rekomendasikan beberapa situs web penyikat pertanyaan Saya biasanya mempelajari pertanyaan di Leetcode dan Niuke.com, dan rasanya cukup bagus. Pertanyaan-pertanyaannya tidak terlalu sulit.

Di Niuke.com, saya terutama mempelajari Penawaran Jianzhi, tetapi ada juga program online bernama Leetcode, tetapi jumlah pertanyaan di dalamnya relatif sedikit. Tempat yang sangat nyaman untuk menjawab pertanyaan di Niuke.com adalah area diskusi. Akan ada banyak orang besar yang berbagi metode pemecahan masalah mereka, jadi kita tidak perlu pergi ke Baidu untuk mencari solusinya. Jadi setelah Anda menyelesaikannya dan Anda benar-benar tidak dapat memikirkan hal lain, Anda dapat dengan mudah pergi dan melihat bagaimana orang lain melakukannya.

Sedangkan untuk leetcode, sebagian besar pertanyaan memiliki jawaban resmi, dan ini juga merupakan situs web yang bagus untuk mempelajari kembali pertanyaan. Anda dapat memilih salah satu dari keduanya, atau melakukan keduanya.

Tentu saja, ada situs web lain yang mengabaikan pertanyaan tersebut, tetapi karena saya belum memeriksa situs web lain, saya tidak tahu cara menghapusnya.

Mari kita bicara tentang struktur data Sebelumnya saya terutama berbicara tentang bagaimana saya biasanya mempelajari algoritma. Dalam hal metode struktur data, saya baru saja menyebutkan bahwa Anda harus mempelajari daftar tertaut dan pohon (tumpukan biner), tetapi ini adalah yang paling dasar dan harus dikuasai sebelum menjawab pertanyaan. Untuk struktur data, saya akan mencantumkan beberapa yang lebih penting:

1. Daftar tertaut (seperti daftar tertaut satu arah, daftar tertaut dua arah).

2. Pohon (seperti pohon biner, pohon seimbang, pohon merah hitam).

3. Grafik (seperti beberapa algoritma untuk jalur terpendek).

4. Antrian, tumpukan, matriks.

Untuk ini, Anda harus menerapkannya sendiri. Anda dapat membaca buku atau menonton video. Pemula dapat menonton video terlebih dahulu, tetapi Anda dapat menonton video pada tahap awal. Setelah itu, saya sarankan Anda harus membaca buku.

Saya telah merekomendasikan video dan buku sebelumnya: Buku algoritma dan struktur data dan manfaat video

Misalnya, untuk pohon seimbang, Anda mungkin melupakannya setelah beberapa saat setelah mengikuti kode di buku, tapi itu tidak masalah. Walaupun anda lupa, namun jika anda sudah mengimplementasikannya dengan kode sebelumnya dan memahaminya, maka ketika anda melihatnya kembali, anda akan cepat mengingatnya dan memahami idenya dengan cepat, dan tanpa disadari kemampuan abstraksi anda akan meningkat. Nanti, jika Anda mempelajari pohon merah-hitam dan struktur data lainnya, Anda akan mempelajarinya dengan sangat cepat.

Yang paling penting Lakukan, lakukan, lakukan. Ucapkan hal-hal penting tiga kali.

Jangan mencari banyak sumber daya, buatlah rencana belajar, dan biarkan sampai hari tertentu untuk melakukannya…

Jangan lakukan ini, tapi ketika passion Anda datang, segera lakukan. Jangan biarkan sampai hari libur atau apa pun. Banyak orang yang berpikiran seperti ini pada akhirnya tidak berbuat apa-apa.

Jangan merasa begitu banyak yang harus dipelajari dan Anda tidak tahu harus mulai dari mana. Seperti yang saya katakan di atas, Anda dapat mempelajari yang paling dasar terlebih dahulu, baru kemudian mempelajari soal-soalnya. Mempelajari soal-soal merupakan suatu hal yang membutuhkan ketekunan jangka panjang, satu atau dua tahun. Dalam proses penyelesaian pertanyaan, Anda dapat menyelingi pembelajaran struktur data lainnya.