这个问题来自Google Foobar,我的代码通过了除最后一个测试外的所有测试,其中输入/输出被隐藏。
提示:
换句话说,选择数组中的两个元素x [i]和x [j](i不等于j),同时将x [i]增加1并将x [j]减少1。你的目标是尽可能多地使数组中的元素具有相等的值。
例如,如果数组是[1,4,1],则可以执行以下操作:
从第1个车发送兔子到第0个车:增加x [0],减少x [1],结果为[2,3,1]
从第1个车发送兔子到第2个车:增加x [2],减少x [1],结果为[2,2,2]。
现在,数组中所有元素都相等了,你可以向Beta Rabbit报告策略!
请注意,如果数组是[1,2],我们可以获得的最大相等元素数量为1,因为车上的兔子数量永远无法相同。
编写函数answer(x),它接受整数数组x并返回我们可以通过执行上述命令多次获得的最大相等数组元素数量。
火车中的车辆数(x中的元素)至少为2,但不超过100。要共享车的兔子数量(x的每个元素)将是范围内的整数[0,1000000]。
提示:
换句话说,选择数组中的两个元素x [i]和x [j](i不等于j),同时将x [i]增加1并将x [j]减少1。你的目标是尽可能多地使数组中的元素具有相等的值。
例如,如果数组是[1,4,1],则可以执行以下操作:
从第1个车发送兔子到第0个车:增加x [0],减少x [1],结果为[2,3,1]
从第1个车发送兔子到第2个车:增加x [2],减少x [1],结果为[2,2,2]。
现在,数组中所有元素都相等了,你可以向Beta Rabbit报告策略!
请注意,如果数组是[1,2],我们可以获得的最大相等元素数量为1,因为车上的兔子数量永远无法相同。
编写函数answer(x),它接受整数数组x并返回我们可以通过执行上述命令多次获得的最大相等数组元素数量。
火车中的车辆数(x中的元素)至少为2,但不超过100。要共享车的兔子数量(x的每个元素)将是范围内的整数[0,1000000]。
from collections import Counter
def most_common(lst):
data = Counter(lst)
return data.most_common(1)[0][1]
def answer(x):
"""The goal is to take all of the rabbits in list x and distribute
them equally across the original list elements."""
total = sum(x)
length = len(x)
# Find out how many are left over when distributing niavely.
div, mod = divmod(total, length)
# Because of the variable size of the list, the remainder
# might be greater than the length of the list.
# I just realized this is unnecessary.
while mod > length:
div += length
mod -= length
# Create a new list the size of x with the base number of rabbits.
result = [div] * length
# Distribute the leftovers from earlier across the list.
for i in xrange(mod):
result[i] += 1
# Return the most common element.
return most_common(result)
在我的测试中,它可以很好地处理一百万次尝试的操作,并且只需要十秒钟左右。但是当输入未知时,它会失败。
我是否忽略了一些显而易见的东西,或者做了我不该做的假设?