leetcode第365题：水壶问题

有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

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

你可以：

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

示例 1:

输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true
解释：来自著名的 “Die Hard”

示例 2:

输入: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
输出: false

示例 3:

输入: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
输出: true

提示:

1 < = jug1Capacity, jug2Capacity, targetCapacity < = 106

方法一：深度优先搜索

思路及算法

首先对题目进行建模。观察题目可知，在任意一个时刻，此问题的状态可以由两个数字决定：X 壶中的水量，以及 Y 壶中的水量。

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

• 把 X 壶的水灌进 Y 壶，直至灌满或倒空；
• 把 Y 壶的水灌进 X 壶，直至灌满或倒空；
• 把 X 壶灌满；
• 把 Y 壶灌满；
• 把 X 壶倒空；
• 把 Y 壶倒空。

水壶问题是一个经典的数学问题，给定两个水壶的容量x和y，需要判断是否能够通过倒水的方式，将其中一个水壶中的水量准确地测量为z升。

代码中的_gen_states函数用于生成所有可能的状态。每个状态都是一个元组，表示两个水壶中的水量。函数中列举了六种可能的状态：

• 清空A杯：将A杯中的水倒空，即(0, b)
• 清空B杯：将B杯中的水倒空，即(a, 0)
• 把A杯装满：将A杯装满，即(x, b)
• 把B杯装满：将B杯装满，即(a, y)
• 把A杯倒入B杯，直到B杯满：将A杯中的水倒入B杯，直到B杯满。如果倒入后A杯中的水量加上B杯中的水量小于B杯的容量，那么状态为(0, a + b)，否则状态为(a + b - y, y)。
• 把B杯倒入A杯，直到A杯满：将B杯中的水倒入A杯，直到A杯满。如果倒入后A杯中的水量加上B杯中的水量小于A杯的容量，那么状态为(a + b, 0)，否则状态为(x, a + b - x)。

canMeasureWater函数使用BFS搜索状态空间，判断是否存在解。首先判断特殊情况，如果z小于0或者x和y的和小于z，那么肯定无法得到z升水量，直接返回False。然后使用队列q进行BFS，初始状态为0，表示两个水壶都是空的。使用集合visited记录已经访问过的状态，初始时将0加入visited。在BFS过程中，每次从队列中取出当前节点current_sum，如果current_sum等于z，那么找到了解，返回True。否则，根据current_sum生成下一层可能的状态，并判断是否已经访问过，如果没有访问过，则将其加入visited并加入队列q。如果遍历完所有可能的状态，仍然没有找到解，那么返回False。

在主函数中，创建了一个Solution对象sol，并分别调用了三个示例的测试用例。输出结果为True、False、True，分别表示第一个和第三个测试用例存在解，而第二个测试用例不存在解。

python

import math
import collections

# 生成所有可能的状态
def _gen_states(a, b, x, y):
    return [
        (0, b),  # 清空A杯
        (a, 0),  # 清空B杯
        (x, b),  # 把A杯装满
        (a, y),  # 把B杯装满
        (0, a + b) if a + b < y else (a + b - y, y),  # 把A杯倒入B杯，直到B杯满
        (a + b, 0) if a + b < x else (x, a + b - x)  # 把B杯倒入A杯，直到A杯满
    ]

class Solution(object):
    # 使用BFS搜索状态空间
    def canMeasureWater(self, x, y, z):
        if z < 0 or x + y < z:
            return False

        # 使用队列进行BFS
        q = collections.deque([0])
        visited = {0}

        while len(q):
            # 当前节点处理
            current_sum = q.popleft()
            if current_sum == z:
                return True

            # 生成下一层节点
            states = _gen_states(current_sum, y - current_sum, x, y)
            for state in states:
                if state not in visited:
                    visited.add(state)
                    q.append(sum(state))

        return False


if __name__ == '__main__':
    sol = Solution()
    print(sol.canMeasureWater(3, 5, 4))
    print(sol.canMeasureWater(1, 2, 3))
    print(sol.canMeasureWater(2, 6, 5))

方法二：数学法 - 最大公约数

思路

这是一道关于数论的题目，确切地说是关于裴蜀定理

摘自wiki的定义：
.
对任意两个整数 a、b，设 d是它们的最大公约数。那么关于未知数 x和 y的线性丢番图方程（称为裴蜀等式）：
ax+by=m
.
有整数解 (x,y) 当且仅当 m是 d的整数倍。裴蜀等式有解时必然有无穷多个解。

因此这道题可以完全转化为裴蜀定理。还是以题目给的例子x = 3, y = 5, z = 4，我们其实可以表示成3 * 3 - 1 * 5 = 4, 即3 * x - 1 * y = z。我们用a和b分别表示3
升的水壶和5升的水壶。那么我们可以：

• 倒满a（1）
• 将a倒到b
• 再次倒满a（2）
• 再次将a倒到b（a这个时候还剩下1升）
• 倒空b（-1）
• 将剩下的1升倒到b
• 将a倒满（3）
• 将a倒到b
• b此时正好是4升

上面的过程就是3 * x - 1 * y = z的具体过程解释。

也就是说我们只需要求出x和y的最大公约数d，并判断z是否是d的整数倍即可。

JavaScript

/**
 * @param {number} x
 * @param {number} y
 * @param {number} z
 * @return {boolean}
 */
var canMeasureWater = function(x, y, z) {
  if (x + y < z) return false;

  if (z === 0) return true;

  if (x === 0) return y === z;

  if (y === 0) return x === z;

  function GCD(a, b) {
    let min = Math.min(a, b);
    while (min) {
      if (a % min === 0 && b % min === 0) return min;
      min--;
    }
    return 1;
  }

  return z % GCD(x, y) === 0;
};

实际上求最大公约数还有更好的方式，比如辗转相除法：

def GCD(a, b):
    if b == 0: return a
    return GCD(b, a % b)

复杂度分析

• 时间复杂度：O(log(max(a,b)))O(log(max(a, b)))O(log(max(a,b)))
• 空间复杂度：空间复杂度取决于递归的深度，因此空间复杂度为 O(log(max(a,b)))O(log(max(a, b)))O(log(max(a,b)))。
• 如果将上述过程改成迭代，那么可以降低到O(1)O(1)O(1)，也不难

BFS、DFS模板