阿里java实习

刚才做了阿里的java实习生的在线编程测试30min一道题：两个数组，要求合并成一个数组，使得到的数组的两两相乘的和最小，输出这个和。比如合并成「1，2，3，4」要求输出1*2+3*4的值。
条件数组等长，正整数，还有长度和大小的限，要求不改变每个数在原数组中的相对位置。
我做完发现做错了就不发解法了，祝各位好运。

这个不要紧的，看都不一定看

lwyucas 发表于 2018-3-30 13:21
我的测试也是这个题，想知道楼主怎么做的？我是比较a与a,b[j]分别相乘，留下结果小的，但是我总感觉我做的 ...

用了贪心，其实显然是不对的，不过我发现的时候已经没时间了。然后结束后写了个backtracking的方法，类似lc加括号那道题。不知道有没有更巧妙的方法

kaka123123 发表于 2018-4-9 22:14
每次两个选择 从第一个数字那两个数 或者第二个数字 或者不同数组 来形成两个数字相乘

哇，点醒我了
一次拿两个数，我开始没想到一次拿两个，一个一个拿，总有落单的，纠结死了

我的测试也是这个题，想知道楼主怎么做的？我是比较a[i-1]与a[i],b[j]分别相乘，留下结果小的，但是我总感觉我做的哪里不对

请问你投的是什么职位？他们oa都一样么？听说不能用python...害怕...不敢打开...

dp可以解

kaka123123 发表于 2018-4-6 10:42
dp可以解

想了一下午没写出来，请教求解。

孙博文 发表于 2018-4-9 18:59
想了一下午没写出来，请教求解。

每次两个选择 从第一个数字那两个数 或者第二个数字 或者不同数组 来形成两个数字相乘

哇 楼主好棒 感谢分享，你现在有思路了吗？我还没想出来

两两相乘的和最小是可以[1,2,3,4]也可以1*4+2*3么？