LeetCode 365. 水壶问题
字数 2212 2025-12-05 09:33:49

LeetCode 365. 水壶问题

题目描述
有两个容量分别为 x 升和 y 升的水壶，以及无限量的水供应。你可以进行以下操作任意次：

  1. 装满任意一个水壶。
  2. 倒空任意一个水壶。
  3. 从一个水壶向另一个水壶倒水，直到倒空出水壶或装满接水壶。
    问是否可以通过这些操作，使得恰好得到 z 升水装在其中一个或两个水壶中？

题目会给出三个整数 x, y, z (x, y, z ≥ 0)，要求返回布尔值表示是否能得到恰好 z 升水。

解题过程
这个问题可以抽象为状态搜索问题，也可以用数学方法（数论）直接求解。我会从直观思路开始，逐步深入解释。

1. 问题理解与初步思路
每个时刻，两个水壶的水量构成一个状态 (a, b)，其中 0 ≤ a ≤ x, 0 ≤ b ≤ y。
初始状态: (0, 0)
目标状态: 存在某个状态使得 a == z 或 b == z 或 a + b == z。
操作可以改变状态，问能否从 (0,0) 到达目标状态。

这很像一个图搜索问题，每个状态是图的一个节点，操作是边，我们可以用 BFS 搜索所有可能状态，看能否达到目标。
BFS 的可行性：状态总数最多 (x+1)*(y+1)，在 x, y 较小时可行（题目约束 x, y ≤ 10^4，BFS 可能稍慢但可行）。

2. 状态转移（操作）
从当前状态 (a, b) 可以转移到：

  1. 装满 A: (x, b)
  2. 装满 B: (a, y)
  3. 倒空 A: (0, b)
  4. 倒空 B: (a, 0)
  5. A 倒向 B: 设倒出量为 pour = min(a, y - b)，新状态 (a - pour, b + pour)
  6. B 倒向 A: 设倒出量为 pour = min(b, x - a)，新状态 (a + pour, b - pour)

每次操作后得到一个新状态，如果未访问过，就加入队列。

3. 搜索实现要点

  • 用 visited 集合记录访问过的 (a,b) 对，避免重复。
  • 队列初始为 [(0,0)]，每次取出状态，尝试所有 6 种操作生成新状态，检查是否达到目标。
  • 目标条件：a == z 或 b == z 或 a + b == z。
  • 如果队列空还未找到，则返回 False。

示例：x=3, y=5, z=4
BFS 过程：
(0,0) -> (3,0) -> (0,3) -> (3,3) -> (1,5) -> (1,0) -> (0,1) -> (3,1) -> (0,4) ✅ 找到 b=4。
所以返回 True。

4. 数学优化（贝祖定理）
实际上，不需要真的 BFS 就能判断。
注意：每次操作只会让总水量增加 x（装满 A），增加 y（装满 B），减少 x（倒空 A），减少 y（倒空 B），或者在倒水时总水量不变。
所以，任意时刻两个水壶的总水量一定是 x 和 y 的线性组合，即 a+b = mx + ny，其中 m,n 是整数（可为负，表示倒空）。
而 z 要能被得到，必须满足：存在某个状态使得其中一个壶有 z 升水，或者两个壶总水量为 z。但可以证明，如果我们能凑出任意一个壶的水量为 z，那么总水量条件也隐含了。更关键的是，可得到的水量总是 x 和 y 的最大公约数（gcd）的倍数。

为什么？
因为每次操作改变单个壶的水量时，总是整壶地倒满或倒空，或者从一个壶倒到另一个壶（倒出量是整数的水量差值）。从数论角度，最终能得到的水量 c 必须满足 c ≤ x+y，且 c 是 gcd(x,y) 的倍数。
同时，还有一个条件：c 不能大于 x+y（因为最多两个壶装满）。

结论：如果 z 能被 gcd(x, y) 整除，且 z ≤ x + y，则可以得到 z 升水。
特殊情况：如果 z=0，一定可以（初始状态就是）。

5. 举例验证数学结论
例1：x=3, y=5, z=4
gcd(3,5)=1，4%1=0 且 4 ≤ 3+5 → True。
例2：x=2, y=6, z=5
gcd=2，5%2=1 → False。确实无法得到 5 升，因为能得到的水量只能是 0,2,4,6,8（但8>2+6不行，所以实际只能是0,2,4,6）。
例3：x=1, y=2, z=3
gcd=1，3%1=0 但 3>1+2=3？3=3 时，需要两个壶总水量为3，但这里 3=1+2 正好是两个壶都满，所以是可能的，条件中 z ≤ x+y 即可，等号成立时是可行的（两个壶都装满）。

6. 最终算法

  1. 如果 z == 0: 返回 True。
  2. 如果 z > x + y: 返回 False（不可能超过两壶总容量）。
  3. 计算 g = gcd(x, y)。
  4. 返回 z % g == 0。

时间复杂度 O(log(min(x,y))) 用于计算 gcd，空间 O(1)。

7. 思考扩展
为什么 BFS 可行但数学解法更优？
因为 BFS 在最坏情况下要探索 O(xy) 个状态，在 x,y 很大时（如 10^4）可能状态过多，而数学解法是常数时间。
数学解法的证明核心是贝祖定理（裴蜀定理）：对于整数 a,b，存在整数 m,n 使得 ma + nb = gcd(a,b)，且能得到的水量一定是 gcd 的倍数，同时任何不超过 a+b 的 gcd 倍数都能被得到（通过倒水操作构造）。

这样我们就得到了高效且准确的解法。

LeetCode 365. 水壶问题 题目描述 有两个容量分别为 x 升和 y 升的水壶，以及无限量的水供应。你可以进行以下操作任意次： 装满任意一个水壶。 倒空任意一个水壶。 从一个水壶向另一个水壶倒水，直到倒空出水壶或装满接水壶。 问是否可以通过这些操作，使得恰好得到 z 升水装在其中一个或两个水壶中？ 题目会给出三个整数 x, y, z (x, y, z ≥ 0)，要求返回布尔值表示是否能得到恰好 z 升水。 解题过程 这个问题可以抽象为状态搜索问题，也可以用数学方法（数论）直接求解。我会从直观思路开始，逐步深入解释。 1. 问题理解与初步思路 每个时刻，两个水壶的水量构成一个状态 (a, b)，其中 0 ≤ a ≤ x, 0 ≤ b ≤ y。 初始状态: (0, 0) 目标状态: 存在某个状态使得 a == z 或 b == z 或 a + b == z。 操作可以改变状态，问能否从 (0,0) 到达目标状态。 这很像一个图搜索问题，每个状态是图的一个节点，操作是边，我们可以用 BFS 搜索所有可能状态，看能否达到目标。 BFS 的可行性：状态总数最多 (x+1)* (y+1)，在 x, y 较小时可行（题目约束 x, y ≤ 10^4，BFS 可能稍慢但可行）。 2. 状态转移（操作） 从当前状态 (a, b) 可以转移到： 装满 A: (x, b) 装满 B: (a, y) 倒空 A: (0, b) 倒空 B: (a, 0) A 倒向 B: 设倒出量为 pour = min(a, y - b)，新状态 (a - pour, b + pour) B 倒向 A: 设倒出量为 pour = min(b, x - a)，新状态 (a + pour, b - pour) 每次操作后得到一个新状态，如果未访问过，就加入队列。 3. 搜索实现要点 用 visited 集合记录访问过的 (a,b) 对，避免重复。 队列初始为 [ (0,0) ]，每次取出状态，尝试所有 6 种操作生成新状态，检查是否达到目标。 目标条件：a == z 或 b == z 或 a + b == z。 如果队列空还未找到，则返回 False。 示例：x=3, y=5, z=4 BFS 过程： (0,0) -> (3,0) -> (0,3) -> (3,3) -> (1,5) -> (1,0) -> (0,1) -> (3,1) -> (0,4) ✅ 找到 b=4。 所以返回 True。 4. 数学优化（贝祖定理） 实际上，不需要真的 BFS 就能判断。 注意：每次操作只会让总水量增加 x（装满 A），增加 y（装满 B），减少 x（倒空 A），减少 y（倒空 B），或者在倒水时总水量不变。 所以， 任意时刻两个水壶的总水量一定是 x 和 y 的线性组合 ，即 a+b = m x + n y，其中 m,n 是整数（可为负，表示倒空）。 而 z 要能被得到，必须满足：存在某个状态使得其中一个壶有 z 升水，或者两个壶总水量为 z。但可以证明，如果我们能凑出任意一个壶的水量为 z，那么总水量条件也隐含了。更关键的是， 可得到的水量总是 x 和 y 的最大公约数（gcd）的倍数 。 为什么？ 因为每次操作改变单个壶的水量时，总是整壶地倒满或倒空，或者从一个壶倒到另一个壶（倒出量是整数的水量差值）。从数论角度，最终能得到的水量 c 必须满足 c ≤ x+y，且 c 是 gcd(x,y) 的倍数。 同时，还有一个条件：c 不能大于 x+y（因为最多两个壶装满）。 结论 ：如果 z 能被 gcd(x, y) 整除，且 z ≤ x + y，则可以得到 z 升水。 特殊情况：如果 z=0，一定可以（初始状态就是）。 5. 举例验证数学结论 例1：x=3, y=5, z=4 gcd(3,5)=1，4%1=0 且 4 ≤ 3+5 → True。 例2：x=2, y=6, z=5 gcd=2，5%2=1 → False。确实无法得到 5 升，因为能得到的水量只能是 0,2,4,6,8（但8>2+6不行，所以实际只能是0,2,4,6）。 例3：x=1, y=2, z=3 gcd=1，3%1=0 但 3>1+2=3？3=3 时，需要两个壶总水量为3，但这里 3=1+2 正好是两个壶都满，所以是可能的，条件中 z ≤ x+y 即可，等号成立时是可行的（两个壶都装满）。 6. 最终算法 如果 z == 0: 返回 True。 如果 z > x + y: 返回 False（不可能超过两壶总容量）。 计算 g = gcd(x, y)。 返回 z % g == 0。 时间复杂度 O(log(min(x,y))) 用于计算 gcd，空间 O(1)。 7. 思考扩展 为什么 BFS 可行但数学解法更优？ 因为 BFS 在最坏情况下要探索 O(xy) 个状态，在 x,y 很大时（如 10^4）可能状态过多，而数学解法是常数时间。 数学解法的证明核心是贝祖定理（裴蜀定理）：对于整数 a,b，存在整数 m,n 使得 m a + n b = gcd(a,b)，且能得到的水量一定是 gcd 的倍数，同时任何不超过 a+b 的 gcd 倍数都能被得到（通过倒水操作构造）。 这样我们就得到了高效且准确的解法。