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

Question

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

We want to make a row of bricks that is goal inches long. We have a number of small bricks (1 inch each) and big bricks (5 inches each). Return True if it is possible to make the goal by choosing from the given bricks.

Test cases:

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

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

I am getting Time Out error when I submit my code on CodingBat Python (https://codingbat.com/prob/p118406)

python

for-loop

if-statement

return