LeetCode 365. 水壶问题
题目描述
题意分析
两个水壶容量分别为
x、y，初始都为空。每次只能装满一个壶、倒空一个壶，或者把一个壶的水倒入另一个壶，直到倒水壶空或接水壶满，不能凭空在任意刻度停下。判断能否使两壶中的总水量等于目标
target，目标不必全部放在同一个壶中。只需回答是否可达，不需要输出具体操作，因此可以从水量的数学约束入手。
解法：贝祖定理 + 最大公约数
核心思路
[!blue]
设 $g = \gcd(x,y)$。最终判定条件是：目标不超过总容量，并且能被
g整除。前者是容积限制；后者既是必要条件，也能通过实际倒水过程证明充分。为什么目标必须是
g的倍数？初始水量为 $0$，两个容量也是g的倍数。装满或倒空后，壶中水量仍是g的倍数；相互倒水时，转移量是「倒水壶现有水量」与「接水壶剩余容量」的较小者，两者都是g的倍数，所以转移后仍保持这一性质。于是每个壶及两壶总水量都只能是g的倍数。贝祖定理说明，
x、y的整数线性组合恰好覆盖g的所有倍数。但线性组合本身没有考虑壶的容量限制，还需要说明这些水量怎样由允许的操作得到。先证明一个壶内的可达水量。固定从容量为
x的壶向容量为y的壶倒水：x壶空了就装满，y壶满了就倒空，继续倒，直到x壶再次为空。每装入一整壶x，接水壶累计增加x，期间只会按整壶y倒掉。因此装满x壶共k次后，在倒水壶为空、接水壶未满的时刻，接水壶剩余量就是 $kx \bmod y$。因为 $x/g$ 与 $y/g$ 互质，这些余数会遍历 $0,g,2g,\ldots,y-g$：若两个轮次出现相同余数，它们的轮次差乘
x必须被y整除，所以最早在相差 $y/g$ 轮时才会重复。再加上直接装满得到y，便能在y壶中得到不超过其容量的任意g的倍数，且另一壶为空。交换两个壶的角色，同样能在x壶中做到。再覆盖两壶总量。令较大容量为
big、较小容量为small。若target <= big，直接在大壶中量出目标即可；若big < target <= big + small，先在小壶中量出target - big，再把空的大壶装满。差值仍是g的倍数且不超过small，所以上述构造可行。这就证明了整除条件与容量上限一起足够。实现时无需模拟这些操作，只用辗转相除法求
g。将(a,b)替换为(b,a % b)不会改变共同因数；当b为 $0$ 时，a就是最大公约数。
解题步骤
- 若
targetCapacity == 0，直接返回true。- 若目标大于两壶容量之和，达到物理上限也不够，返回
false。- 用辗转相除法求两壶容量的最大公约数 $g$。
- 判断目标是否能被 $g$ 整除；能整除说明可构造，否则不可达。
代码实现
class Solution {
public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
if (targetCapacity == 0) {
return true;
}
// 目标不能超过两壶总容量，整除条件不能代替这个物理上限。
if (jug1Capacity + jug2Capacity < targetCapacity) {
return false;
}
// 可量出的水量必须是两个容量最大公约数的倍数。
int gcd = gcd(jug1Capacity, jug2Capacity);
return gcd != 0 && targetCapacity % gcd == 0;
}
private int gcd(int a, int b) {
// 将两数替换为除数和余数，最大公约数保持不变。
while (b != 0) {
int remain = a % b;
a = b;
b = remain;
}
return Math.abs(a);
}
}
func canMeasureWater(jug1Capacity int, jug2Capacity int, targetCapacity int) bool {
if targetCapacity == 0 {
return true
}
// 目标不能超过两壶总容量，整除条件不能代替这个物理上限。
if jug1Capacity+jug2Capacity < targetCapacity {
return false
}
// 可量出的水量必须是两个容量最大公约数的倍数。
gcdValue := gcdWater(jug1Capacity, jug2Capacity)
return gcdValue != 0 && targetCapacity%gcdValue == 0
}
func gcdWater(a int, b int) int {
// 将两数替换为除数和余数，最大公约数保持不变。
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}
复杂度分析
- 时间复杂度：$O(\log \min(x,y))$。只需用辗转相除法求一次最大公约数。
- 空间复杂度：$O(1)$。迭代求最大公约数只使用常数个变量。
关键点总结
[!green]
- 可达状态保持“每个壶的水量都是最大公约数的倍数”这一不变量，因此整除条件不可少。
- 反复装满、倒入和倒空会产生模容量的余数循环，覆盖容量内所有最大公约数的倍数。
target <= x + y是物理上限，不能被最大公约数判定替代。
易错点总结
[!yellow]
- 只检查整除而漏掉容量上限：数学上可以表示的水量，也可能超过两个壶能容纳的总量。
- 只检查容量上限而漏掉整除：操作始终保持水量是最大公约数的倍数，不能量出其他余数。
- 把目标误解为必须放入某一个壶：判断上限应使用
x + y，不能使用max(x, y)。- 直接把贝祖等式中的系数当成可执行操作次数：正负系数没有体现中间容量约束，需要倒水构造来说明充分性。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 154. 最大公约数 | 简单 | 两壶容量的整数线性组合受最大公约数约束，是本题数论判定的基础。 |
| 752. 打开转盘锁 | 中等 | 也可把两个水量作为状态做BFS；与转盘锁相同，需要去重已访问状态避免循环。 |