三个嵌套的for循环会降低性能 - python

我想知道是否还有另一种方法可以像我在这里那样不使用3个嵌套的for循环来解决此问题？我知道，如果在足够大的列表上测试该方法，以这种方式嵌套循环很可能会引起很多问题。

这是问题：

from typing import List

def can_pay_with_three_coins(denoms: List[int], amount: int) -> bool:
    """Return True if and only if it is possible to form amount, which is a
    number of cents, using exactly three coins, which can be of any of the
    denominations in denoms.

    >>> can_pay_with_three_coins([1, 5, 10, 25], 36)
    True
    >>> can_pay_with_three_coins([1, 5, 10, 25], 37)
    False

    """

这是我的解决方案：

for i in range(len(denoms)):
    one_coin = denoms[i]
    for j in range(len(denoms)):
        another_coin = denoms[j]
        for k in range(len(denoms)):
            last_coin = denoms[k]
            if one_coin + another_coin + last_coin == amount:
                return True
return False

我确信还有另一种解决这个问题的方法，只是我真的没有想到。谢谢你的帮助！

参考方案

好吧，让我们用itertools作弊:)

import itertools
from typing import List


def can_pay_with_three_coins(denoms: List[int], amount: int) -> bool:
    """Return True if and only if it is possible to form amount, which is a
    number of cents, using exactly three coins, which can be of any of the
    denominations in denoms.

    >>> can_pay_with_three_coins([1, 5, 10, 25], 36)
    True
    >>> can_pay_with_three_coins([1, 5, 10, 25], 37)
    False

    """

    for variant in itertools.permutations(denoms, len(denoms)):
        if sum(variant[:3]) == amount:
            return True

    return False


print(can_pay_with_three_coins([1, 5, 10, 25], 36))
print(can_pay_with_three_coins([1, 5, 10, 25], 37))
print(can_pay_with_three_coins([1, 1, 5, 10, 25], 37))
print(can_pay_with_three_coins([1, 3, 5, 10, 25], 37))
print(can_pay_with_three_coins([20, 20, 20, 50], 60))

输出

True
False
False
False
True

Python 3运算符>>打印到文件 - python

我有以下Python代码编写项目的依赖文件。它可以在Python 2.x上正常工作，但是在使用Python 3进行测试时会报告错误。depend = None if not nmake: depend = open(".depend", "a") dependmak = open(".depend.mak&#…

Python:对于长时间运行的进程，通过还是休眠？ - python

我正在编写一个队列处理应用程序，该应用程序使用线程等待和响应要发送到该应用程序的队列消息。对于应用程序的主要部分，只需要保持活动状态即可。对于像这样的代码示例:而True: 通过要么而True: time.sleep(1)哪一个对系统的影响最小？除了保持python应用运行外，什么都不做的首选方式是什么？ 参考方案 我可以想象time.sleep()会减少系…

Python:无符号32位按位算术 - python

试图回答另一篇有关其解决方案涉及IP地址和网络掩码的文章时，我陷入了普通的按位算法。在Python中，是否存在一种标准的方式来进行按位AND，OR，XOR，NOT运算，假设输入是“32位”(可能是负数)整数或long，并且结果必须是[[ 0，2 ** 32]？换句话说，我需要一个与无符号长整数之间的C按位运算有效的Python对应物。编辑:具体问题是这样的:…

>> Python中的运算符 - python

>>运算符做什么？例如，以下操作10 >> 1 = 5有什么作用？ 参考方案 它是右移运算符，将所有位“右移”一次。二进制10是1010移到右边变成0101这是5

Python:如何从字节中提取特定位？ - python

我有一条消息，显示为14 09 00 79 3d 00 23 27。我可以通过调用message[4]从此消息中提取每个字节，例如，这将给我3d。如何从该字节中提取单个8位？例如，如何将24-27位作为单个消息？只需28位？ 参考方案 要回答问题的第二部分，您可以使用按位运算来获取特定的位值# getting your message as int i = …