小编Kin*_*ber的帖子

这是一个谷歌面试问题,我使用HashMap或类似的数据结构在线找到大多数答案.我想尽可能找到使用Trie的解决方案.有人可以给我一些提示吗？

这是一个问题:您将获得一个字典,其形式为每行包含一个单词的文件.例如,

abacus 
deltoid 
gaff 
giraffe 
microphone 
reef 
qar 

您还会收到一系列信件.例如,

{a, e, f, f, g, i, r, q}. 

任务是找到字典中可以拼写字母集合的最长单词.例如,上面示例值的正确答案是"长颈鹿".(注意"礁石"不是一个可能的答案,因为这组字母只包含一个"e".)

Java实现将是首选.

所以这是一个问题:

在一个派对中,有n种不同口味的蛋糕,每卷的体积为V1,V2,V3 ...... Vn.需要将它们划分为存在于党内的K人

• 派对的所有成员获得相同数量的蛋糕(比如V,这是我们正在寻找的解决方案)

• 每个成员应该只获得一种单味的蛋糕(你不能将不同风味蛋糕的部分分配给一个成员).

• 分配后会浪费一些蛋糕,我们希望尽量减少浪费; 或者,等同于我们遵循最大分配政策

给定已知条件:如果V是最优解,那么至少一个滤饼X可以除以V而不留任何体积,即Vx mod V == 0

我正在努力寻找具有最佳时间复杂度的解决方案(蛮力会做到这一点,但我需要更快的方式).

任何建议将不胜感激.

谢谢

PS:这不是作业,而是面试问题.这是蛮力的pseducode:

int return_Max_volumn(List VolumnList)
{
    maxVolumn = 0;
    minimaxLeft = Integer.Max_value;
    for (Volumn v: VolumnList)
         for i = 1 to K people
             targeVolumn = v/i;
             NumberofpeoplecanGetcake = v1/targetVolumn + 
                 v2/targetVolumn + ... + vn/targetVolumn
             if (numberofPeopleCanGetcake >= k)
                  remainVolumn = (v1 mod targetVolumn) + (v2 mod targetVolumn)
                   + (v3 mod targetVolumn + ... + (vn mod targetVolumn)
                  if (remainVolumn < minimaxLeft)
                       update maxVolumn to …