程式小白的筆記

想法: 類似玩大老二在整理牌的時候 把所有牌分成已排序區和未排序區 初始假設第一張在已排序區 例如 在第一回合 把第二張拿來跟第一張比較 第二張如果小於第一張 => 第二張放在較小的位置 第二張如果大於第一張 => 第二張放在較大的位置 所以此時第一張和第二張的相對位置會是正確的 (第一二張位在已排序區，其他都是未排序區) 在第二回合 把第三張拿來跟已排序區的做比較 找到對的相對位置後插進去 所以此時這三張牌的相對位置會是正確的 以此類推 要注意一個地方 在插入的地方 要把插入的地方往後的地方(直到已排序區的尾巴)都往後移一格 記得 要先移動最後面的值 如果從最前面開始移動 會把值一直往後覆寫 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 insertionsort ( 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 ]); ...

想法: 類似於 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...

Linked List 優點: 1. 容易新增、插入、刪除內部的元素 2. list size很彈性 Linked List 缺點: 1. 無法 Random Access ( Array 可以透過指定 offset 直接存取) 2. 較 array 浪費記憶體空間 (多一個 entry 存指向下個位置的pointer) 適用時機: 1. 頻繁新增/插入/刪除元素 2. 無法預期會有多少元素 不適用時機: 2. 頻繁查詢內部元素 Ref: linked list

想法: 硬記解法 利用 快慢指針 的概念 快的一次移動兩個位置 慢的一次移動一個位置 照理來說快的跟慢的不會碰到 如果快慢指針有碰到就表示該 list 有循環 如果快的碰到終點就表示該 list 沒有循環 code: /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     struct ListNode *next;  * };  */ typedef struct ListNode Node ; bool hasCycle ( Node * head ) {     Node * slow = head ;     Node * fast = head ;     if ( head == NULL ){         return 0 ;     }     while ( fast -> next != NULL ){         fast = fast -> next -> next ;         if ( ! fast ){             return 0 ;         }         slow = slow -> next ;         if ( fast == slow ){             return 1 ;         }     }     return 0 ; } ref: 刷題筆...

想法: cur 就是一直往下尋訪 pos 用來記錄目前 cur 尋訪到的節點位置 (從0開始, 0, 1, 2, 3...) pos & 1 是用來判斷奇數偶數 (用 bit 來判斷) mid 則是在碰到"尋訪到第奇數個"時才會往下尋訪 Code: /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     struct ListNode *next;  * };  */ typedef struct ListNode Node; Node * middleNode (Node * head ){     Node * cur;     Node * mid;     cur = head;     mid = cur;     int pos = 0 ;     if (cur == NULL ){         return NULL ;     }     while (cur != NULL ){         if (pos & 1 ){             mid = mid -> next ;         }         pos ++ ;         cur = cur -> next ;     }     return mid;     }