LeetCode 3. 水壶问题

摘要：
数学知识贝祖定理应用。

题目：

有两个容量分别为 $x$ 升 和 $y$ 升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 $z$ 升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 $z$ 升 水。

你允许：

• 装满任意一个水壶
• 清空任意一个水壶
• 从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1:

输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False

---

贝祖定理

关键在于划分成功条件。
题干默认 $z >= 0$，首先当 $z = 0$ 时，$x$ 和 $y$ 取任意值，一定成功。
当 $z > 0$ 时：

• 当 $x + y < z$ 时，即使两盏杯子装满水，依然不可能成功。
• 当 $x + y = z$ 时，$x$, $y$, $z$ 取任意值，一定成功。
• 当 $x + y > z$ 时，不一定。问题的核心在此，用贝祖定理判定成功条件。
  由贝祖定理可知，对任何整数 $x$、$y$ 和它们的最大公约数 $gcd(x, y)$，对于它们的的任意整数倍数 $a$, $b$, $c$，都有
  $ax + by = c \times gcd(x, y)$ 恒成立。
  由题干给出的几种操作，要完成目标，一定有 $ax + by = z$。
  和贝祖定理完美锲合，那么，只要 $z mod (gcd(x, y)) = 0$ 为真，则一定成功。

• Java

class Solution {
    //贝祖定理
    public static boolean canMeasureWater(int x, int y, int z) {
        //默认z >= 0
        if (z == 0)
            return true;
        //z>0
        if (x +y <z)
            return false;
        else if (x + y == z)
            return true;
        else
            //only x!=0,y!=0; x!=0,y==0; x==0,y!=0
            return z % gcd(x, y) == 0;
    }
    public static int gcd(int x, int y) {
        while (y != 0) { //辗转相除法
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }
}

原题链接： LeetCode 3. 水壶问题