365. Water and Jug Problem

LeetCode
,

今天的题目是365. Water and Jug Problem。

我们可以执行的操作有三种：

  • 给一个杯子装满
  • 倒掉一个杯子中的所有水
  • 将一个杯子中的水转移到另一个杯子中直到没水或者另一个杯子装满

三种操作会分别让两个杯子总水量产生三种：

  • 增加x或y
  • 减少x或y
  • 总量不变

上面的说法是没有考虑向一个未空的杯子中加水或者是从一个未空的杯子中加水的情况，因为这样的操作显然是没有意义的。

因此杯子中的总水量可以用ax+by表示，其中a和b都是整数。此时问题转换为是否存在a和b使得ax+by=z。根据裴蜀定理，我们可以用z % gcd(x,y)来判断。

代码如下：

1
2
3
4
5
6
7
8
9
10
int gcd(int x,int y) {
	return x % y == 0 ? y : gcd(x, x % y);
}
bool canMeasureWater(int x, int y, int z) {
	if (x == 0 && y == 0) return z == 0;
	if (x + y < z) return false;
	if (x > y) swap(x, y); // y >= x
	int d = x ? gcd(y, x) : y;
	return (z % d == 0);
}