Note to self

1. Bubble Sort 氣泡排序法（bubble sort）是排序演算法（sorting algorithm）中較簡易的一種。 其運作的原理是藉由逐次比較相鄰的兩筆資料，並依照排序條件（由大至小或由小至大）交換資料直到排序完成為止。 FOR( i=n to 0) do:        FOR (j = 0 to n-1 ) do:             if (A[j] > A[j+1])                 SWAP(A[j], A[j+1]) 2. Selection Sort FOR(i=0 to n) do:     FOR(j = i+1 to n) do:           if (A[i] > A[j]):               SWAP(A[i], A[j]) 每次產生最小的在序列的最左邊。 3. Merge Sort 4. Bucket Sort 5. Quick Sort

自己想到遞迴的解法，但效能不是說很好。 讓head->next = func(head->next)，如果下一個和當前一樣就return func(head->next)，

首先先用兩個指針來維護此Linked List，一個叫做pre、一個叫做cur。 而temp就是每次處理的對象，要將往前指，所以temp是cur->next。 cur做的是每一次的遍歷，遍歷目標在temp下一個。 temp下一個就是尾巴，尾巴就是pre->next。 pre做的是就是複雜尾巴的部分，每次結束把temp給他。而pre->next就是temp。 另外一個方法是：一開始用TempList儲存處理的對象(一開始尾巴是NULL)，遍歷head。 尾巴等於tail，TempList assign給tail。TempList 等於頭，頭等於頭->next。TempList下一個等於tail。一直循環直到head == NULL

2. 白板題給一個 8-bit size的值求最高位元是在第幾個bit 3. SET BIT(n) = 1, CLEAR BIT(n) = 0 寫function 把某個數的第x個bit改成1或0 (改成1直接用or、改成0用mask 之後and) 4. 判斷是否是2的次方 5. 判斷一整數是偶數還是奇數     return x & 1; //回傳1odd, 0 even; 6. 請擷取出Input中的第七個bit值?     return (x & 64(1000000)) >> 6;     return (x >> 6) & 1 7. 請擷取出Input中的第N個bit值?     int Get_N_bit(int x, int n){          return (x >> (n-1)) & 1     } 8. 計算有幾個位元是 1    for (; n !=0; n >>= 1) if (n&1 == 1) ++i int  count_bits2(unsigned  int  n) {        int  i= 0 ;        for  ( ; n !=  0 ; n >>=  1 )            if  (n &  1 )               ++i;        return  i;   } 

找出三的次方。 這邊有遞迴方法和迭代的方法。提示有說要不用迭代和遞迴解這題。 遞迴的方法如下： 迭代的方法如下：

找到二的次方，有很多方法，這邊我實作一個最常見的方法。 用n & n - 1，從二進制去看，如果是0就是二的次方。

這題很簡單，規則限定直接從root到leaf的總和。 直接用DFS遞迴解。 參考Path Sum III方法一樣，用一個pre去找。

看到這題，一開始的想法是level order travel，但是最後沒有做出來。 問題在於無法判斷同一條路上有2條以上的路徑。 後來發現有一個很猛的作法，用雙重遞迴。

首先我覺得這題有點難，level order, DFS, BFS要複習清楚！ 解題的思路：

強盜搶劫問題，首先依題目規定，一旦搶了i就不能搶i+1的房子了。 因此我們釐清一下，如何看到題目就知道要用DP去解呢？ DP又分為top-down和bottom-up， top-down顧名思義就是從大問題到小問題，bottom-up是從小問題到大問題，DP加入memorization的機制。 top-down通常是用遞迴觀念去看。bottom-up通常用陣列(or vector)去記憶初始的問題，再從小問題逐步和成大問題。 因此，題目可以這麼看。設i為index。rob[i]為最佳解。以ex. 2為例： rob[0] = 只有一間房子，故得最佳解，即2。 rob[1] = 從[2,7]當中挑出的最佳解，即7。 此時，要思考怎麼得出rob[2]呢？ rob[2] 先直接從肉眼看出[2,7,9] = 11，它等同於rob[2] = max(rob[2-1], 當前第i房子+ rob[2-2]) rob[i] = max(rob[i-1], 當前房子 + rob[i-2])

求樹的最大深度，解這種題目可以思考要用DFS還是BFS。 DFS多半用遞迴解，BFS多半用Queue去存取adjacent node。 DFS思維是從起點出發會一直往深度去尋訪，故，深度優先搜尋：  Start Node為1 我們默認左側的child node會先被搜索到，所以3->5 ->6 ->2 ->4 可以想像每一次找到子節點再遞迴下去孫節點，直到找到NULL。 沒找到一個子節點等同於深度加1，找到NULL就return 0。

首先觀察奇數與偶數的關係，上面範例為長度5的linked list，會取index 2。長度6的linked list會取index 3。所以即 ans = arr [n / 2] 求Linked list中間的數字，我的方法為：

題目是判斷input是否有回文。 我們首先要做的是把多餘的符號刪掉，這時候用c library的isalnum檢查是否為字母， 這個函數返回非零值，如果是一個數字或字母傳回1，否則為0。 因此我們的想法是two pointer，一個從前面來，一個從後面來，一一比較。

遞迴方法： 思考方式Top-down，大問題可以拆解小問題 頭指針的下一個是 1. 如果==val 則會return ->next->next 2. 否則 return ->next 缺點容易stack overflow;

瑞昱藍芽: 語言是C，大部分都是考Function的Return值 主管說他們最重視C code、OS、計算機組織 有通訊、硬體相關經歷加分 指標函式 bitwise sizeof extern oop cstyle string 一些常考問題 以及資料結構如li nk list tree演算法如graph 霍夫曼 等等 1. 考void pointer之casting和call by refer. unsigned int x = 0xa;  void* ptr= (void*)&x;  *(unsigned int*)ptr = 5;  Call by reference 就不寫了 

首先這題是要求出在一個字串vector裡面，每個字串共同最長前置(prefix)。 想法很簡單：把vector第一個字串拿來當作比較對象，我們稱之COMP好了。return的值稱為ans。 ans = ""; COMP=input[0]; 拿COMP[0]的字元與其他對象字串比較 如果有存在在其他字串當中，將他加入到ans 否則，return ans 重複1-3步驟直到遍歷完所有的COMP字元。 return ans;