水壶问题 | Nameless Site

来自Leetcode第365题水壶问题

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

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

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空 示例 1: (From the famous “Die Hard” example)

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

求最大公因数

来自官方题解

预备知识：贝祖定理

对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.

${(\frac{m}{d}(x_0 + \frac{kb}{d}),\frac{m}{d}(y_0 + \frac{ka}{d})) | k \in Z}$

在题目所给的操作下，两个桶不可能同时有水且不满。因为观察题目中的所有操作的结果都至少有一个桶是空的或者满的；

其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；

再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。

因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a, b，使得

$ax+by=z$

而只要满足 $z\leq x+y$，且这样的 a, b 存在，那么我们的目标就是可以达成的。这是因为：

若 $a\geq 0, b\geq 0$，那么显然可以达成目标。
若 $a\lt 0$，那么可以进行以下操作：
1. 往 y 壶倒水；
2. 把 y 壶的水倒入 x 壶；
3. 如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。
重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。
若 $b\lt 0$，方法同上，x 与 y 互换。

而贝祖定理告诉我们，$ax+by=z$ 有解当且仅当 z 是 x, y的最大公约数的倍数。因此我们只需要找到 x, y的最大公约数并判断 z是否是它的倍数即可。

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if(x + y < z)
            return false;
        if(x == 0 || y == 0)
            return z == 0 || x + y == z;
        while(y != 0){
            int tmp = y;
            y = x % y;
            x = tmp;
        }
        return z % x == 0;
    }
}

BFS

摘自题解

题目说：

你允许：

装满任意一个水壶

清空任意一个水壶

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

为了方便说明，我们做如下定义：

装满任意一个水壶，定义为「操作一」，分为：
（1）装满 A，包括 A 为空和 A 非空的时候把 A 倒满的情况；
（2）装满 B，包括 B 为空和 B 非空的时候把 B 倒满的情况。

清空任意一个水壶，定义为「操作二」，分为
（1）清空 A；
（2）清空 B。

从一个水壶向另外一个水壶倒水，直到装满或者倒空，定义为「操作三」，其实根据描述「装满」或者「倒空」就知道可以分为 4 种情况：

（1）从 A 到 B，使得 B 满，A 还有剩；
（2）从 A 到 B，此时 A 的水太少，A 倒尽，B 没有满；
（3）从 B 到 A，使得 A 满，B 还有剩余；
（4）从 B 到 A，此时 B 的水太少，B 倒尽，A 没有满。

因此，从当前「状态」最多可以进行 8 种操作，得到 8 个新「状态」，对这 8 个新「状态」，依然可以扩展，一直做下去，直到某一个状态满足题目要求。

建议大家在草稿纸上做一个简单的计算，看一下这 8 种操作怎么写，需要注意哪些边界的情况，相信是一个不错的练习。

然后请大家自己尝试写一下代码，广度优先遍历常见的写法有 2 种，由于这里不用求路径最短的长度，在出队的时候不用读取队列的长度。

从当前状态可以扩展出 8 种相邻的状态；
因为状态有重复，因此是一个「有向」且「有环」的图，在遍历的时候，需要判断该结点设置是否访问过；
有序整数对 (a, b) 可以自定义成一个私有的类；
图的遍历，可以使用「深度优先遍历」和「广度优先遍历」，因为状态空间很大，广搜是相对较快；
尽量「剪枝」，跳过不必要的搜索；
当然最快的是数学方法。

要重写qeuals和hashcode方法，不然会超时，这和HashSet的判断重复有关。

public boolean canMeasureWater(int x, int y, int z) {
    if (x + y < z)
        return false;
    if (x == 0 || y == 0)
        return z == 0 || x + y == z;
    Queue<Pair> queue = new LinkedList<>();
    Pair start = new Pair(0, 0);
    queue.add(start);  //增加初始状态(0,0)
    HashSet<Pair> visited = new HashSet<>();
    visited.add(start);
    Pair temp;
    int curX, curY,tmp;
    while (!queue.isEmpty()) {
        temp = queue.poll();
        curX = temp.x;
        curY = temp.y;
        if (curX == z || curY == z || curX + curY == z) {
            return true;
        }

        if (curX == 0) {  //转移状态1，将x装满
            temp = new Pair(x, curY);
            if (!visited.contains(temp)) {
                visited.add(temp);
                queue.add(temp);
            }
        }

        if (curY == 0) {  //转移状态1，将y装满
            temp = new Pair(curX, y);
            if (!visited.contains(temp)) {
                visited.add(temp);
                queue.add(temp);
            }
        }

        if (curY < y) { // 转移状态3，将x倒空
            temp = new Pair(0, curY);
            if (!visited.contains(temp)) {
                visited.add(temp);
                queue.add(temp);
            }
        }

        if (curX < x) { // 转移状态3，将x倒空
            temp = new Pair(curX, 0);
            if (!visited.contains(temp)) {
                visited.add(temp);
                queue.add(temp);
            }
        }

        tmp = Math.min(curX, y - curY);
        // y - curY是第二个桶还可以再加的水的升数，但是最多只能加curX升水。
        temp = new Pair(curX - tmp, curY + tmp);
        if (!visited.contains(temp)) {
            visited.add(temp);
            queue.add(temp);
        }

        tmp = Math.min(curY, x - curX);
        // y - curY是第二个桶还可以再加的水的升数，但是最多只能加curX升水。
        temp = new Pair(curX + tmp, curY - tmp);
        if (!visited.contains(temp)) {
            visited.add(temp);
            queue.add(temp);
        }

    }
    return false;
}

class Pair {
    public int x;
    public int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public Pair() {
    }

    @Override
    public boolean equals(Object obj) {
        if(this == obj)
            return true;
        if(obj == null || getClass() != obj.getClass())
            return false;
        Pair p = (Pair)obj;
        return p.x == this.x && p.y == this.y;
    }

    @Override
    public int hashCode() {
        return this.x * 10000 + this.y / 2;
    }
}