程式小白的筆記

想法: 類似於 Bubble Sort 差別在於 Bubble Sort 是"尚未比較完畢的搜尋區內"每個節點鄰居做比較，條件成立就交換 Selection Sort 是"尚未比較完畢的搜尋區內"第一個節點與其後每個節點比較，條件成立就交換 因此每個回合會有一個點被定下來(可以是最大值也可以是最小值) Code: #include <stdio.h> #include <stdlib.h> #include <time.h> void swap ( int * a , int * b ); void printarray ( int size , int * data ); void generate_random_array ( int size , int * data ); void bubblesort ( int size , int * data ); void selectionsort ( int size , int * data ); void swap ( int * a , int * b ){     int tmp = * a ;     * a = * b ;     * b = tmp ; } void printarray ( int size , int * data ){     printf ( "data: " );     for ( int i = 0 ; i < size ; i ++ ){         printf ( " %d ," , data [ i ]);     }     printf ( " \n " ); } void generate_random_array ( int size , int * data ){     srand ( time ( NULL ));     for ( int i = 0 ; i < size ; i ++ ){...

想法: 所有尚未被定位的資料會形成一個 搜尋區 在搜尋區內，從最小的開始，一直跟鄰近的點比較，如果前面的點大於後面的點，則交換 所以在每個回合都會找到一個最大值 這個最大值就會被定下來並且不再加入比較(將最大值踢出搜尋區) 在下個回合一樣，在搜尋區內從最小的開始一直做比較 這個回合就會找到次大值(將次大值踢出搜尋區) 所以 bubble sorting 的概念就是在每個回合都會把最大值擠到最後面的 index 去 Code: #include <stdio.h> #include <stdlib.h> #include <time.h> void swap ( int * a , int * b ); void bubblesort ( int size , int * data ); void printarray ( int size , int * data ); void swap ( int * a , int * b ){     int tmp = * a ;     * a = * b ;     * b = tmp ; } void bubblesort ( int size , int * data ){     int i , j ;     for ( i = 0 ; i < size ; i ++ ){         for ( j = 0 ; j < size - i - 1 ; j ++ ){             if ( data [ j ] > data [ j + 1 ]){                 swap ( & data [ j ], & data [ j + 1 ]);             }     ...

想法: 這題的 general 公式很簡單 就是對於 [i][j] 的數值 (i 為 row number, j 為 column number) 計算方式是將 [i-1][j-1] 和 [i-1][j] 的數值相加 然後每個 row 的第一個和最後一個都會是 1 但這題卡住我最久的是 pointer 的問題 這時候就要複習到 function 中的 call by pointer returnSize 是一個 pointer，他指向一個 int 的空間 returnSize 的意思是回傳的二維 array 有幾個 array (也就是有幾個 row) 所以將 "returnSize 這個 pointer 所指向的空間的值" (*returnSize) 指定為 numRows 的值 returnColumnSizes 是一個 pointer，他指向一個 int pointer array 的空間 returnColumnSizes 的意思是每個 row 有幾個 column 所以將 "returnColumnSizes 這個 pointer 所指向的空間，並且加上 index，找到存放對應 row 的 column size 的空間" (*returnColumnSizes[i]) 指定為每個 column 的大小 pascal_array 是一個 pointer，他指向一個 int pointer array 的空間 (就是一個 2D array) 每次尋訪到新的 row 時，都要記得宣告新的空間 所以每次 loop 一開始 "pascal_array 這個 pointer 所指向的空間，並且加上 index，找到存放對應 row 的 data 的 array" (pascal_array[i]) 都要新宣告一個對應 column size 的空間存放這些 int Code: /**  * Return an array of arrays of size *returnSize.  * The sizes of the arrays are returned as *returnColumnSizes array.  * Note: Both returned array and *columnS...

想法: 設置兩個 pointer 分別為 node1 和 node2 node1 為由前面往後數 n 個 node2 為由後面往前數 n 個 1. 先定位好兩個 pointer 先定位好 node1，再來定位好 node2 2. 進行交換 原本想說要把兩個 pointer 交換，但要考慮到太多問題一直寫不出來，後來發現其實直接交換值就好了 * 如果 list 中只有一個節點，就算交換了也會是原本的樣子，所以直接回傳 Code: /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     struct ListNode *next;  * };  */ typedef struct ListNode Node ; Node * swapNodes ( Node * head , int k ){     if ( head -> next == NULL ){         return head ;     }         Node * cur , * node1 , * node2 ;     node1 = NULL ;     node2 = NULL ;     cur = head ;     int i = 0 ;     for ( i = 0 ; i < k - 1 ; i ++ ){         cur = cur -> next ;     }     node1 = cur ;     cur = head ;     for ( i = 0 ; i < k ; i ++ ){     ...

想法: 先將該 linked list 做 reverse  然後再從尾巴尋訪回來計算數字 (計算方式: 每個 binary 的 digit 要轉成 decimal 的方式為 * 2 的某次方 所以從最小的 digit 開始尋訪並每次遞增 count pow(a,b) 的結果為 a 的 b 次方 因此 pow(2,count) 會回傳 2 的 count 次方) Code: /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     struct ListNode *next;  * };  */ typedef struct ListNode Node ; int getDecimalValue ( Node * head ){     Node * cur ;     Node * pre ;     Node * tail ;     int count = 0 ;     int dec_value = 0 ;         cur = head ;     tail = cur -> next ;     cur -> next = NULL ;     pre = cur ;     cur = tail ;     while ( tail ){         tail = tail -> next ;         cur -> next = pre ;         pre = cur ;         cur = tail ;   ...

想法策略: 設置兩個 pointer 第一個 pointer 會先走 n+1 步 然後第一個和第二個 pointer 一起前進 所以兩個 pointer 會一直保持 n+1 的距離 直到先出發的 pointer 碰到 NULL 時 後出發的 pointer 所指到的就是要移除的 node 詳細解說: cur 指到 head，pos_remove 指到 NULL 1. 讓 cur 先走 n 個位置 2. 判斷 cur 是否為空      1. 如果 cur 不為空，則把 pos_remove 指定為 cur 的位置， cur 在往後走 1 個位置      (因此目前 pos_remove 和 cur 的距離是 n + 1 個位置)      2. 如果 cur 是空的，則 cur 和 pos_remove 都不動 3. 直到 cur 碰到尾巴為止， cur 跟 pos_remove 一起往前 4. 如果 pos_remove 為 NULL，就表示要移除的是 head，所以把 head 指定成 head 的下個節點後直接 return head 5. 此時 pos_remove 的下個節點就是要移除的，所以 pos_remove 的下個節點要指向下下個節點(跳過下個節點) code: /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     struct ListNode *next;  * };  */ typedef struct ListNode Node ; Node * removeNthFromEnd ( Node * head , int n ){     Node * cur = head ;     Node * pos_remove = NULL ;     //cur increment n steps at first     for ( int...