0365. 水壶问题【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 裴蕴定理
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

有两个水壶，容量分别为 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^3

2. 🎯 s.1 - 裴蕴定理

c

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
    if (jug1Capacity + jug2Capacity < targetCapacity) return false;
    return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
}

js

/**
 * @param {number} jug1Capacity
 * @param {number} jug2Capacity
 * @param {number} targetCapacity
 * @return {boolean}
 */
var canMeasureWater = function (jug1Capacity, jug2Capacity, targetCapacity) {
  if (jug1Capacity + jug2Capacity < targetCapacity) return false
  const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b))
  return targetCapacity % gcd(jug1Capacity, jug2Capacity) === 0
}

py

class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
        if jug1Capacity + jug2Capacity < targetCapacity:
            return False
        return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0

• 时间复杂度：$O(\log (min(x,y)))$，GCD 计算
• 空间复杂度：$O(\log (min(x,y)))$，递归栈

算法思路：

• 裴蕴定理：$ax+by=z$ 有解当且仅当 $z$ 是 $gcd(x,y)$ 的倍数
• 判断 targetCapacity % gcd(jug1, jug2) === 0 且总容量足够

3. 🔗 引用

• Youtube - Die hard 3 : Jugs Problem