Thursday, March 22, 2018

[LeetCode]Super Washing Machines

这道题我们可以观察出几点,假设我们有n台洗衣机:

  1. 如果衣服的总数不能被n整除,显然我们不能做到;如果能做到,每台机器最终被分配的衣服数量是固定的,假设为k
  2. 以处在i的机器为界,根据k,我们可以算出从[0 : i]流向[i + 1 : n - 1]的衣服数量m1;同时,我们也可以算出需要从[i : n - 1]流向[0 : i - 1]的数量m2,m1 + m2就是机器i需要被选择的总次数m
  3. 算出所有机器的m,求最大值即可
时间复杂度O(n),空间O(1),代码如下:


No comments:

Post a Comment