LeetCode.365.Water and Jug Problem 水壶问题

题目描述

365 Water and Jug Problem
https://leetcode-cn.com/problems/water-and-jug-problem/

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:
Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

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

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

---

解题过程

之前只遇到过具体的题目，就比如示例中的 3 升水桶和 5 升水桶量出 4 升水，但找出一个通用解法还真没想过。
想了半天发现怎么也考虑不全，只能看答案了，官方题解讲的还是听清楚的。

DFS或BFS

在任意一个时刻，此问题的状态可以由两个数字决定：X 壶中的水量 remainX，以及 Y 壶中的水量 remainY。

在任意一个时刻，我们可以且仅可以采取以下几种操作：

• 装满x
• 装满y
• 倒空x
• 倒空y
• x倒入y，直到x为空或者y满
• y倒入x，直到y为空或者x满

这6种操作就可以看做是以当前状态 (remainX, remainY) 为起点的 6 个分支，如下图所示。我们需要遍历这6个分支，深度优先搜索 DFS 或者 广度优先搜索 BFS 都可以，用递归或者栈就是深度优先搜索DFS，用队列就是广度优先搜索BFS。

需要注意的是，遍历过程中会回到起点，比如 (0, 0) 开始，装满 x 得到 (x, 0) ，倒空 x 又得到 (0, 0)，所以用一个 set 标记已经访问过的状态，其实就相当于图中的把访问过的结点标为 visited = true

时间复杂度 O(xy) 空间复杂度 O(xy)

private static class SolutionV2020 {
    public boolean canMeasureWater(int x, int y, int z) {
        if (z > x + y || z < 0) {
            return false;
        }
        Deque<Pair<Integer, Integer>> stack = new LinkedList<>();
        stack.push(new Pair<>(0, 0));
        // 已经检查过的 remainX, remainY 集合
        Set<Pair<Integer, Integer>> found = new HashSet<>();
        while (!stack.isEmpty()) {
            Pair<Integer, Integer> pair = stack.pop();
            // 已经检查过的不再考虑
            if (found.contains(pair)) {
                continue;
            }
            int remainX = pair.getKey(), remainY = pair.getValue();
            if (z == remainX || z == remainY || z == remainX + remainY) {
                return true;
            }
            found.add(pair);
            // 装满x
            stack.push(new Pair<>(x, remainY));
            // 装满y
            stack.push(new Pair<>(remainX, y));
            // 倒空x
            stack.push(new Pair<>(0, remainY));
            // 倒空y
            stack.push(new Pair<>(remainX, y));
            // x倒入y，直到x为空或者y满
            stack.push(remainX + remainY < y ? new Pair<>(0, remainX + remainY) : new Pair<>(remainX + remainY - y, y));
            // y倒入x，直到y为空或者x满
            stack.push(remainX + remainY < x ? new Pair<>(remainX + remainY, 0) : new Pair<>(x, remainX + remainY - x));
        }
        return false;
    }
}

数学(贝祖定理)

两个壶里水的总量一定是ax+by（a,b为整数），当z=ax+by时，返回true。
根据贝祖定理： 若a,b是整数, 且a,b的最大公约数是d，即 gcd(a,b)=d，那么对于任意的整数x,y, ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
所以，若存在整数a,b，使得ax+by=z成立，则z一定为x.y最大公因数的整数倍。
所以，只要z是x，y最大公约数的整数倍，返回true

---

GitHub代码

algorithms/leetcode/leetcode/_365_WaterJugProblem.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_365_WaterJugProblem.java

---