当我在CodingBat Python上提交代码时，出现了超时错误(https://codingbat.com/prob

Question

我正在CodingBat上练习，并尝试以下问题：

我们想做一排球门几英寸长的砖。我们有一些小砖块(每个1英寸(和大砖块(每个5英寸(。如果可以通过从给定砖块中进行选择来实现目标，则返回True。

测试用例：

• make_bricks(3, 1, 8)→True
• make_bricks(3, 1, 9)→False
• make_bricks(3, 2, 10)→True
• make_bricks(7, 1, 13)→False
• make_bricks(1, 4, 12)→False

当我在代码编辑器(VSCode(上运行我的代码时，我通过了每个测试用例，但当我在CodingBat上提交时(https://codingbat.com/prob/p118406)我得到和错误作为超时。请任何人解释我为什么，或者我下面的代码中有任何错误：

def make_bricks(small, big, goal):
myNum = 5
result = 0
i = 1
for i in range(big+1):
if (i * myNum) == goal:
return True
elif (i * myNum) > goal:
result = ((i * myNum) - myNum)
elif (i * myNum) < goal:
result = (i * myNum)
for i in range(small + 1):
if result + i == goal:
return True
return False
print(make_bricks(20, 0, 19))

Answer 1

您可以在没有循环的情况下计算它。是循环花费了太多时间。一些简单的算法和几个快速的早期检查应该可以解决这个问题：

def make_bricks(small, big, goal):
big_ = big * 5
max_ = big_ + small
if goal > max_:
return False  # impossible
if goal == max_:
return True  # simple case - just use all the bricks
if big_ > goal:
big_ = goal // 5 * 5
return big_ + small >= goal

Answer 2

超时发生在这个测试用例中：

make_bricks(2, 1000000, 100003) 

这可能是因为处理测试用例需要花费大量时间。在上面的测试用例中，代码迭代超过一百万次，在每次迭代中，它都会相乘并将结果存储到result中，以便在前999.999个循环中不使用：

elif (i * myNum) < goal:
result = (i * myNum)

你可以在没有循环的情况下进行计算：

def make_bricks(small_bricks_available, big_bricks_available, goal):
big_brick_size = 5
small_brick_size = 1

if goal < big_brick_size:
return small_bricks_available >= goal

big_bricks_needed = goal // big_brick_size

if big_bricks_needed > big_bricks_available:
big_bricks_needed = big_bricks_available
goal -= big_bricks_needed * big_brick_size
small_bricks_needed = goal // small_brick_size

# the first comparison is not necessary, but I left it for clarity
return big_bricks_available >= big_bricks_needed and small_bricks_available >= small_bricks_needed