LeetCode 365题 “水壶问题”（Water and Jug Problem）是一个经典的数学问题，可以用深度优先搜索（DFS）、广度优先搜索（BFS）或者数学方法（贝祖定理）来解决。下面我会详细解释这个问题的背景、解题思路和代码实现。
问题背景
你有两个水壶，容量分别为 x 升和 y 升。你还有无限多的水。你需要判断是否能够通过以下操作得到恰好 z 升的水：
- 装满任意一个水壶。
- 清空任意一个水壶。
- 将一个水壶中的水倒入另一个水壶，直到一个水壶空或者另一个水壶满。
解题思路
方法一：深度优先搜索（DFS）
我们可以用DFS来遍历所有可能的状态。每个状态可以用 (当前x壶中的水量, 当前y壶中的水量) 来表示。我们从 (0, 0) 开始，通过上述操作进行状态转移，看是否能达到 (z, 0) 或 (0, z)。
方法二：广度优先搜索（BFS）
BFS也是一种常见的搜索方法，适用于这种需要遍历所有可能状态的问题。我们用一个队列来存储所有可能的状态，并逐层扩展。
方法三：数学方法（贝祖定理）
贝祖定理告诉我们，对于任意的整数 a 和 b，ax + by = z 有解当且仅当 gcd(a, b) | z（即 z 是 a 和 b 的最大公约数的倍数）。在这个问题中，a 和 b 分别是 x 和 y，所以我们只需要判断 z 是否是 gcd(x, y) 的倍数。
代码实现
这里我们以数学方法为例，因为它最为简洁高效。
from math import gcd
def canMeasureWater(x, y, z): if x + y < z: return False if x == 0 or y == 0: return z == 0 or x + y == z return z % gcd(x, y) == 0
示例
x, y, z = 3, 5, 4 print(canMeasureWater(x, y, z)) # 输出: True
详细解释
-
边界条件：
- 如果
x + y < z，显然不可能得到z升水，直接返回False。 - 如果
x或y为0，那么只能通过另一个水壶来得到水。此时只有z为0或者z等于另一个水壶的容量时才可能成功。
- 如果
-
贝祖定理应用：
- 计算
x和y的最大公约数gcd(x, y)。 - 判断
z是否是gcd(x, y)的倍数，如果是则返回True，否则返回False。
- 计算
复杂度分析
- 时间复杂度：O(log(min(x, y)))，因为计算最大公约数的时间复杂度是 O(log(min(x, y)))。
- 空间复杂度：O(1)，只需要常数级别的额外空间。
通过上述方法，我们可以高效地解决这个水壶问题。如果你有更多问题或者需要其他方法的实现，欢迎继续提问！
发表回复