我正在解决 codingbat 上的编码问题在 Python 中。 make_bricks问题定义为:
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. This is a little harder than it looks and can be done without any loops.
make_bricks(3, 1, 8) → True make_bricks(3, 1, 9) → False make_bricks(3, 2, 10) → True
我想到的第一个解决方案是:
from itertools import permutations
def make_bricks(small, big, goal):
l = small*[1]+big*[5]
return any([(goal in i) for i in ([[sum(j) for j in set(permutations(l,i))] \
for i in range(2,len(l)+1)])])
这是正确的，但被评审软件拒绝了，因为不允许导入。 所以我的下一个解决方案是:
def make_bricks(small, big, goal):
bricks = small*[1]+big*[5]
for step in range(len(bricks)+1,1,-1):
for start in range(len(bricks)):
if len(bricks[start:start+step])==step:
if sum(bricks[start:start+step])==goal:
return True
return False
这也是正确的，但是在像 make_bricks(1000000, 1000, 1000100) 这样的输入时被超时阻塞了。
那么，您将如何在不使用导入、不使用循环和限时的情况下用 Python 解决这个问题？
请您参考如下方法:
def make_bricks(small, big, goal):
if goal > small + big * 5:
return False
else:
return goal % 5 <= small
