两水壶量取目标容量问题求解及GCD解法原理解析咨询

核心理论依据：贝祖定理 #

对于任意两个正整数a、b，设二者的最大公约数为d，那么一定存在整数x、y，使得 a*x + b*y = d。同时，所有可以表示为a*x + b*y形式的整数，一定是d的倍数。

定理与水壶问题的关联 #

水壶的所有操作对应的水量变化，本质上都是两个容量的线性组合：

• 装满任意一个水壶：总水量增加对应水壶的容量，对应线性组合的正系数+1
• 倒空任意一个水壶：总水量减少对应水壶的容量，对应线性组合的负系数-1
• 两个水壶之间互相倒水：总水量不变，不会改变线性组合的取值
  所以最终能得到的目标水量target，一定可以表示为jug1Capacity*x + jug2Capacity*y的整数形式，结合贝祖定理，target必须是两个水壶容量的最大公约数的倍数。

代码逐段解析 #

你提到的C++解法代码如下：

class Solution {
private:
    int gcd (int a, int b) {
        return b ? gcd (b, a % b) : a;
    }
public:
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        return jug1Capacity+jug2Capacity>=targetCapacity ? !(targetCapacity%gcd(jug1Capacity,jug2Capacity)) : false;
    }
};

1. gcd函数实现 #

这是递归版本的欧几里得算法，用来计算两个整数的最大公约数：

• 若b不为0，就递归计算b和a%b的最大公约数
• 若b为0，此时a就是两个数的最大公约数

2. 主逻辑判断 #

代码用三目运算符实现了两个必要条件的校验：

• 第一个校验：jug1Capacity+jug2Capacity>=targetCapacity，两个水壶最多装下二者容量之和的水，目标超过这个值直接不可能，返回false
• 第二个校验：!(targetCapacity%gcd(jug1Capacity,jug2Capacity))，判断目标值是否是两个容量最大公约数的倍数，如果取余结果为0就满足条件，返回true，否则返回false

测试用例验证 #

对应题目给出的三个用例验证逻辑完全匹配：

• 用例1：jug1=3，jug2=5，target=4。gcd(3,5)=1，4%1=0，3+5>=4，返回true
• 用例2：jug1=2，jug2=6，target=5。gcd(2,6)=2，5%2=1，不满足，返回false
• 用例3：jug1=1，jug2=2，target=3。gcd(1,2)=1，3%1=0，1+2=3>=3，返回true

内容的提问来源于stack exchange，提问作者sachin