Swift 解法详解 LeetCode 365：水壶问题

摘要

这道题其实就是经典的 “两个水壶问题”，你可能在电影《虎胆龙威3》里见过，布鲁斯·威利斯用两个水壶精确量出 4 升水来解除炸弹。这题就是把那个场景搬到了编程世界里。

我们的目标是：给定两个水壶的容量，看看能不能通过倒水、装满、倒空等操作，刚好得到指定的 target 升水。

描述

题目设定：

• 有两个水壶，容量分别是 x 和 y 升。

• 水无限供应。

• 操作允许：

  1. 把任意一个水壶装满
  2. 把任意一个水壶清空
  3. 把一个水壶里的水倒进另一个水壶，直到前者空或者后者满

问题：能不能正好量出 target 升？

示例 1

输入: x = 3, y = 5, target = 4
输出: true

示例 2

输入: x = 2, y = 6, target = 5
输出: false

示例 3

输入: x = 1, y = 2, target = 3
输出: true

题解答案

其实解法有两个方向：

1. 数学解法（最大公约数 GCD）

   • 经典定理：只要 target <= x + y，并且 target 是 gcd(x, y) 的倍数，就能得到。
   • 这就是数论里的贝祖定理。
   • 这个方法非常简洁高效。

2. 模拟解法（BFS/DFS 搜索所有可能的状态）

   • 模拟真实倒水过程，尝试所有可能的壶水量组合，看是否能达到 target。
   • 更直观，但效率会差一些。

我这里用 Swift 先写 数学解法，然后再在分析里扩展到模拟解法。

题解代码分析

下面是 Swift 的数学解法代码：

import Foundation

class Solution {
    func canMeasureWater(_ x: Int, _ y: Int, _ target: Int) -> Bool {
        // 如果目标超过两个水壶加起来的容量，直接不可能
        if target > x + y {
            return false
        }
        // 如果刚好等于总容量，也行
        if target == x + y {
            return true
        }
        // 如果目标是 0 也 trivially 成立
        if target == 0 {
            return true
        }
        // 使用最大公约数判断
        return target % gcd(x, y) == 0
    }
    
    // 求最大公约数（辗转相除法）
    private func gcd(_ a: Int, _ b: Int) -> Int {
        if b == 0 { return a }
        return gcd(b, a % b)
    }
}

// MARK: - Demo 演示
let solution = Solution()

print("示例1: \(solution.canMeasureWater(3, 5, 4))") // true
print("示例2: \(solution.canMeasureWater(2, 6, 5))") // false
print("示例3: \(solution.canMeasureWater(1, 2, 3))") // true

代码拆解

1. 判断边界情况：

   • 如果 target 比两个壶加起来还大，那不可能。
   • 如果 target 等于总容量，那就直接可以倒满。
   • 如果 target = 0，也 trivially 成立。

2. 用最大公约数 GCD 判断：

   • 数学原理是：能倒出的水量一定是 gcd(x, y) 的倍数。
   • 所以只要 target % gcd(x, y) == 0，就能实现。

3. Demo 测试：
   三个示例跑完结果都正确。

示例测试及结果

运行结果：

示例1: true
示例2: false
示例3: true

再自己加几个测试：

print(solution.canMeasureWater(6, 10, 8)) // true，因为 gcd(6,10)=2，8是2的倍数
print(solution.canMeasureWater(6, 10, 7)) // false，因为 gcd=2，7不是倍数
print(solution.canMeasureWater(4, 4, 8))  // true，两个壶一起装满就行

时间复杂度

• 主要就是求一次最大公约数，时间复杂度 O(log(min(x, y)))。
• 非常快。

空间复杂度

• 除了递归栈，几乎没有额外空间，复杂度是 O(1)。

总结

这题其实一眼看上去像 BFS/DFS 的模拟搜索题，但背后藏着一个非常优雅的数学结论。
核心公式就是：target % gcd(x, y) == 0 且 target <= x + y。

在实际生活中，这种场景也经常遇到，比如：

• 你有两个量杯，要量出指定的水。
• 工厂配料时，用不同规格的容器去配比原料。
• 甚至调酒的时候，也能用这个方法。

如果你喜欢更直观的解法，也可以用 BFS 来写，把 (a, b) 表示当前两个壶的状态，然后不断倒水直到找到目标。这个解法更贴近真实操作，但效率会差一些。