0365. Water and Jug Problem =========================== 题目信息 -------- :题号: 0365 :难度: Medium :主题: 两个水壶、允许操作、精确水量、可达性 :原题: `LeetCode 0365 `_ :重点: 只能装满、倒空或相互倾倒、目标是两壶总水量恰好等于目标、倾倒持续到一方空或另一方满 题目重述 -------- 有两个容量分别为 ``x`` 和 ``y`` 升的水壶,水源不限。每一步只能执行以下操作之一:把任意一个水壶装满;把任意一个水壶倒空;把一个水壶中的水倒入另一个,直到源水壶为空或目标水壶装满。 判断是否能够经过若干操作,使两个水壶中保存的水量总和恰好等于 ``target``。三个容量均位于 ``[0, 10^6]``;当 ``target=0`` 时无需取水即可满足条件。水壶没有刻度,不能直接量取任意中间水量。 自建示例 -------- 目标可由合法倾倒过程得到: .. code-block:: text 输入:x = 4,y = 9,target = 7 输出:true 解释:可以反复装满、倾倒和倒空,使其中一个水壶最终留下 7 升;此时两壶总水量恰好为 7。 容量足够但无法精确量出: .. code-block:: text 输入:x = 2,y = 6,target = 5 输出:false 解释:允许操作只能产生偶数升的总量,无法得到恰好 5 升。 可达总量由最大公约数决定 -------------------------- 装满、倒空和相互倾倒的操作可以构造出容量 ``x`` 与 ``y`` 的整数线性组合,因此所有可精确量出的正整数都必须是 ``gcd(x, y)`` 的倍数;反过来,欧几里得算法给出的贝祖等式说明这些倍数可以通过反复倒水实现。目标还必须不超过两壶总容量,否则即使同时装满也不够。 因此只需检查 ``target <= x + y`` 且 ``target`` 能被 ``gcd(x, y)`` 整除。目标为 0 时两壶都空即可满足;两个容量都为 0 且目标为正时,容量上界检查会直接失败。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool canMeasureWater(int x, int y, int target) { if (target == 0) return true; if (target > x + y) return false; int divisor = std::gcd(x, y); return divisor != 0 && target % divisor == 0; } }; 代码分析 -------- 容量上限排除水量不足的情况,最大公约数条件排除刻度操作无法产生的余数;两者同时满足时由经典两壶量水过程可实现目标。算法只做一次最大公约数计算,时间复杂度为 ``O(log(min(x,y)))``,额外空间为 ``O(1)``。