亚麻 4.19 3轮VO

第二题感觉更像异灵意义的无序版。。。感觉楼主的题好难啊。。

第二题是无序的，因为无序其实感觉会更简单，我的思路是先按大小排序，【5,4,3,2,1】然后分成K组，每次放入一个List中的最大值进去K组中sum最小的组。最后返回K组中最大的sum。不知道对不对，应该不算是Hard的难度？

Sengo 发表于 2019-4-20 11:33
第二题是无序的，因为无序其实感觉会更简单，我的思路是先按大小排序，【5,4,3,2,1】然后分成K组，每次放入 ...

对，当时脑子抽了实在想不出来，现在想想感觉还好

Jarvet 发表于 2019-4-20 08:46
第二题感觉更像异灵意义的无序版。。。感觉楼主的题好难啊。。

就第二题可能乍一看不太会那种，其他两个还好啦

君为妖 发表于 2019-4-20 11:35
对，当时脑子抽了实在想不出来，现在想想感觉还好

祝楼主好运，拿offer

Sengo 发表于 2019-4-20 11:38
祝楼主好运，拿offer

借你吉言，祝早日上岸

Sengo 发表于 2019-4-20 11:33
第二题是无序的，因为无序其实感觉会更简单，我的思路是先按大小排序，【5,4,3,2,1】然后分成K组，每次放入 ...

这个贪心算法的证明怎么证明呢？想了很久，谢谢🙏

这个greedy algo可以用induction证，假设前i个数放入k个bucket后达到了最大值最小的状态，在考虑第k+1个数的时候，只有把它放在k个buckets中最小的那个bucket内才可以达到最大值最小的状态

LZ我感觉第二题就是lintcode上面的copy books，用dp做

补充内容 (2019-4-21 12:09):
看错题了请无视。。

hahazyb201 发表于 2019-4-21 09:31
这个greedy algo可以用induction证，假设前i个数放入k个bucket后达到了最大值最小的状态，在考虑第k+1个数 ...

谢谢回复！但是想到一个问题，如何说明需要提前把array提前从大到小排序。