LeetCode 365. 水壶问题

2024-10-04 HGNULB 约 5 分钟

文章信息 8 个分类 7 个标签

分类

题目描述

✅ 365. 水壶问题

题意分析

有两个没有刻度的水壶，容量分别是 $x$ 和 $y$。允许的操作只有三类：把某个壶装满、把某个壶倒空、把一个壶里的水往另一个壶里倒（倒到源壶空了或目标壶满了为止）。问最终能否让两个壶里的水量之和恰好等于 $z$。

注意题目问的是「两壶中水的总量」，而不是「某一个壶里恰好有 $z$ 升」。这个区别很重要：$z$ 可以由两个壶各装一部分凑出来。

约束信号：三个数的范围都是 $[1, 10^6]$。上界不大，但状态空间是二维的，朴素搜索的状态数是 $x \cdot y$ 量级，最坏可达 $10^{12}$，明显超时——这在提示答案应当是一个可以直接算出来的判定条件，而不是搜索。

边界情况：$z = 0$ 时什么都不做即可，答案为真；$z$ 超过 $x + y$ 时两个壶全装满也不够，答案为假；$z$ 恰好等于 $x$、$y$ 或 $x + y$ 时显然可行。

解法：贝祖定理 + 最大公约数

核心思路

把两壶当前水量 $(a,b)$ 作为状态做 BFS 虽然直观，但搜索规模会随容量数值增长；本题只问能否到达，没必要枚举状态，应寻找可达水量的数论条件。

令 $g=\gcd(x,y)$。必要性可以用不变量严格说明：初始水量都是 $g$ 的倍数；装满会把水量设为 $x$ 或 $y$，倒空会设为 0；从第一壶向第二壶倒水时，转移量为 $\min(a,y-b)$，其中 $a$ 与 $y-b$ 都是 $g$ 的倍数，所以转移后两边仍是 $g$ 的倍数。由归纳可知，任意可达状态的总水量都必须是 $g$ 的倍数。

充分性也能构造。假设 $0<x\le y$，反复执行“装满 $x$ 壶并倒入 $y$ 壶；$y$ 壶满时将其倒空，再继续倒”，大壶中的水量会按 $kx \bmod y$ 变化。由于 $x/g$ 与 $y/g$ 互质，这些余数会遍历 $[0,y)$ 内所有 $g$ 的倍数，因此任意不超过 $y$ 的目标倍数都能量出。若 $y<z\le x+y$，先在大壶中量出 $z-x$，再装满小壶即可得到总量 $z$。

因而答案恰好满足：$z\le x+y$ 且 $g$ 能整除 $z$。$z=0$ 时不做操作即可；上界检查与整除检查缺一不可。

解题步骤

若 targetCapacity == 0，直接返回 true。

若目标大于两壶容量之和，达到物理上限也不够，返回 false。

用辗转相除法求两壶容量的最大公约数 $g$。

判断目标是否能被 $g$ 整除；能整除说明可构造，否则不可达。

例如 $x=3,y=5,z=4$，上限检查通过且 $\gcd(3,5)=1$。按“小壶反复倒入大壶”的过程，可经过 $(0,3)$、$(1,5)$、$(0,1)$，最终到达 $(0,4)$。反例 $x=2,y=6,z=5$ 虽未超过总容量，但最大公约数为 2，奇数目标不可能到达。

代码实现

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)$。迭代求最大公约数只使用常数个变量。

关键点总结

可达状态保持“每个壶的水量都是最大公约数的倍数”这一不变量。

裴蜀定理给出整除条件，欧几里得式倒水过程给出可执行的充分性构造。

target <= x + y 是物理上限，不能被最大公约数判定替代。

面试不能只背 target % gcd == 0，应能分别解释必要性不变量和充分性构造。

易错点总结

只检查整除而漏掉容量上限：x=1,y=2,z=100 能被最大公约数整除，但两壶最多装 3。

只检查容量上限而漏掉整除：x=2,y=6,z=5 不超上限，却无法用偶数容量量出奇数。

把目标误解为“某一个壶中有 $z$”：x=3,y=5,z=8 可由两壶装满达到。

漏掉 z=0 或未防止最大公约数为 0，可能在零容量边界上发生取模除零。

只引用裴蜀定理却不给操作构造，证明不完整；倒水循环与辗转相除对应，才说明整除条件确实充分。

相似题目

题目	难度	考察点
1071. 字符串的最大公因子	简单	把最大公约数的结论迁移到字符串长度上
1010. 总持续时间可被 60 整除的歌曲	中等	同余分类计数，重点在余数配对
752. 打开转盘锁	中等	状态空间可枚举时，广度优先搜索才是正解
878. 第 N 个神奇数字	困难	最小公倍数配合容斥，再用二分定位第 N 个数