調和的靈感

解題策略 典型的Binary Tree的題目，牽涉到兩個跟Binary Tree相關的動作 我們知道只要有 inorder + postorder 就可得唯一的一棵 binary tree。那該怎麼把樹建起來呢 ? 我寫在 build_tree()裡。 樹建起來之後，該怎麼走這顆樹，才能找出最小路徑呢? 這我寫在 do_summing( ) 函數，遞迴往下累加總和，再回傳最小的樹葉回來。 Tree 天生就是遞迴結構，用遞迴來寫再自然不過了。 注意 Tree原本應該是NULL的地方，我都掛了外部點(External Node)，這樣會讓程式碼清爽一些。

解題策略 相當有趣的題目，要旋轉字串90度再印出。注意字串不足的部份要自行補白。 提供一個測資： aaa aaa bbb bbb cccccc dddd ee f f g g h h

解題策略 這題要找出字串中的最小週期，我的作法比較好玩一些。 首先用兩個指針i,j分別指向字串的頭兩個字母，像這樣： abcdabcd ↑↑ 我的基本想法很簡單，讓i,j之間保持一個固定間距，如果這個間距就是週期，那麼且同步往後移動指針，比對字母，i,j指的兩字母應該要一直都相同。 # 例子:不管何時，兩指針的字母皆同。 abcabcabc ↑ ↑ abcabcabc ↑ ↑ abcabcabc ↑ ↑ 那麼我們的任務就是找出i, j 的間距啦。初始從週期值1開始比對兩字，不同表示尚未找到週期，拉開指針的間距一格 (++j) 。直到兩字相同 buf[i]==buf[j]，這時候可能就是字串中的週期出現了，同步移動指針 (++i,++j) 持續往後比對。 這個作法有兩個Special case要考慮 字串只有一個字母的時候(長度為1)，兩根指針還能指去哪，直接return 1。 有時候字串尾巴會出現一些破壞週期的字母，例如：abcabcabc d ，或者hoha ho 。所以最後必須檢查找到的週期，跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了，週期值直接等於字串長度。

解題策略 慶祝新書入手，解了書中第一題噴題。盯著鍵盤建好Ascii對應表：如 map['W'] = 'Q'，注意空格跟換行不需要換字。

Dynamic Programming的基本題 LCS DJWS的LCS筆記 洪朝貴老師的動態規劃講義 這題我寫了兩種解法 LCS() 是一般的作法，最清楚直接。 LCS_save_memory() 是針對記憶體優化過的算法。 這題唯一要小心的點就是UVa的字串中包含空格。