---

0365. 水壶问题

• 标签：深度优先搜索、广度优先搜索、数学
• 难度：中等

题目链接

• 0365. 水壶问题 - 力扣

题目大意

描述：

有两个水壶，容量分别为 $x$ 和 $y$ 升。水的供应是无限的。

要求：

确定是否有可能使用这两个壶准确得到 $target$ 升。

你可以：

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

说明：

• $1 \le x, y, target \le 10^{3}$。

示例：

• 示例 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)。

• 示例 2：

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

解题思路

思路 1：数学方法（贝祖定理）

核心思想：这是一个经典的数学问题，可以使用贝祖定理（Bézout's identity）来解决。根据贝祖定理，对于两个整数 $x$ 和 $y$，存在整数 $a$ 和 $b$ 使得 $ax + by = \gcd(x, y)$。因此，我们能够测量的水量必须是 $x$ 和 $y$ 的最大公约数的倍数。

数学原理：

• 贝祖定理：对于整数 $x$ 和 $y$，存在整数 $a$ 和 $b$ 使得 $ax + by = \gcd(x, y)$。
• 在操作过程中，我们只能通过装满、倒空、倒水等操作来改变水壶中的水量。
• 这些操作本质上是在做 $x$ 和 $y$ 的线性组合。
• 因此，能够测量的水量必须是 $\gcd(x, y)$ 的倍数。

算法步骤：

1. 特殊情况处理：如果 $target = 0$，直接返回 $true$（两个水壶都为空）。
2. 容量检查：如果 $target > x + y$，返回 $false$（总容量不足）。
3. 贝祖定理判断：检查 $target$ 是否能被 $\gcd(x, y)$ 整除。
4. 返回结果：如果 $target \bmod \gcd(x, y) = 0$，则返回 $true$，否则返回 $false$。

思路 1：代码

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        # 特殊情况：目标为 0，两个水壶都为空即可
        if target == 0:
            return True
        
        # 特殊情况：目标大于两个水壶的总容量
        if target > x + y:
            return False
        
        # 使用贝祖定理：能够测量的水量必须是 gcd(x, y) 的倍数
        def gcd(a: int, b: int) -> int:
            """计算最大公约数"""
            while b:
                a, b = b, a % b
            return a
        
        # 计算 x 和 y 的最大公约数
        g = gcd(x, y)
        
        # 检查 target 是否能被 gcd(x, y) 整除
        return target % g == 0

思路 1：复杂度分析

• 时间复杂度：$O(\log(\min(x, y)))$，计算最大公约数的时间复杂度为 $O(\log(\min(x, y)))$，其中 $x$ 和 $y$ 是水壶的容量。
• 空间复杂度：$O(1)$，只使用了常数额外空间，没有使用额外的数据结构。