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

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

ops 2025/8/29 20:37:39

在这里插入图片描述

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 代码拆解
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结

摘要

这道题其实就是经典的 “两个水壶问题”，你可能在电影《虎胆龙威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

题解答案

其实解法有两个方向：

数学解法（最大公约数 GCD）
- 经典定理：只要 target <= x + y，并且 target 是 gcd(x, y) 的倍数，就能得到。
- 这就是数论里的贝祖定理。
- 这个方法非常简洁高效。
模拟解法（BFS/DFS 搜索所有可能的状态）
- 模拟真实倒水过程，尝试所有可能的壶水量组合，看是否能达到 target。
- 更直观，但效率会差一些。

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

题解代码分析

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

import Foundationclass 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

代码拆解

判断边界情况：
- 如果 target 比两个壶加起来还大，那不可能。
- 如果 target 等于总容量，那就直接可以倒满。
- 如果 target = 0，也 trivially 成立。
用最大公约数 GCD 判断：
- 数学原理是：能倒出的水量一定是 gcd(x, y) 的倍数。
- 所以只要 target % gcd(x, y) == 0，就能实现。
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，两个壶一起装满就行