Leetcode 365-水壶问题

1. 题目描述

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

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

你允许：

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

例子：

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

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

2. 思路

其实不管怎么倒水，实质上，我们可以把两个水桶中的水视为一个整体，任何一次倒水的操作无非是下面这些情况中的某种：

让桶里的水总量增加$x$或$y$；
让桶里的水总量减少$x$或$y$；

乍一看，似乎会觉得不太对，因为似乎我们没考虑往一个不满的水桶中倒满水、或者把一个不满的水桶中的水全部倒掉的情况，但仔细一想，这两个操作是没有任何意义的：

因为，该问题已经做出了约束，每次只能把一个水桶倒满或者倒空，所以不可能会出现两个水桶都没满的情况；于是我们可以分析出，为什么说上述的没考虑的两种情况是无意义的；
如果我们尝试对一个不满的水桶A中加水，直到这个桶倒满。
- 如果另外一个桶B是空的，那这个操作就等价于最开始，只将A倒满；
- 如果另外一个桶B是满的，那这个操作就等价于最开始，依次将A、B倒满；
如果我们尝试把一个不满的水桶A中倒空。
- 如果另外一个桶B是空的，那这个操作就等价于最原始的情况，啥也没做；
- 如果另外一个桶B是满的，那这个操作就等价于最开始，只将B倒满；

所以，实际上我们就是要去找到一对整数$a,b$，使得$ax+by=z$，而只要满足 $z\leq x+y$，那么我们的目标就是可以达成的。这是因为：

若$a \geq 0, b \geq 0$，那么显然是可以的；
若$a<0$,则可视作为以下的操作：
1. 把$y$壶加满；
2. 把$y$壶的水倒入$x$中；
3. 如果$y$壶不为空，那么$x$壶肯定是满的，那么把$x$壶的水全倒掉，再把$y$壶的水倒入$x$中。
  
  重复以上操作直至某一步时$x$壶进行了$a$次倒空操作，$y$壶进行了$b$次倒水操作。
若$b<0$,和$a<0$的情况等效。

由贝祖定理可知：$ax+by=z$ 有解当且仅当$z$是$x,y$的最大公约数的倍数.

3. 代码

// 数学问题： 贝祖定理
class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        // 边界情况
        if(z==0)
            return true;
        if(z>x+y)
            return false;
        if(x==0 || y==0)
            return z==(x+y);
        
        int c=gcd(Math.max(x,y),Math.min(x,y));
        if(z%c==0)
            return true;
        else
            return false;

    }

    // 辗转相除求a和b的最大公约数,假设a>=b
    private int gcd(int a,int b)
    {
        int c;
        while((c=a%b)!=0)
        {
            a=b;
            b=c;
        }
        return b;
    }
}

Leetcode 365-水壶问题

贝祖定理

Leetcode 365-水壶问题

1. 题目描述

2. 思路

3. 代码

FEATURED TAGS

FRIENDS