Re: [討論] 面試遇到的考題

看板Soft_Job作者 (自立而後立人)時間10年前 (2014/07/03 15:03), 10年前編輯推噓8(8推 0噓 20→)
留言28則, 8人參與, 最新討論串2/27 (看更多)
※ 引述《sleeper0121 (sleeper)》之銘言： : 今天去面試，裡面有題題目是這樣: : 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0 : 請回傳一個陣列裡面相鄰互乘的最大整數值 : 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5] : 就是 2 * 3 * 8 = 48 : 再一個例子: [-2 , 0 , 3 , 5 , -7] : 就是 3 * 5 = 15 : 請問這題思考邏輯大概是怎樣呢? : 當下沒解出來，害我回家後還一直再想 XD 暴力解(in JavaScript)，裡面有應用到部份 DP 的觀念。 var input = [-2,0,3,5,-7]; var result = {sum:input[0],items:[input[0]]}; var stacks = []; for(var i = 0 ; i < input.length ;++i){ var now = input[i]; if(now == 0){ //優化 stacks.length = 0; //drop old queue continue; } for(var j = 0 ; j < stacks.length ;++ j){ stacks[j].sum *= now; stacks[j].items.push(now); if(stacks[j].sum > result.sum){ result.sum = stacks[j].sum; result.items = stacks[j].items.slice(0); } } stacks.push({sum:now,items:[now]}); if(now > result.sum){ result.sum = now; result.items = [now]; } } console.log(result.sum, result.items); 解題邏輯 [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5] 2 2 * -7 -7 0(清queue) 2 2 * 3 3 2 * 3 * 8 3 * 8 8 2 * 3 * 8 * -6 3 * 8 * -6 8 * -6 2 * 3 * 8 * -6 * 5 3 * 8 * -6 * 5 8 * -6 * 5 -6 * 5 5 ......... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.75.169.82 ※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404370996.A.997.html ※ 編輯: TonyQ (211.75.169.82), 07/03/2014 15:03:48
推
07/03 15:12, , 1F
DP全名為何?
07/03 15:12, 1F
推
07/03 15:13, , 3F
Dynamic Programming
07/03 15:13, 3F
→
07/03 15:13, , 4F
btw 這個解法的複雜度約 O(n^2)
07/03 15:13, 4F
→
07/03 15:14, , 5F
我相信如果對 0 跟正負號 optimzed 的話，或許還可以再降
07/03 15:14, 5F
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 15:21:06
推
07/03 15:17, , 6F
我猜用 divide conquer? 如果左右同號，那兩邊連起來的結果
07/03 15:17, 6F
→
07/03 15:17, , 7F
更好
07/03 15:17, 7F
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 15:22:02
→
07/03 15:23, , 8F
我目前能想到的是碰到 0 就 drop 舊的 queue。
07/03 15:23, 8F
→
07/03 15:23, , 9F
針對正負號的狀況因為鏈上碰到幾個號很難說 我現在想不到
07/03 15:23, 9F
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 15:25:16 ※ 編輯: TonyQ (211.75.169.82), 07/03/2014 15:27:15 ※ 編輯: TonyQ (211.75.169.82), 07/03/2014 15:32:14
推
07/03 15:38, , 10F
先以0為切口切成幾個小array,算小array的答案就好
07/03 15:38, 10F
→
07/03 15:38, , 11F
小array裡面先算有幾個負數 偶數個直接相乘就是小
07/03 15:38, 11F
→
07/03 15:39, , 12F
array的答案,若有奇數個負數,則把第一個或最後一個
07/03 15:39, 12F
→
07/03 15:40, , 13F
負數切掉乘乘看就行
07/03 15:40, 13F
→
07/03 15:41, , 14F
例如 2,-1,3,-4,5 就試試看2*-1*3跟3*-4*5取大的
07/03 15:41, 14F
→
07/03 15:41, , 15F
阿錯了= =
07/03 15:41, 15F
→
07/03 15:42, , 16F
2,-1,-3,-4,5就試試看2*-1*-3跟-3*-4*5就行了
07/03 15:42, 16F
→
07/03 15:42, , 17F
求得小array的答案後比哪個答案最大就是答案
07/03 15:42, 17F
→
07/03 15:43, , 18F
這樣的話應該是O(N)
07/03 15:43, 18F
推
07/03 15:47, , 19F
你要把SORT的時間算進去阿
07/03 15:47, 19F
→
07/03 15:48, , 20F
欸...不太對
07/03 15:48, 20F
推
07/03 15:48, , 21F
michael0728n +1
07/03 15:48, 21F
推
07/03 15:48, , 22F
find max應該也是O(N)啦如果我沒想錯的話 不用sort
07/03 15:48, 22F
→
07/03 16:07, , 23F
我寫了一版 micahel0728n 的版本，但有點醜
07/03 16:07, 23F
→
07/03 16:07, , 24F
我發現切掉其實有兩種切法，往前切跟往後切，所以有點麻煩
07/03 16:07, 24F
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 16:20:57
→
07/03 16:59, , 25F
用 michael0728n 的概念寫了一版 (python)
07/03 16:59, 25F
推
07/03 20:39, , 27F
本來也有想自己寫一版,不過想想就覺得有點麻煩XD
07/03 20:39, 27F
→
07/04 16:05, , 28F
07/04 16:05, 28F
‣ 更多 TonyQ 的文章
文章代碼(AID): #1JjG0qcN (Soft_Job)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 2 之 27 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共27篇)
‣ 更多 TonyQ 的文章
文章代碼(AID): #1JjG0qcN (Soft_Job)