当前位置：首页 > news >正文

个体户做网站与公司好网站开发销售提成

news 2025/9/18 4:04:40

个体户做网站与公司好,网站开发销售提成,青岛外发加工网,网站制作设计哪家公司好水壶问题有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。你可以： 装满任意一个水壶清空任意一个水壶将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。示…

水壶问题

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

复杂度分析

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