算法题之水壶问题

水壶问题

有两个水壶，容量分别为 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];}
}

复杂度分析

• 时间复杂度：，不同的情况最多可能有种，我们使用深度优先搜索，深度优先的复杂度是，所以总的时间复杂度即。
• 空间复杂度：，我们用了一个Stack栈和Set集合，其中Set集合中最多会放置种情况。