腾讯笔试编程题?

依依雨柔
  • 233

小q和博士在玩一个石子合并的游戏。初始一共有n堆石子,每堆石子有w[i]个石子。小q和博士他们需要对识字进行合并,每次他们可以选任意2堆石子合并。一堆有x个石子和一堆有y个石子的石子堆合并得到一堆有x+y个石子的石子堆,这次合并得分为x*y,只剩下一堆石子时游戏结束。小牛和博士希望采取优秀的策略获得最大得分,请算他们的最大得分是多少?
输入:一个正整数

  n个正整数,即每堆石子的个数

输出:最大得分
例:输入:3

     1,2,3
输出:11
回复
阅读 6.7k
7 个回答
✓ 已被采纳

其实你写出公式规律就很明显了

a1*a2 + (a1+a2)*a3 + (a1+a2+a3)*a4 ...
↓
a1*a2 + a1*a3 + a2*a3 + a1*a4 + a2*a4...

看到规律了吗,就是两两组合乘积之和。


$arr = [7,58,9,10,27,28];

$length = count($arr);
$score = 0;
for($i=0;$i<$length-1;$i++){
    rsort($arr);
    $score += $arr[0]*$arr[1];
    $arr[] = $arr[0] + $arr[1]; 
    unset($arr[0]);
    unset($arr[1]);


}
bitsman
  • 254

咋感觉有点想哈夫曼树呢,如果是累加的话,确实很像哈夫曼树,每次找两个最小的,合并成一个大的,之后再找两个最小的合并,成一颗哈夫曼树后,分数就很好算了

甜酒0917
  • 85

没想到好办法,只会这个笨办法

function getMax(ary,temp){
  var temp=temp||0;
     if(ary.length<2){
       return temp;
     }
     if(ary.length==2){
       temp+=ary[0]*ary[1]
       return temp;
     }
     var tempAry=[];
   for(var i=0;i<ary.length-1;i++){
     for(var j=i+1;j<ary.length;j++){
       var newAry=ary.filter(function(item,index){
         return index!=i&&index!=j;
       });
       newAry.push(ary[i]+ary[j]);
      tempAry.push(getMax(newAry,temp+ary[i]*ary[j])) 
     }
   }
    
     return Math.max.apply(null,tempAry);
}
    
console.log(getMax([7,58,9,10,27,28]))

这题是个陷阱啊,考的是数学知识,不管选取的顺序是什么,最终的结果是不变的
公式是:
( (n[1]+n[2]+n[3]+..+n[m])(n[1]+n[2]+n[3]+..+n[m])-(n[1]n[1]+n[2]n[2]+...n[m]n[m]) )/2

防止计算过程中整数溢出:

function getValue(ary){
  var addValue=0;
  var resultValue=0;
  for(var i=0;i<ary.length;i++){
   addValue+=ary[i];
  }
  for(var i=0;i<ary.length;i++){
   resultValue+=addValue*ary[i];
   resultValue-=ary[i]*ary[i];
  }
  return resultValue/2;
}
呱呱呱
  • 631

我用递归写一个吧

f(n) = f(n - 1) + n (1 + n - 1) (n - 1)/2

f(n)的得分等于f(n-1)的得分加上 n * (1+2+3+4+...+n-1),应该能看懂吧

function f(n) {
    if(n > 2) {
        return f(n - 1) + n*n*(n - 1)/2
    }else if(n === 2) {
        return 2
    }else {
        return 0
    }
}

我觉得题主题目出错了 得分应该是x+y并不是x*y

function sortNumber(a,b){return a-b};

var aN=[1,2,3]; // n组石子形成的数组
var total=0; // 最后得分

// 从小到大排序,用最小的2个相加形成新的数字
aN.sort(sortNumber);

do{

total+=aN[0]*aN[1];
aN.splice(0,2,aN[0]+aN[1]);
aN.sort(sortNumber);

}while(aN.length>=2)

console.log(total); // 11

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏