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;
    }
};