有两个容量分别为 x
升 和 y
升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z
升的水?
如果可以,最后必须用以上水壶中的一或两个来盛放取得的 z
升水。
允许做以下操作:
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水,直到装满或者倒空
示例 1:(出自电影《虎胆龙威》)1
2输入: x = 3, y = 5, z = 4
输出: True
操作方法:先把A壶加满,倒入B壶,再把A壶加满,倒入B壶,此时A、B各有1升和5升水。倒光B壶,把A壶中的1升水倒入B壶,加满A壶,倒入B壶,此时B壶即有4升水。
示例 2:1
2输入: x = 2, y = 6, z = 5
输出: False
题解:
如果从纯算法角度来考虑该问题,那么 DFS 或者 BFS 都可以。以 (A壶水量, B壶水量)
作为状态去搜索。每个状态需要搜下面这 6 种情况:
- 装满A壶
- 装满B壶
- 清空A壶
- 清空B壶
- 从A壶向B壶倒水,直到装满或者倒空
- 从B壶向A壶倒水,直到装满或者倒空
为了防止无限递归,需要建立一个 HashSet 来存储已经搜索过的状态,保证每个状态最多只被搜到一次。由于搜索深度很深,递归实现容易爆栈,所以可以用栈(队列)实现 DFS(BFS)。
无论 DFS 还是 BFS,因为最多有 $(x+1)(y+1)$ 种状态,所以时间复杂度和空间复杂度都是 $O(xy)$。反正我写的 DFS 在 LeetCode 上 TLE 了😩
![TLE](/2020/03/water-and-jug-problem/img1.png)
然而此题有个绝妙的数学解法,可秒杀 DFS/BFS:
我们首先需要明确,在初始状态下,两个水壶中水的总量是 0,之后,不管我们做六种操作的哪一种,都只会使水的总量 增加x
或 增加y
或 减少x
或 减少y
。注意,两个水壶不会同时半满,所以如果我们把半满的水壶倒空或接满,虽然水的总量的变化量不是 x
或 y
,但是这么操作之后就又回到了 一个空一个满
或 两个空
或 两个满
的状态,所以把半满的水壶倒空或接满这类操作是无意义的。
所以,水的总量的变化量一定是 x
或 y
,由此我们可以得知水的总量永远等于 $ax+by$,其中$a,b\in Z$。这样一来,获取 z
升水的充要条件就是 $z\leq x+y$ 并且方程 $ax+by=z$ 有整数解。
由贝祖定理(或称裴蜀定理)可知,$ax+by=z$ 有解当且仅当 $z$ 是 $x, y$ 的最大公约数的倍数。所以此题数学解法的代码如下:
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14int gcd(int a, int b) // 求最大公约数
{
return b ? gcd(b, a%b) : a;
}
bool canMeasureWater(int x, int y, int z)
{
if(z > x + y)
return false;
else if(x == 0 && y == 0 && z == 0)
return true;
else
return z % gcd(x, y) == 0;
}
这种解法的时间复杂度等于辗转相除法求最大公约数的时间复杂度,即 $O(\log(\min \lbrace x, y\rbrace ))$,空间复杂度为 $O(1)$。
![双百解法](/2020/03/water-and-jug-problem/img2.png)