365. 水壶问题

🟠   🔖  深度优先搜索 广度优先搜索 数学  🔗 力扣 LeetCode

题目

You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:

• Fill either jug completely with water.
• Completely empty either jug.
• Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

Example 1:

Input: x = 3, y = 5, target = 4

Output: true

Explanation:

Follow these steps to reach a total of 4 liters:

1. Fill the 5-liter jug (0, 5).
2. Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
3. Empty the 3-liter jug (0, 2).
4. Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
5. Fill the 5-liter jug again (2, 5).
6. Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
7. Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).

Reference: The Die Hard example.

Example 2:

Input: x = 2, y = 6, target = 5

Output: false

Example 3:

Input: x = 1, y = 2, target = 3

Output: true

Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.

Constraints:

• 1 <= x, y, target <= 10^3

题目大意

有两个水壶，容量分别为 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 <= 10^3

解题思路

这道题是经典的 水壶问题，可以通过深度优先搜索（DFS）进行求解。

1. 状态空间：
   • 每个状态由当前水量 n 表示，从初始状态 n = 0 开始。
2. 四种可能的操作：
   • 向当前水量加入 x 升水：n + x
   • 向当前水量加入 y 升水：n + y
   • 倒掉 x 升水：n - x
   • 倒掉 y 升水：n - y
3. 剪枝条件：
   • 超出总容量 x + y
   • 当前水量小于 0
   • 当前水量已经访问过（避免死循环）
4. 结束条件：
   • 当 n = target 时，代表可以量出 target 升水，返回 true.

复杂度分析

• 时间复杂度：O(x + y)，由于水量只能在 0 到 x + y 之间，因此最多有 O(x + y) 种不同的水量组合需要遍历。

• 空间复杂度：O(x + y)

  • 使用递归 DFS，会有函数调用栈，最深递归层数为 O(x + y)。
  • 还使用了一个集合 visited 来存储访问状态，空间需求为 O(x + y)。

代码

/**
 * @param {number} x
 * @param {number} y
 * @param {number} target
 * @return {boolean}
 */
var canMeasureWater = function (x, y, target) {
	let visited = new Set();
	const dfs = (n) => {
		if (visited.has(n) || n < 0 || n > x + y) return false;
		if (target == n) return true;
		visited.add(n);
		return dfs(n + x) || dfs(n - x) || dfs(n + y) || dfs(n - y);
	};
	return dfs(0);
};