0365. Water and Jug Problem

题目信息

题号:

0365

难度:

Medium

主题:

两个水壶、允许操作、精确水量、可达性

原题:

LeetCode 0365

重点:

只能装满、倒空或相互倾倒、目标是两壶总水量恰好等于目标、倾倒持续到一方空或另一方满

题目重述

有两个容量分别为 x 和 y 升的水壶,水源不限。每一步只能执行以下操作之一:把任意一个水壶装满;把任意一个水壶倒空;把一个水壶中的水倒入另一个,直到源水壶为空或目标水壶装满。

判断是否能够经过若干操作,使两个水壶中保存的水量总和恰好等于 target。三个容量均位于 [0, 10^6];当 target=0 时无需取水即可满足条件。水壶没有刻度,不能直接量取任意中间水量。

自建示例

目标可由合法倾倒过程得到:

输入:x = 4,y = 9,target = 7
输出:true
解释:可以反复装满、倾倒和倒空,使其中一个水壶最终留下 7 升;此时两壶总水量恰好为 7。

容量足够但无法精确量出:

输入:x = 2,y = 6,target = 5
输出:false
解释:允许操作只能产生偶数升的总量,无法得到恰好 5 升。

可达总量由最大公约数决定

装满、倒空和相互倾倒的操作可以构造出容量 x 与 y 的整数线性组合,因此所有可精确量出的正整数都必须是 gcd(x, y) 的倍数;反过来,欧几里得算法给出的贝祖等式说明这些倍数可以通过反复倒水实现。目标还必须不超过两壶总容量,否则即使同时装满也不够。

因此只需检查 target <= x + y 且 target 能被 gcd(x, y) 整除。目标为 0 时两壶都空即可满足;两个容量都为 0 且目标为正时,容量上界检查会直接失败。

C++ 实现

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)。