跳到主要內容

發表文章

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

UVa 548 Tree

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

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。有時候字串尾巴會出現一些破壞週期的字母,例如:abcabcabcd,或者hohaho。所以最後必須檢查找到的週期,跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了,週期值直接等於字串長度。

Ruby 快速筆記: Block and Iterator

BlockBlock是相當特別的東西,在某些語言裡block被稱做closure,
先看個例子,我需要連續打印"hello"五次,那麼這樣寫就行:
5.times { print "hello" } # hellohellohellohellohello Ruby是個純OO語言,所以數字5也有函數可以呼叫,times就是其中之一。
這個例子最常被拿來說嘴Ruby有多麼簡潔。

Block可以看作某種匿名的函數,或者是...一沱程式碼。
{ print "hello" } # 這就是一個block Block不能單獨存在,必須掛在function call後面,以供function使用,
例如它附掛在times這個函數後面,而5.times的功用就是連續執行這個block五次!
這程式可讀性實在高。(有什麼比5.times更接近五次?)

Iterator那這個Block有什麼實際的用途呢?
Ruby裡的Iterator就是用Block來達成。
例如
a = ["apple", "banana", "orange"] 這是一個字串Array,我們想要遍訪a的各個元素,該怎麼做呢?
a.each { |s| puts s+'is fruit' } # 執行結果 # apple is fruit # banana is fruit # orange is fruit a.each 這個方法會遍訪array的各個元素(此處就是水果的名稱),並且對每個元素就都調用一次Block。Block開頭處的 |變數| ,就代表當下的的陣列元素,例如上例的 |s|就是各個水果的名稱。這個例子我們將陣列內水果的名稱都打印出來。

以下還有很多例子
(1..100).each { |i| puts i } # 依序印出數字1~100 ('a'..'z').each { |c| puts c } # 依序印出26個英文字母 [1,2,3,4,5].map { |e| e*e } # [1,4,9,16,25] 陣列每個元素都取平方 open('aaa.txt').each do |line| # …

Ruby 快速筆記: 流程控制

流程控制都差不多,一般語言該有的都有
if-else 敘述if weight > 80 puts "You are too fat!" elsif weight > 60 puts "You are ok" else puts "You are too thin!" end While範例Echo程式,會重複你輸入的字句
while line = gets puts line end For Loop印出1~10的平方,形式相當簡潔
for i in 1..10 print i*i end # 1 4 9 16 25 ... 倒裝句比較特別的一點,就是從Perl借來的倒裝句法(後置條件)
可以創造出近似英文敘述的語句,相當漂亮。
puts "Good Job" if price<100 puts "Level Up!" if exp>10000 例如我們想把陣列內元素全部依序pop出來
array = [1,3,5] while not array.empty? puts array.pop end #上面那幾行意義完全等同這一句 puts array.pop while not array.empty? 事實上還有個 until loop,剛好判斷條件跟while相反
所以這樣寫效果也一樣
puts array.pop until array.empty?

Ruby 快速筆記: 一個簡單的函數

一個簡單的函數叫 say_hi ,很容易理解。
def say_hi ( name ) s = "Hello, "+ name return s end 也可以像php一樣把變數嵌到字串裡,用法是 #{變數} 。
但只有""雙引號夾住的字串才會解析,''單引號不會,這點也像php。
def say_hi ( name ) s = "Hello, #{name}" return s end Ruby會自動回傳最後出現的變數值,所以return也可以省略。
def say_hi ( name ) "Hello, #{name}" #這樣寫效果一樣 end 呼叫的效果
puts say_hi("David") # "Hello, David" puts say_hi "Mary" # "Hello, Mary" 括號也可以省略 省略括號的用法自己看狀況斟酌
如果參數很多,易搞混順序,還是加一下比較好。

Ruby 快速筆記: Hello Ruby

Hello Ruby不可免俗得來一下 Hello Ruby
puts "Hello Ruby!" # 螢幕印出 Hello Ruby! puts跟C/C++的用法一樣,輸出字串到螢幕上並附上一個換行\n。

Ruby有一個蠻有趣的特性,就是呼叫函數時若不會造成歧義,可省略括號。
puts("Hello Ruby") puts "Hello Ruby" # 這兩行意思一樣
這有什麼好處呢?除了少敲幾下鍵盤外,可以讓code看起來更簡單清爽
例如Ruby 的 setter
s = Song.new s.title="星晴" # 這行原本是 s.title=("星晴") s.singer="周滷蛋" # 看似直接存取成員變數,其實是透過setter函數 # 兼顧了物件的封裝性跟程式碼的可讀性
Ruby WayRuby允許函數使用少數幾個特殊符號作為的結尾。
而這些符號都有特殊的意義,例如上面提到的等號(=)通常就拿來作為setter
還有問號(?) 以問號結尾的函數會回傳True/False
2.zero? # falsev (是零嗎?) [].empty? # true (陣列是空的嗎?)
驚嘆號(!)代表危險,或者會改動原本的變數值
s = "DAVID" s.downcase # 回傳"david" ,但s依然是"DAVID"。 s.downcase! # s變成"david"
這種規則就叫做 Ruby way

Ruby 快速筆記: Everything is Object

Ruby裡所有的東西都是物件。
包括數字、陣列、字串都是物件。
所以會生出一些看似神奇的用法

# 數字是物件 -55.abs # 55 (取絕對值) 2.zero? # false (是零否?) 10.to_f # 10.0 (轉成浮點數) 20.to_s # "20" (轉成字串) 1.2.round # 1 (四捨五入) # 字串也是物件 "KERKER".length # 6 (取字串長度) "hello".upcase # "HELLO" (轉成大寫) # Array也是物件 [1,5,2].sort # [1,2,5] (陣列排序) [1,2,3].reverse # [3,2,1] (陣列反轉) a.push("f") # 作為stack使用
這些用法都很簡單,也很直覺。