Re: [討論] 面試遇到的考題
※ 引述《TonyQ (自立而後立人)》之銘言：
: 推 michael0728n:先以0為切口切成幾個小array,算小array的答案就好 07/03 15:38
: → michael0728n:小array裡面先算有幾個負數 偶數個直接相乘就是小 07/03 15:38
: → michael0728n:array的答案,若有奇數個負數,則把第一個或最後一個 07/03 15:39
: → michael0728n:負數切掉乘乘看就行 07/03 15:40
: → michael0728n:例如 2,-1,3,-4,5 就試試看2*-1*3跟3*-4*5取大的 07/03 15:41
: → michael0728n:阿錯了= = 07/03 15:41
: → michael0728n:2,-1,-3,-4,5就試試看2*-1*-3跟-3*-4*5就行了 07/03 15:42
: → michael0728n:求得小array的答案後比哪個答案最大就是答案 07/03 15:42
: → michael0728n:這樣的話應該是O(N) 07/03 15:43
: 推 GoalBased:你要把SORT的時間算進去阿 07/03 15:47
: → GoalBased:欸...不太對 07/03 15:48
: 推 carrlyea:michael0728n +1 07/03 15:48
: 推 michael0728n:find max應該也是O(N)啦如果我沒想錯的話 不用sort 07/03 15:48
: → TonyQ:我寫了一版 micahel0728n 的版本，但有點醜 07/03 16:07
: → TonyQ:我發現切掉其實有兩種切法，往前切跟往後切，所以有點麻煩 07/03 16:07
我參考 miachel 意見實作的版本，雖然我覺得我應該是寫複雜了。 XD
var input = [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5];
var result = {sum:input[0],items:[input[0]]};
var stacks = [];
var counter = 0;
var queue = [];
var negatives = [];
function sum(ary){
if(ary.length == 0){
return null;
}
var _sum = ary[0];
for(var i= 1 ;i< ary.length;++i){
_sum *= ary[i];
}
return {sum:_sum,items:ary};
}
function get_result(queue,negatives){
if(negatives.length %2 == 0 || queue.length == 1){
return sum(queue);
}else if(negatives.length == 1){
var sum1 = sum(queue.slice(0,negatives[0]));
var sum2 = sum(queue.slice(negatives[0] +1 ));
return sum1.sum > sum2.sum ? sum1 : sum2;
}else{
var now_sum = null;
var sums = [
sum(queue.slice(0,negatives[0])),
sum(queue.slice(negatives[0] +1 )),
sum(queue.slice(0,negatives[1])),
sum(queue.slice(negatives[1] +1 ))];
now_sum = sums[0];
for(var i =1;i<sums.length;++i){
if(now_sum.sum > sums[i].sum){
now_sum = sums[i];
}
}
return now_sum;
}
}
for(var i = 0 ; i < input.length ;++i){
var now = input[i];
if(now == 0){ //切 0
var now_sum = get_result(queue,negatives); //算分區的分數
if(now_sum != null && now_sum.sum > result.sum){
result = now_sum;
}
negatives = [];
queue = [];
continue;
}
queue.push(now);
if(now < 0 ){
negatives.push(queue.length -1);
}
}
if(queue.length){ //最後一塊
var now_sum = get_result(queue,negatives);
if(now_sum != null && now_sum.sum > result.sum){
result = now_sum;
}
}
console.log(result.sum, result.items,counter);
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.75.169.82
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404375395.A.476.html
→
07/03 16:17, , 1F
07/03 16:17, 1F
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 16:19:21
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 16:21:08
→
07/03 16:29, , 2F
07/03 16:29, 2F
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 16:31:16
※ 編輯: TonyQ (211.75.169.82), 07/03/2014 16:32:23
推
07/03 16:52, , 3F
07/03 16:52, 3F
討論串 (同標題文章)