1 题目

https://leetcode-cn.com/problems/water-and-jug-problem/

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

装满任意一个水壶

清空任意一个水壶

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

输入: x = 3, y = 5, z = 4

输出: True

示例 2:

输入: x = 2, y = 6, z = 5

输出: False

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/water-and-jug-problem

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 题目解析与数学解法

题目没说清楚，看了解答才知道，我们把题目做一个等价。

题目想表达的是这样：有3个壶编号，容量如下表。

| 水壶编号| 水壶1 | 水壶2 | 水壶3 |

|:--------:|:--------:| :----------:| :----------:|

| 容量 | x| y |x+y |

最开始水壶3全是水，是满的。不管我们怎么倒腾，最终要得到z升水在水壶3（目标）。

因此必须有 z <= x+y 了。

一个数学解答是，找到2个整数a和b，让其满足 ax+by=z 。（整数=正整数+0+负整数）

贝祖定理：ax+by=z 有解当且仅当 z 是 x,y 的最大公约数的倍数。

所以判断有没有这样的2个整数a和b，就去判断x+y最大公约数的倍数是不是可以等于z。（3和5的最大公约数是1）

python

python
import math
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x + y < z:  # 一共都没那么多水
            return False
        if x == 0 or y == 0:  #
            return z == 0 or x + y == z  # z是0显然True  x和y有一个是0就必须x+y=z才是True
        return (z % math.gcd(x, y)) == 0
print(Solution().canMeasureWater(3, 5, 4))

3 DFS

python
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        stack = [(0, 0)]
        self.seen = set()
        while stack:
            remain_x, remain_y = stack.pop()
            if remain_x == z or remain_y == z or remain_x + remain_y == z:
                return True
            if (remain_x, remain_y) in self.seen:
                continue
            self.seen.add((remain_x, remain_y))
            # 把 X 壶灌满。
            stack.append((x, remain_y))
            # 把 Y 壶灌满。
            stack.append((remain_x, y))
            # 把 X 壶倒空。
            stack.append((0, remain_y))
            # 把 Y 壶倒空。
            stack.append((remain_x, 0))
            # 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
            stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))
            # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
            stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))
        return False
print(Solution().canMeasureWater(3, 5, 4))