leetcode 365题 水壶问题

题目

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?

如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许:
· 装满任意一个水壶
· 清空任意一个水壶
· 从一个水壶向另外一个水壶倒水,直到装满或者倒空

1
2
3
4
示例 1:

输入: x = 3, y = 5, z = 4
输出: True
1
2
3
4
示例 2:

输入: x = 2, y = 6, z = 5
输出: False

解题思路

这个问题最初始的解法就是深度优先搜索,这里不再详细介绍,网上有很多代码和方法
在查看题解的时候发现有一个很巧妙的方法,在这里分享

就是用数学方法来做,因为题目要求,不存在两个桶都不满的情况,所以我们每次的操作都只会对整体水量添加或减少x或者是y的水量
把不满的桶倒掉,如果另一桶是满的,相当于从空直接向另一桶灌满的操作,若果另一桶是空的,则相当于回归到最初的空状态
把不满的桶灌满,如果另一桶是满的,相当于从空直接把两个桶灌满的操作,若果另一桶是空的,则相当于把这个桶灌满的操作

所以我们可以得出这个问题其实就是求解方程

ax+by=zax+by=z

而这个方程有解的条件是z是gcd(x,y)的倍数
所以这个问题就转换成了求最大公因子的问题

代码实现

下述代码中gcd是求最大公因子的代码,当然也可以用c++自带的__gcd()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(x==0||y==0){
if(z==0||x+y==z){
return true;
}
return false;
}
if(z%gcd2(x,y)==0&&x+y>=z){
return true;
}
return false;
}
inline int gcd2(int a,int b) {
if(b) while((a%=b) && (b%=a));
return a+b;
}
};