Medium

题目描述

给你两个容量分别为 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. 把 5 升水壶剩下的 2 升水倒进 3 升水壶 (2, 0)
5. 再次装满 5 升水壶 (2, 5)
6. 把 5 升水壶的水倒进 3 升水壶直到 3 升水壶满，5 升水壶剩下 4 升 (3, 4)
7. 倒空 3 升水壶，现在 5 升水壶里正好有 4 升水 (0, 4)

示例 2:

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

示例 3:

输入: x = 1, y = 2, target = 3
输出: true
解释: 同时装满两个水壶，总水量等于 3

提示:

  • 1 <= x, y, target <= 10³

解题思路

这是一个经典的数学问题，可以用数论中的贝祖等式（Bézout’s identity）来解决。

核心思想： 对于两个水壶容量 x 和 y，通过倒水操作能够得到的水量，本质上是 x 和 y 的线性组合，即 ax + by 的形式（其中 a, b 为整数）。根据贝祖等式，整数 a, b 存在使得 ax + by = gcd(x, y) 成立，因此我们能够测量出的最小正水量是 gcd(x, y)。

判断条件：

  1. 如果 target > x + y，显然无法达到，因为两个水壶的总容量就是 x + y
  2. 如果 target == 0，直接返回 true（两个水壶都为空）
  3. 如果 target % gcd(x, y) == 0，说明 target 是 gcd(x, y) 的倍数，可以通过组合操作达到

算法步骤：

  1. 处理边界情况：target 为 0 或者超出总容量
  2. 计算 x 和 y 的最大公约数 gcd(x, y)
  3. 判断 target 是否为 gcd(x, y) 的倍数

这种数学方法的时间复杂度是 O(log(min(x, y)))，远优于 BFS/DFS 搜索方法。

代码实现

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        if (target == 0) return true;
        
        return target % gcd(x, y) == 0;
    }
    
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target > x + y:
            return False
        if target == 0:
            return True
        
        import math
        return target % math.gcd(x, y) == 0

public class Solution {
    public bool CanMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        if (target == 0) return true;
        
        return target % GCD(x, y) == 0;
    }
    
    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
}

/**
 * @param {number} x
 * @param {number} y
 * @param {number} target
 * @return {boolean}
 */
var canMeasureWater = function(x, y, target) {
    if (target > x + y) return false;
    if (target === 0) return true;
    
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    return target % gcd(x, y) === 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(log(min(x, y)))计算最大公约数的时间复杂度
空间复杂度O(1)只使用常数级别的额外空间