365. 水壶问题
题目描述
有两个水壶，容量分别是 x 升和 y 升，水源不限量。一开始两个壶都是空的。
每一步可以做下面三件事之一：把某个壶装满；把某个壶倒空；把一个壶里的水倒进另一个壶，直到接水的壶满了或者倒水的壶空了为止。
判断能否经过若干步，使两个壶里的水加起来恰好是 target 升。能则返回 true，否则返回 false。
示例 1
输入：x = 3, y = 5, target = 4 输出：true
解释：反复用 5 升壶装水、向 3 升壶倒水，最后可以让 5 升壶里剩下 4 升。
数据范围
1 <= x, y, target <= 10^3
解题思路
观察每次操作后总水量的变化：只会增加或减少 x 或 y（倒水不改变总量）。所以能得到的总量都形如 a·x + b·y。由裴蜀定理，这类数恰好是 gcd(x, y) 的倍数。再加上总量不能超过 x + y，答案就是 target ≤ x + y 且 target 是 gcd(x, y) 的倍数。gcd 用辗转相除法求。
为什么正确
辗转相除时 gcd(a, b) = gcd(b, a % b) 始终不变，b 变为 0 时 a 就是最大公约数。
复杂度分析
时间 O(log min(x, y))，空间 O(1)。
易错点
别忘了 target > x + y 的情况：即使是 gcd 的倍数，两个壶也装不下。用 BFS 搜索状态也能做，但状态数可达 x·y，大数据会超时。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def canMeasureWater(self, x: int, y: int, target: int) -> bool:
if target > x + y:
return False
a, b = x, y
while b:
a, b = b, a % b
return target % a == 0class Solution {
public boolean canMeasureWater(int x, int y, int target) {
if (target > x + y) {
return false;
}
int a = x, b = y;
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return target % a == 0;
}
}class Solution {
public:
bool canMeasureWater(int x, int y, int target) {
if (target > x + y) {
return false;
}
int a = x, b = y;
while (b) {
int t = a % b;
a = b;
b = t;
}
return target % a == 0;
}
};func canMeasureWater(x int, y int, target int) bool {
if target > x+y {
return false
}
a, b := x, y
for b != 0 {
a, b = b, a%b
}
return target%a == 0
}var canMeasureWater = function(x, y, target) {
if (target > x + y) {
return false;
}
let a = x, b = y;
while (b) {
[a, b] = [b, a % b];
}
return target % a === 0;
};function canMeasureWater(x: number, y: number, target: number): boolean {
if (target > x + y) {
return false;
}
let a = x, b = y;
while (b) {
[a, b] = [b, a % b];
}
return target % a === 0;
}