水壶问题
有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。
你可以：
- 装满任意一个水壶
- 清空任意一个水壶
- 将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。
示例 1:
输入: x = 3,y = 5,target = 4 输出: true 解释： 按照以下步骤操作，以达到总共 4 升水： 1. 装满 5 升的水壶(0, 5)。 2. 把 5 升的水壶倒进 3 升的水壶，留下 2 升(3, 2)。 3. 倒空 3 升的水壶(0, 2)。 4. 把 2 升水从 5 升的水壶转移到 3 升的水壶(2, 0)。 5. 再次加满 5 升的水壶(2, 5)。 6. 从 5 升的水壶向 3 升的水壶倒水直到 3 升的水壶倒满。5 升的水壶里留下了 4 升水(3, 4)。 7. 倒空 3 升的水壶。现在，5 升的水壶里正好有 4 升水(0, 4)。 参考：来自著名的 "Die Hard"
示例 2:
输入: x = 2, y = 6, target = 5 输出: false
示例 3:
输入: x = 1, y = 2, target = 3 输出: true 解释：同时倒满两个水壶。现在两个水壶中水的总量等于 3。
提示:
1 <= x, y, target <= 103
解题思路
想起了当年实习面试的时候，笔试题中有一道题目就是类似的，有两个水壶，一个3升，一个5升，问怎么才能获取4升水。当时思考了一下，然后把题目做出来了；不仅做出来，还画了一个如何操作的草图。时隔多年，还能想到当时做出题目高兴的样子，现在想想还是挺有趣的。
今天咱们来尝试用代码解出来。
最容易想到的办法，就是一直尝试，装满第一个水壶，然后倒到第二个水壶里，或者从第二个水壶里倒到第一个水壶里，利用两个壶相差的容量，尝试出最后的结果。
在这道题中，提供了两个水壶，也就是说往壶里倒水或者不倒水是可以穷举出来的，假设两个壶分别为X壶、Y壶，操作上有以下这几种情况：
- 把X壶装满
- 把Y壶装满
- 把X壶倒空
- 把Y壶倒空
- 把X壶的水倒到Y壶里，直到X壶的水倒完了或者Y壶装满了
- 把Y壶的水倒到X壶里，直到Y壶的水倒完了或者X壶装满了
如果上面几种操作都不满足，那么可以继续再来一轮操作，需要注意的是，这轮操作中，需要以上轮操作中，X壶和Y壶中剩余的水量开始操作，而不是直接以满壶或者空壶来操作。
如果没有找到满足的答案的情况，什么时候停止呢？
我们其实可以发现，第一轮的操作和后面的操作中，两个壶里剩下的水量可能会有相同的情况，那么出现的相同的水量的情况，就可以不用再重复操作了。所以我们需要用一个Set集合记录已经出现的情况，并且再下一次操作之前去除。当我们把所有情况都遍历完了，仍然没有找到符合的情况，那么就可以停止了，说明是不能获取到出目标水量的。
具体代码如下：
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
Deque<int[]> stack = new LinkedList<int[]>();
stack.push(new int[]{0, 0});
Set<Long> seen = new HashSet<Long>();
while (!stack.isEmpty()) {
if (seen.contains(hash(stack.peek()))) {
stack.pop();
continue;
}
seen.add(hash(stack.peek()));
int[] state = stack.pop();
int remain_x = state[0], remain_y = state[1];
if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
return true;
}
// 把 X 壶灌满。
stack.push(new int[]{x, remain_y});
// 把 Y 壶灌满。
stack.push(new int[]{remain_x, y});
// 把 X 壶倒空。
stack.push(new int[]{0, remain_y});
// 把 Y 壶倒空。
stack.push(new int[]{remain_x, 0});
// 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
stack.push(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});
// 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
stack.push(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});
}
return false;
}
public long hash(int[] state) {
return (long) state[0] * 1000001 + state[1];
}
}复杂度分析
- 时间复杂度：
，不同的情况最多可能有
种，我们使用深度优先搜索，深度优先的复杂度是
，所以总的时间复杂度即
- 空间复杂度：