Leecode365. 水壶问题

题目描述：

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

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

你允许：

装满任意一个水壶

清空任意一个水壶

从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1: (From the famous “Die Hard” example)

输入: x = 3, y = 5, z = 4

输出: True

示例 2:

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

输出: False

解题思路，由于这个题只需要判断是否能通过，不需要知道具体的过程，那么我们可以抽象的将其化成一个求两个数字的公约数问题。

同时要注意在求最大公约数的时候，gcd()方法内是不需要判断x,y的大小的，因为是递归调用，因此如果两个数是互质的，那么调用这个方法都是返回1，如果两个数不是互质的，那么无论x大还是y大，最终返回的都是x和y的最大公约数。

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if(x == 0 && y == 0) return z == 0;
        return (z % gcd(x,y) == 0 && x + y >= z);
    }
    static int gcd(int x,int y){
        if(y == 0) return x;
        int r = x % y;
        return gcd(y,r);
    }
}