推 kurakidream:推 實用 感謝分享 07/10 08:18
※ 編輯: lovdkkkk (36.226.184.121), 07/12/2014 04:58:58
※ 引述《sleeper0121 (sleeper)》之銘言：
: 今天去面試，裡面有題題目是這樣:
: 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0
: 請回傳一個陣列裡面相鄰互乘的最大整數值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一個例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 請問這題思考邏輯大概是怎樣呢?
: 當下沒解出來，害我回家後還一直再想 XD
閒聊一些 tips
這類型問題算是相當的經 (ㄌㄠˇ) 典 (ㄍㄥˇ)，
(因為有最後附的那個，複雜度更高的經典中的經典...)
就是一個或兩個什麼列怎樣怎樣的這種，
經典程度大概是一看就直覺有 O(N) (一列) 或 O(M*N) (二列) 的解，
可能可以一回掃過去這樣
臨場解題時大致有一定的步驟。
1. 找出邏輯
具體作法就是列幾種可能的 case，
多列個幾種正負數與零的組合手算一下，
找出 "什麼時候要怎樣" 這樣的規則。
以這題來說大約五個 case 左右就足以找出必要的規則。
2. 寫出解法
這有幾種選擇。
最直接的就是直接照 1 找出的邏輯刻，
或許最基本的暴力解或某種程度的優化。
時間有限下這也是一種選擇，
但寫字速度可能要夠快...
或者可以試著將問題 "視覺化"，
對不同類型的問題有不同的視覺化方法，
例如畫圈圈集合圖、畫棒棒甘特圖等，
而以這一題來說，矩陣是很適合的方式。
視覺化有什麼好處呢？
就是你只要簡單的畫好一個有足夠代表性的 case，
透過觀察其內容便可以很快地找出許多實際運作上的細節，
並且可以不斷地在上面比手劃腳跑模擬過程。
有沒有視覺化的差距大概就像是
1. 寫一行字 "秦滅六國"
2. 除了上面這行再給你 http://ppt.cc/68Te 這樣一張圖
這兩者的差距
ex 設一數列 1, -1, 2, 3, 0, 1, -2, 2, 3, -5, -4
可以畫出像底下的矩陣 (部份省略)
1 -1 2 3 0 1 -2 2 3 -5 -4
1 -1 -2 -6 0
-1
2 6
3
0
1 -2 -4 -12 60 -240
-2
2 120
3
-5
-4
[i, j] 為第 i 位連續乘到第 j 位的值 (這裡以把連續算相鄰為例)
然後就可以看到在 [1, 5] 遇到 0 時要重算，
重算的動作就是 i = j+1, j = j+2 再繼續，
然後就可以耍帥 i = ++j++; 面試官看了不爽 -> 刷掉
然後也很容易看出乘到負的時若前面有出現過負數，
只要除掉前面第一個出現的負數就能取到最大正數，
(這其實就是 以第一個負號切 或 分兩群 的部份，
實做上只要除一下就好，不需要真的分子數列)
也能觀察出中間的負數不用管，
只要處理階段的最後一個 (0 的前一個或整個數列的最後一個)。
(因為越乘數字一定越大，
如果之後變正數就不必處理，最後還是負數則只要處理最後的)
從矩陣中經過候選答案的路徑也能看出只要一路乘下去就好，
(不過也有此例看不到的,
假設數列為 1, -1, 2, 0, ...，
那在乘到 -2 時若不可取單一數則不能對其做處理，
亦即要判斷與最前面出現負數的位置有超過二才能處理)
實際操作上，比起像上例畫一個較大的矩陣 (為了舉例方便 @@)，
多畫幾個小 case 可能更有幫助。
視覺化還有幾個好處，
首先考官看到你知道要畫矩陣輔助應該會加分，
其次寫字慢程式難產的話，
靠比手畫腳或虛擬碼/文字說明搭配矩陣也足以說明。
甚至這也可以是你篩選公司的做法，
假如可以清楚提出好的解只是 code 寫不完而被刷掉，
這公司可能不去也罷。(純舉例，不鼓勵，請自行負責。)
當然夠熟的話就不用視覺化，腦內推推就夠了。
附上另一個類似的可以用矩陣表示求解的經典問題，
兩個字串找最長共同子序列
longest common subsequence: http://ppt.cc/k9nd
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.226.184.121
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404898117.A.FF1.html