卡题了。。。

方法一 暴力

暴力出奇迹!

这题可以考虑 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 的总额

代码复用大成功!