發表文章

目前顯示的是 四月, 2010的文章

UVa 548 Tree

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

UVa 490 Rotating Sentences

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

UVa 455 Periodic Strings

解題策略 這題要找出字串中的最小週期,我的作法比較好玩一些。 首先用兩個指針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 。所以最後必須檢查找到的週期,跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了,週期值直接等於字串長度。

UVa 10082 WERTYU

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

UVa 10405 Longest Common Subsequence

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