卡题了。。。

方法一 暴力

暴力出奇迹！

这题可以考虑 BFS 或者 DFS ，用一个 unordered_set 来记录当前l两个水壶水的状态

在任意一个时刻，你可以执行以下操作

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

然而这个办法并不推荐，时间和空间都太大了

方法二 扩展 GCD

然后就是这题的正解，说是扩展 GCD ，其实就是裴蜀等式

先考虑一下方法一里面的操作，其实有两个操作是没有提到的：

  • 把一个不空的水壶倒空
  • 把一个不满的水壶装满

然而，你是不会做这两个操作的。这两个操作相当与你把之前的操作直接抹掉了

然后两个壶里面互相倒其实是不会对总量发生改变的

我们可以认为每次操作只会给水的总量带来正负 x 或者正负 y 的变化量

因此我们要找到一对整数 (a, b)，使得 ax+by=z 有解即可

还有一点是 z<=x+y ，毕竟壶就这么大

然后摸出裴蜀等式：

对任意两个整数 a, b ，关于未知数x和y的线性丢番图方程（裴蜀等式） ax+by=m

当且仅当 m 是 gcd(a,b) 的倍数时有整数解 (x,y) 。裴蜀等式有解时必然有无穷多个解。

推论： a,b 互质时使得 ax+by=1 有解（充要条件）

所以只需要找到 gcd(x, y) 并判断 z 是否是它的倍数即可

1
2
3
4
5
6
7
8
9
10
11
class Solution
{
public:
	bool canMeasureWater(int x, int y, int z)
	{
		if (z > x + y) return false;
		if (z == x || z == y) return true;
		if (x == 0 || y == 0) return false;
		return z % gcd(x, y) == 0;
	}
};

方法三 动态规划

没想到吧！这也能 DP ！

其实原理和方法二一样的

现在我们能有无限个 x 升和 y 升，因此我们还能有无限个 -x 升和 -y 升

然后摸出 Leetcode 322 零钱兑换 的代码，改一改扔进去跑就行

也就是根据这四个零钱拼出来 z 的总额

代码复用大成功！