我在面试中被问到以下问题,我仍在思考一种有效的方法。
您有一个数组,其数字表示桶中液体的百分比。您还有一个带有方法的 API:combine(int x,int y)
,它在数组中获取两个输入百分比,并且将一个桶中的液体混合到另一个桶中。通过使用此信息,您必须找到 100% 液体可能的最大桶数。
示例 1. 数组:10,15,20,35,55,65
答案:桶数为2。
由于 combine(65,35)
---一个 100% 桶,
combine(55,20)
--75% barrel, next combine(75,15)
--90% next combine(90,10)
--100%--1桶
所以一共2桶
例子2:99,99,99
Ans:此处的桶数将为 1,因为您执行了combine(99,99)
——您得到一个 100% 的桶,其余的液体被浪费了并且你不能将任何其他桶与第三个 99% 的桶组合起来使其成为 100
注意:一旦将液体从一个桶倒入另一个桶中,就不能再使用它
例如:combine(55,15)
--70% 桶。您可以使用 70% 桶,但不能使用 55% 和 15% 桶。
最佳答案
您确实可以查看装箱问题的算法。 This student paper表示其中四个。具有最佳近似值的算法是 Decreasing First Fit 算法。
归结为快速排序(原地,平均时间复杂度为 O(nlogn),最坏情况为 O(n2)),然后是首次拟合。
First Fit 按顺序扫描箱子,并将新元素放入第一个足够大的箱子中。如果没有适合当前对象的容器,则启动一个新容器。
要在 O(nlogn) 复杂度中进行 FF,请使用 Max Winner Tree 数据结构。它有 n 个外部节点(玩家)和 n-1 个内部节点(每场比赛的获胜者), 获胜者是值(value)最大的玩家。
关于arrays - 加起来为 100 的百分比数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16256663/