每日一题：水壶问题

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

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

你允许：

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

实例1
输入: x = 3, y = 5, z = 4
输出: True

实例2
输入: x = 2, y = 6, z = 5
输出: False

方法一：深度优先搜索

此问题的状态可以有两个数字决定，X水壶中的水量和Y水壶中的水量。
在任意时刻，我们可以并且尽可以采取以下几种操作：

把X壶的水灌进Y壶，直至灌满或倒空；
把Y壶的水灌进X壶，直至灌满或倒空；
把X壶灌满；
把Y壶灌满；
把X壶倒空；
把Y壶倒空；

因此，本题可以采用深度优先搜索解决。搜索中的每一步以remain_x, remain_y作为状态，即表示X壶和Y壶中的水量。在每一步搜索时，依次尝试所有的操作，递归地搜索下去。并且使用一个HashSet来存储所有已经搜索过的remain_x, remain_y状态，保证每个状态至多被搜索一次。
C++代码：

using PII = pair<int, int>;class Solution {
public:bool canMeasureWater(int x, int y, int z) {stack<PII> stk;stk.emplace(0, 0);auto hash_function = [](const PII& o) {return hash<int>()(o.first) ^ hash<int>()(o.second);};unordered_set<PII, decltype(hash_function)> seen(0, hash_function);while (!stk.empty()){if (seen.count(stk.top())) {stk.pop();continue;}seen.emplace(stk.top());auto [remain_x, remain_y] = stk.top();stk.pop();if (remain_x == z || remain_y == z || remain_x + remain_y == z){return true;}// 把X壶灌满；stk.emplace(x, remain_y);// 把Y壶灌满；stk.emplace(remain_x, y);// 把X壶倒空；stk.emplace(0, remain_y);// 把Y壶倒空；stk.emplace(remain_x, 0);// 把X壶的水灌进Y壶，直至灌满或倒空；stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y));// 把Y壶的水灌进X壶，直至灌满或倒空；stk.emplace(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));}return false;}
};

Python代码：
因为Python3的最大递归层数是998，所以这里采用栈来模拟。

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 Trueif (remain_x, remain_y) in self.seen:continueself.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

方法二：贝祖定理

贝祖定理：对于任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（成为贝祖等式）：若a，b是整数，且gcd(a,b) = d, 那么对于任意的整数x,y, ax+by都一定是d的倍数，特别地，一定存在整数x，y，使得ax+by=d成立。

在本题中，我们认为，每次操作只会让桶里的水总量增加x，增加y，减少x，或者减少y。因此，我们可以认为每次操作只会给水的总量带来x或者y的变化量。因此我们的目标可以改写成：找到一对整数a，b使得ax+by=z。

而只要满足z≤x+y，且这样的a，b存在，那么我们的目标就是可以达成的。因为：
若a≥0，b≥0，那么显然可以达成目标。
若a＜0，那么可以进行以下操作：

往y壶倒水；
把y壶的水倒入x壶；
如果y壶不为空，那么x壶肯定是满的，把x壶倒空，然后再把y壶的水倒入x壶。

重复以上操作直至某一步时，x壶进行了a次倒空操作，y壶进行了b次倒水操作。

若 b < 0，方法同上，x与y互换。

贝祖定理告诉我们，ax+by=z有解当且仅当z是x，y的最大公约数的倍数。因此我们只需要找到x，y的最大公约数并判断z是不是它的倍数即可。

class Solution {
public:bool canMeasureWater(int x, int y, int z) {if (x + y < z) return false;if (x == 0 || y == 0) return z == 0 || x + y == z;return z % gcd(x, y) == 0;}
};