水壶问题

难度: Medium

有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。

你可以：

装满任意一个水壶
清空任意一个水壶
将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。

示例 1:

输入: x = 3,y = 5,target = 4
输出: true
解释：
按照以下步骤操作，以达到总共 4 升水：
1. 装满 5 升的水壶(0, 5)。
2. 把 5 升的水壶倒进 3 升的水壶，留下 2 升(3, 2)。
3. 倒空 3 升的水壶(0, 2)。
4. 把 2 升水从 5 升的水壶转移到 3 升的水壶(2, 0)。
5. 再次加满 5 升的水壶(2, 5)。
6. 从 5 升的水壶向 3 升的水壶倒水直到 3 升的水壶倒满。5 升的水壶里留下了 4 升水(3, 4)。
7. 倒空 3 升的水壶。现在，5 升的水壶里正好有 4 升水(0, 4)。
参考：来自著名的 "Die Hard"

示例 2:

输入: x = 2, y = 6, target = 5
输出: false

示例 3:

输入: x = 1, y = 2, target = 3
输出: true
解释：同时倒满两个水壶。现在两个水壶中水的总量等于 3。

提示:

1 <= x, y, target <= 10³

Submission

运行时间: 34 ms

内存: 16.0 MB

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target > x+y:
            return False
        return target % gcd(x, y) == 0

Explain

这个题解利用了贝祖定理(Bézout's identity)的性质。贝祖定理指出，对于任意两个整数 x 和 y，存在整数 a 和 b 使得 ax + by = gcd(x, y)，其中 gcd(x, y) 表示 x 和 y 的最大公约数。题解的思路是： 1. 如果目标水量 target 大于两个水壶的容量之和 x+y，那么无论如何都无法达到目标水量，返回 False。 2. 否则，检查目标水量 target 是否可以被 x 和 y 的最大公约数整除。如果可以整除，那么可以通过某种倒水方案达到目标水量；否则无法达到目标水量。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        # 如果目标水量大于两个水壶的容量之和，无法达到目标水量
        if target > x + y:
            return False
        
        # 计算两个水壶容量的最大公约数
        # 如果目标水量是最大公约数的整数倍，则可以通过倒水达到目标水量
        return target % gcd(x, y) == 0

Explore

在水壶问题中，贝祖定理的运用是基于这样一个事实：任意使用两个容量分别为x和y的水壶，我们能够通过不断倒入或倒出水来组合出的水量必须是两个水壶容量的最大公约数（gcd）的倍数。这里的ax + by = gcd(x, y)表达式中的a和b可以是任意整数（包括负数），代表向水壶中加水或从水壶中倒水，其中x和y是两个水壶的容量。例如，如果a为正，则表示往容量为x的水壶中加a次水；如果a为负，则表示从容量为x的水壶中倒出|a|次水。因此，只有当目标水量是x和y的最大公约数的倍数时，我们才能通过这样的加水或倒水操作达到目标水量。

如果目标水量大于两个水壶的总容量之和，那么无论如何操作都无法达到这个目标。因为两个水壶的容量加起来都无法达到目标水量，即使两个水壶都装满水也无法满足要求的水量。这是一个基本的容量限制问题，容量的总和设置了能够达到的最大水量的上限。

假设有两个水壶，容量分别为3升和5升，目标水量为1升。这两个水壶的最大公约数为1。根据贝祖定理，我们可以找到整数a和b，使得3a + 5b = 1。一个可能的操作步骤如下： 1. 先将5升水壶装满，然后将其水倒入3升水壶，直到3升水壶满。此时5升水壶中剩下2升。 2. 将3升水壶中的水倒掉，再将5升水壶中的2升水倒入3升水壶。 3. 再次将5升水壶装满，然后继续向3升水壶中倒水，直到3升水壶满。此时5升水壶中剩下1升水，即达到了目标水量。这个过程中，我们通过反复填充和倒空水壶，最终利用水壶的容量关系达到目标水量。