› 看板 Soft_Job 關於我們 聯絡資訊
作者holydc (のヮの)
看板Soft_Job
標題Re: [討論] 面試遇到的考題
時間Fri Jul 4 21:01:17 2014
※ 引述《sleeper0121 (sleeper)》之銘言： : 今天去面試，裡面有題題目是這樣: : 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0 : 請回傳一個陣列裡面相鄰互乘的最大整數值 : 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5] : 就是 2 * 3 * 8 = 48 : 再一個例子: [-2 , 0 , 3 , 5 , -7] : 就是 3 * 5 = 15 : 請問這題思考邏輯大概是怎樣呢? : 當下沒解出來，害我回家後還一直再想 XD 今天在 facebook 釣出高手，我想應該是最正確的演算法了 先從左邊乘過去，再從右邊乘回來，遇 0 重算，取最大值 以 { 2, -7, 0, 2, 3, 8, -6, 5 } 來說 左邊乘過去會得到 2, -14, 0, 2, 6, 48, -288, -1440 右邊乘回來會得到 5, -30, -240, -720, -1440, 0, -7, -14 幾個值，得到最大值 48 我的實作 http://ideone.com/dmOEEO 沒判斷子陣列只有一個元素的情況，不過題目也沒定義所以就算了 :p -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.23.220 ※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404478881.A.E1B.html
→ Lwms:-2, 10, 10, -2 呢？ 07/04 21:28
→ holydc:400 呀 07/04 21:30
推 BlazarArc:有趣 07/04 21:36
→ Lwms:好妙 07/04 21:38
推 bonny5566:讚 07/04 21:45
※ 編輯: holydc (36.231.23.220), 07/04/2014 21:55:17
推 michael0728n:(y) 07/04 22:29
推 lovdkkkk:推 再加點判斷還可以只要單向算過去就好 07/04 23:17
推 pika0923:這作法還不錯 要看單向版本可以看我那篇 07/04 23:19
推 dementia:推 07/05 02:21
推 Tr3e:好方法! 07/05 10:17
→ y3k:Good 07/05 10:33
推 orz811017:好厲害！！！ 07/05 13:14
推 twsh:引用一樓-2 10 10 -2 -3 呢?(-2 -20 -200 400 -1200) max600 07/05 14:09
→ twsh:忘了還有右邊乘回來的 07/05 14:11
推 typepeter:Push 07/05 15:13
→ dlikeayu:我那篇有右邊乘回來同時把last value做動態變動的 07/05 15:28
推 pika0923:樓上 你那篇跑[-2, 2, -2]好像不會算出8? 07/05 15:41
→ dlikeayu:真的也 那篇只有回原Po的解決方式 看來要加判斷式 07/05 15:53
→ dlikeayu:應該還是能在O(n)內解決 07/05 15:53
→ dlikeayu:http://jsfiddle.net/ERKxh/3/ 這是有多一些設定的 07/05 15:54
→ dlikeayu:但是還是不能解決全部算完是正的 晚點來看 07/05 15:54
推 BruceX:0 999 999 999 999 999 999 999 999 999 999 999 999 999 0 07/05 15:55
→ typepeter:要解過大的數字 那只能建質數表 因式分解 最終才用大數 07/05 18:37
→ javatea:...不是這樣吧 ... 這個例子0的位置讓他歪打正著 07/06 06:50
推 a126095653:[-0.5, 2, 2, -0.5] 就會算錯喔 07/06 19:46
推 a126095653:喔喔我搞錯如果題目只有整數就是對的 07/06 19:54
推 SansWord:-1,-2,-3,-4,-5,-6,-7 07/07 18:38
推 ypwalter:bruceX: 遇到零就重算 07/08 00:39
→ ypwalter:SansWord, 計算過程中取大的值, 所以反方向算回來就可以 07/08 00:39
→ ypwalter:holydc: 這...這...這好像是我在你facebook的解法!!! 07/08 00:40
推 ypwalter:pika0923: 你的是單向沒錯 07/08 00:42
→ ypwalter:可是你有考慮過你每次都要做很多次乘積和三數取大/小 07/08 00:42
→ ypwalter:雖然大家都是O(n), 可是我這邊實際跑出數字應該是不會 07/08 00:43
→ ypwalter:比較慢?! 07/08 00:43
樓上就是被釣出來的高手 <(_ _)> 又釣到一次!! XD ※ 編輯: holydc (36.231.119.219), 07/08/2014 09:56:24
推 lovdkkkk:這個方法改一下就可以單向了 07/08 13:54
→ lovdkkkk:乘出負數時若之前沒有就記下來 07/08 13:54
→ lovdkkkk:若之前有就除掉之前記下的數, 這樣就不必反向算回來 07/08 13:55
→ lovdkkkk:實際速度會不會比較快就...要測看看 @@ 07/08 13:57
→ lovdkkkk:更進一步, 只有零的前一個是負數時需要去除, 中間不必 07/08 15:07
→ lovdkkkk:這樣應該就確定會比較快 07/08 15:08
推 ypwalter:剛剛看了一下lovdkkkk, 理論上你的做法應該會快些 07/08 17:03
→ ypwalter:而且也才是真的one parse 07/08 17:03
→ ypwalter:(1 parse比2 parse複雜的情況其實就當他不是好了...) 07/08 17:04
推 drkkimo:perfact! 07/09 00:54
推 pika0923:現在才看到yp回的 嚴格說起來用ruby作已經比c慢20倍了XD 07/10 00:44
→ pika0923:而最大最小值其實算是為了閱讀方便 07/10 00:45
→ pika0923:如果玩過這類演算法競賽就會知道 在同一個語言的實作下 07/10 00:45
→ pika0923:其實答案對量級對之後實作差異非常小 07/10 00:46
→ pika0923:甚至有時候把一堆判斷式省掉還會比較快 07/10 00:46
→ pika0923:加一堆判斷式有時候是省小錢花大錢的作法 07/10 00:47
→ pika0923:我還蠻喜歡你這篇的作法就是因為概念簡單正確XD 07/10 00:48
推 lovdkkkk:以 C 來說的話, 判斷相對於乘/除法是可以忽略的 07/10 03:09
→ lovdkkkk:(除非判斷的對象本身需要其它運算) 07/10 03:10
→ lovdkkkk:真的想再省的話, 只要多記一組數 (3 個 int) 07/10 03:17
→ lovdkkkk:就可以把處理和原本判斷遇 0 重算的部份寫在一起 07/10 03:18
→ lovdkkkk:以及在廻圈結束後再處理最後一個數 07/10 03:19
→ lovdkkkk:更正, 多記一個 int 應該就夠了 07/10 03:19
→ lovdkkkk:想成把處理前一個負數包成 function 07/10 03:39
→ lovdkkkk:遇零及廻圈結束後再 call 一下就好, 只要多記前一個算的 07/10 03:40
→ lovdkkkk:值, 位置則可以直接用推的 07/10 03:40
→ lovdkkkk:再更正, 應該也不用多記, 在算下一個之前先處理就好 07/10 08:01
推 ypwalter:pika0923: XD 因為我只想得出奇怪的解法XD 07/15 08:59
→ ypwalter:不過是說 這其實有個複雜的證明在後面... 07/15 09:00
→ ypwalter:理論上可以用數學歸納法證明...只要證明1~3個數字的數列 07/15 09:00
→ ypwalter:然後最後在推廣他應該就可以 07/15 09:00
→ ypwalter:lovdkkkk: 我自己實際上去看應該是多記一個負數就可 07/15 09:01