题目描述

[EN | CN]

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

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

你允许:

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

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

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

示例 2:

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

解法 1:BFS / DFS

直接的思路就是暴力遍历所有情况,不过要注意记录每次剩水的情况,避免重复。

我们可选的操作有:

  • 装满 x
  • 装满 y
  • 清空 x
  • 清空 y
  • x 的水倒入 y,直到 y 被倒满或者 x 的水倒完;
  • y 的水倒入 x,直到 x 被倒满或者 y 的水倒完。

遍历可以用 BFS 或者 DFS 来做,下面我们使用 BFS。

假设两个水壶的容量分别为 $x$、$y$,那么

  • 时间复杂度为 $O(xy)$,极端条件下我们最多有 $(x+1)(y+1)$ 种剩水的情况;
  • 空间复杂度为 $O(xy)$,极端条件下我们最多有 $(x+1)(y+1)$ 种剩水的情况。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        stack = [(x, y)]
        passed = set()
        while stack:
            a, b = stack.pop(0)
            if (a, b) in passed:
                continue
            if a == z or b == z or a + b == z:
                return True
            passed.add((a, b))
            stack.extend([
                (x, b),
                (a, y),
                (0, b),
                (a, 0),
                (a - min(a, y - b), b + min(a, y - b)),
                (a + min(b, x - a), b - min(b, x - a)),
            ])

        return False
  • 执行用时:6292 ms,在所有 Python3 提交中击败了 9.27% 的用户。
  • 内存消耗:81.4 MB,在所有 Python3 提交中击败了 100.00% 的用户。

解法 2:数学

首先需要知道一个数学知识 裴蜀定理(Bézout's Lemma),也叫 裴蜀等式(Bézout's identity)、贝祖定理

对于任意两个整数 $a$、$b$,若 $d=\gcd(a,b)$ 是他们的最大公约数,那么关于 $x$、$y$ 的 线性丢番图方程(即 裴蜀等式): $$ ax + by = m $$ 有整数解 $(x, y)$ 当且仅当 $m$ 是 $d$ 的整数倍;并且当它有解时必定有无穷多个解。

首先,在我们能对水壶做的 6 种操作里面,有些操作是无意义的,解释如下:

  • 首先,两个水壶不可能同时有水且不满。
  • 其次,对一个不满的水壶加满水或者倒空是没有意义的,因为此时另一个水壶为空或者满,做这个操作之后得到的结果与初始状态其实是一样的。
  • 因此,我们其实只有两个操作是有效操作:将空水壶装满、将满水壶倒空。

综上,我们可以认为每次操作只会给水的总量带来 xy 的变化量,我们的目标变成了:找到一对整数 ab,满足 $ax + by = z$

又根据 裴蜀定理,该等式成立当且仅当 $z$ 是 $x$、$y$ 的最大公约数的倍数,因此,我们只要找到 $x$、$y$ 的最大公约数,并判断 $z$ 是否是它的倍数即可。

假设两个水壶的容量分别为 $x$、$y$,那么

  • 时间复杂度为 $O(\log(\min(x, y)))$,取决于最大公约数的计算;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

1
2
3
4
5
6
7
8
import math
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x + y < z:
            return False
        if x == 0 or y == 0:
            return z == 0 or x + y == z
        return z % math.gcd(x, y) == 0
  • 执行用时:40 ms,在所有 Python3 提交中击败了 71.51% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 100.00% 的用户。