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

看板Soft_Job作者pika0923 (宜安)時間11年前 (2014/07/03 17:18)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串5/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 想了一個作法開兩個陣列存 "含有這個位子及以左的最大值和最小值" 叫他amax和amin好了由於這題目一定是整數在這裡絕對值要變大就要一路乘下去不然就不乘(0的狀況) 所以 amax[x]會是 ar[x], ar[x]*amax[x-1], ar[x]*amin[x-1]三者之一同理 amin[x]也會出現在其中而所求的區段一定有個結尾也一定被某個amax[x]算到所以最後求amax的最大值即可 -- 寫了一個ruby code(最近正在練習XD) 就算當作演算法的pseudo code應該也不會太難讀 ar = gets.split(' ').map(&:to_i) #讀陣列 amin, amax = [ar[0]], [ar[0]] #初始化 (1...(ar.length)).each do |x| #迴圈,把剩下的跑完 amin << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].min #見上述 amax << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].max #見上述 end p amax.max -- 前文的2 -7 0 2 3 8 -6 5 -1是可以正確求解的 (是說這題比較像是prob_solve版的業務雖然說那邊人也不太多就是^^") -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.127.4.157 ※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404379102.A.0D1.html

推

aknow

07/03 18:11, , 1^F

07/03 18:11, 1^F

補上長度至少2的作法 "長度至少2"的最佳解會由 "尾端一個數"串上"前面至少一個數的最佳解"求得 bmax ar[x] amax[x-1],amin[x-1] 因此只需要在後面加上幾行修正即可 code如下 ar = gets.split(' ').map(&:to_i) amin, amax = [ar[0]], [ar[0]] (1...(ar.length)).each do |x| amin << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].min amax << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].max end bmax = [] (1...(ar.length)).each do |x| bmax << [ar[x]*amin[x-1],ar[x]*amax[x-1]].max end p bmax.max ※ 編輯: pika0923 (59.127.4.157), 07/03/2014 19:34:32

推

michael0728n

07/03 20:34, , 2^F

07/03 20:34, 2^F

推

dementia

07/03 23:09, , 3^F

07/03 23:09, 3^F

推

twsh

07/03 23:35, , 4^F

07/03 23:35, 4^F