365. 水壶问题

题目

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水.

你允许：

• 装满任意一个水壶
• 清空任意一个水壶
• 从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例1：

输入: x = 3, y = 5, z = 4
输出: True

示例2：

输入: x = 2, y = 6, z = 5
输出: False

解法

解法一：

例子中的3升的水壶和5升的水壶，得到4升水，可以这么操作

1. 装满3升水壶，倒入5升水壶
2. 再装满3升水壶，倒入5升水壶，此时3升水壶剩1升水，5升水壶已装满
3. 倒空5升水壶，将3升水壶的1升水倒入5升水壶，此时3升水壶为空，5升水壶剩1升水
4. 装满3升水壶，倒入5升水壶，此时5升水壶的水刚好为4升

再看一个例子，用7升和13升的水壶，能否到处3升的水

1. 装满7升的水壶，倒入13升的水壶
2. 再装满7升的水壶，倒入13升的水壶直至满，此时，7升的水壶剩1升水
3. 清空13升的水壶，并将7升水壶的1升水，倒入13升的水壶
4. 继续装满13升的水壶，此时，7升的水壶剩2升
5. 清空13升的水壶，并将7升水壶的2升水倒入13升的水壶中
6. 装满13升的水壶，此时7升的水壶剩3升水

例子1可以抽象为3x mod 5 = 4，这里x=3，也就是要装满3次3升的水壶

例子2可以抽象为7xmod13=3，这里x=6，也就是要装满6次7升的水壶

再把问题抽象得到

X*x mod Y == Z

求这个方程是否有解？

此处可参考扩展欧几里得算法

Java

public boolean canMeasureWater(int x, int y, int z) {
		if (x + y < z) {
			return false;
		}
		if (x == 0 || y == 0) {
			return z == 0 || x + y == z;
		}
		return z % gcd(x, y) == 0;
	}

	private int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}