第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0365. 水壶问题

题目地址(365. 水壶问题)

题目描述

1
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?
2
3
如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。
4
5
你允许:
6
7
装满任意一个水壶
8
清空任意一个水壶
9
从一个水壶向另外一个水壶倒水,直到装满或者倒空
10
示例 1: (From the famous "Die Hard" example)
11
12
输入: x = 3, y = 5, z = 4
13
输出: True
14
示例 2:
15
16
输入: x = 2, y = 6, z = 5
17
输出: False
Copied!

BFS(超时)

前置知识

  • BFS
  • 最大公约数

公司

  • 阿里
  • 百度
  • 字节

思路

两个水壶的水我们考虑成状态,然后我们不断进行倒的操作,改变状态。那么初始状态就是(0 0) 目标状态就是 (any, z)或者 (z, any),其中 any 指的是任意升水。
已题目的例子,其过程示意图,其中括号表示其是由哪个状态转移过来的:
0 0 3 5(0 0) 3 0 (0 0 )0 5(0 0) 3 2(0 5) 0 3(0 0) 0 2(3 2) 2 0(0 2) 2 5(2 0) 3 4(2 5) bingo

代码

1
class Solution:
2
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
3
if x + y < z:
4
return False
5
queue = [(0, 0)]
6
seen = set((0, 0))
7
8
while(len(queue) > 0):
9
a, b = queue.pop(0)
10
if a ==z or b == z or a + b == z:
11
return True
12
states = set()
13
14
states.add((x, b))
15
states.add((a, y))
16
states.add((0, b))
17
states.add((a, 0))
18
states.add((min(x, b + a), 0 if b < x - a else b - (x - a)))
19
states.add((0 if a + b < y else a - (y - b), min(b + a, y)))
20
for state in states:
21
if state in seen:
22
continue;
23
queue.append(state)
24
seen.add(state)
25
return False
Copied!
复杂度分析
  • 时间复杂度:由于状态最多有$O((x + 1) (y + 1))$ 种,因此总的时间复杂度为$O(x y)$。
  • 空间复杂度:我们使用了队列来存储状态,set 存储已经访问的元素,空间复杂度和状态数目一致,因此空间复杂度是$O(x * y)$。
上面的思路很直观,但是很遗憾这个算法在 LeetCode 的表现是 TLE(Time Limit Exceeded)。不过如果你能在真实面试中写出这样的算法,我相信大多数情况是可以过关的。
我们来看一下有没有别的解法。实际上,上面的算法就是一个标准的 BFS。如果从更深层次去看这道题,会发现这道题其实是一道纯数学问题,类似的纯数学问题在 LeetCode 中也会有一些,不过大多数这种题目,我们仍然可以采取其他方式 AC。那么让我们来看一下如何用数学的方式来解这个题。

数学法 - 最大公约数

思路

这是一道关于数论的题目,确切地说是关于裴蜀定理(英语:Bézout's identity)的题目。
摘自 wiki 的定义:
1
对任意两个整数 a、b,设 d是它们的最大公约数。那么关于未知数 x和 y的线性丢番图方程(称为裴蜀等式):
2
3
ax+by=m
4
5
有整数解 (x,y) 当且仅当 m是 d的整数倍。裴蜀等式有解时必然有无穷多个解。
Copied!
因此这道题可以完全转化为裴蜀定理。还是以题目给的例子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 的整数倍即可。

代码

代码支持:Python3,JavaScript
Python Code:
1
class Solution:
2
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
3
if x + y < z:
4
return False
5
6
if (z == 0):
7
return True
8
9
if (x == 0):
10
return y == z
11
12
if (y == 0):
13
return x == z
14
15
def GCD(a, b):
16
smaller = min(a, b)
17
while smaller:
18
if a % smaller == 0 and b % smaller == 0:
19
return smaller
20
smaller -= 1
21
22
return z % GCD(x, y) == 0
Copied!
JavaScript:
1
/**
2
* @param {number} x
3
* @param {number} y
4
* @param {number} z
5
* @return {boolean}
6
*/
7
var canMeasureWater = function (x, y, z) {
8
if (x + y < z) return false;
9
10
if (z === 0) return true;
11
12
if (x === 0) return y === z;
13
14
if (y === 0) return x === z;
15
16
function GCD(a, b) {
17
let min = Math.min(a, b);
18
while (min) {
19
if (a % min === 0 && b % min === 0) return min;
20
min--;
21
}
22
return 1;
23
}
24
25
return z % GCD(x, y) === 0;
26
};
Copied!
实际上求最大公约数还有更好的方式,比如辗转相除法:
1
def GCD(a, b):
2
if b == 0: return a
3
return GCD(b, a % b)
Copied!
复杂度分析
  • 时间复杂度:$O(log(max(a, b)))$
  • 空间复杂度:空间复杂度取决于递归的深度,因此空间复杂度为 $O(log(max(a, b)))$

关键点分析

  • 数论
  • 裴蜀定理
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。