题目
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:
Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous “Die Hard” example)
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False
假设现在有两个杯子，每个杯子分别最多可以装 x 和 y 升水，假设现在水的供应量是无限的，问是否有可能用这两个杯子共同承装 z 升水，可以用两个杯子执行的操作如下：
将任何一个杯子装满水
倒掉任何一个杯子中的所有水
将一个杯子中的水倒进另一个杯子，直到另一个杯子满了或者是当前的杯子已经空了
比如，如果现在两个杯子 A 和 B 分别能装 3 升水和 5 升水，需要在两个杯子中共装 4 升水。我们可以找到这样一个序列满足题目要求：
将 B 杯倒满水并导入 A 中，此时 A:3 B:2
将 A 杯倒空，并将 B 中的水倒入 A 中，此时 A:2 B:0
将 B 杯装满并倒 A 中，此时 A:3 B:4
将 A 杯倒掉，此时 A:0 B:4
思路一：搜索
这里可以说我们变相的利用了深度 / 广度优先搜索来实现。通过深度 / 广度优先搜索我们可以实现遍历所有可能的场景，直到找到我们最终想要的结果，或者得到该结果无法达到的结论。假设我们知道当前水杯的情况为 A 最多可以放置 x 升水，B 最多可以放置 Y 升水，而且 A 当前水杯中有 a 升水，B 中有 b 升水，则由当前情况在一次操作之后可能产生以下几种情况：
倒光 A 中的水：A:0 | B:b
倒光 B 中的水：A:a | B:0
装满 A 中的水：A:x | B:b
装满 B 中的水：A:a | B:y
将 A 中的水倒进 B 中：A:a – min(a, y-b) | B:b + min(a, y-b)
将 B 中的水倒进 A 中：A:a + min(x-a, y) | B:b – min(x-a, y)
最后两种情况需要判断两个杯子的剩余水情况和可倒入水的情况
如果以上几种情况都不满足 z，则我们再以以上几种情况为基础继续寻找可能的情况。这里可以使用 HashSet 来避免对情况的重复遍历。代码如下：
public class Status{
private int x;
private int y;
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getWater() {
return this.getX() + this.getY();
}
public Status(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if(o==null || !(o instanceof Status)) return false;
if(this == o) return true;
Status s = (Status) o;
return this.getX() == s.getX() && this.getY() == s.getY();
}
@Override
public int hashCode() {
return this.getX() + 17 * this.getY();
}
}
Set<Status> statusSet = new HashSet<Status>();
public boolean canMeasureWaterDFS(int x, int y, int z) {
if(x + y < z) return false;
if(x == z || y == z || x + y == z) return true;
return canMeasureWaterDFS(x, y , new Status(0, 0), z);
}
public boolean canMeasureWaterDFS(int x, int y, Status curStatus, int z) {
if(statusSet.contains(curStatus)) return false;
else if(curStatus.getWater() == z) return true;
else{
statusSet.add(curStatus);
return canMeasureWaterDFS(x, y, new Status(x, curStatus.getY()), z)
|| canMeasureWaterDFS(x, y, new Status(curStatus.getX(), y), z)
|| canMeasureWaterDFS(x, y, new Status(curStatus.getX(), 0), z)
|| canMeasureWaterDFS(x, y, new Status(0, curStatus.getY()), z)
|| canMeasureWaterDFS(x, y, new Status(
curStatus.getX() – Math.min(curStatus.getX(), y-curStatus.getY()),
curStatus.getY() + Math.min(curStatus.getX(), y-curStatus.getY())
),
z)
|| canMeasureWaterDFS(x, y, new Status(
curStatus.getX() + Math.min(x – curStatus.getX(), curStatus.getY()),
curStatus.getY() – Math.min(x – curStatus.getX(), curStatus.getY())
),
z);
}
}
思路二：数学
这里使用了一个数学结论叫做 Bézout’s identity，在该理论中，假设数字 a 和 b 有一个最大公约数 d，则一定存在 x 和 y 满足 ax+by=d。x,y 的其它组合所得到的值一定是 d 的倍数。这里 x 为负值时代表将杯子倒空，x 为正值时代表将杯子装满。
public boolean canMeasureWater(int x, int y, int z) {
if(x == z || y == z || x + y == z) return true;
if(x + y < z) return false;
while((x %= y) != 0 && (y %= x) != 0);
return z % (x+y) == 0;
}