leetcode365. 水壶问题

有两个水壶，容量分别为 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"

/**
 * @param {number} x
 * @param {number} y
 * @param {number} target
 * @return {boolean}
 */
 // 1.先装满5L壶的水，装满3L的壶 ，5:2，3:3
// 2.3L的壶清空，5L壶的水倒入3L壶的水， 5:0，3:2
// 3.再装满5L壶的水，装满3L的壶 ，5:4，3:3
// 4.辗转相除法，还有求A与B的最大公约数
var canMeasureWater = function(x, y, z) {
    if(x + y < z) return false;
    if(z === 0) return true;
    if(x === 0 ) return y === z;
    if(y === 0 ) return x === z;

    function shuihu(a,b){
        let min = Math.min(a,b);
        while(min){
            if(a % min === 0 && b % min === 0) return min;
            min--;
        }
        return 1;
    }
    return z % shuihu(x,y) === 0;
};

代码解读：

题干聚焦：给定两个容量分别为x和y的水壶以及目标容量z，判断是否可以使用这两个水壶来测量出恰好z升的水。

逻辑梳理:

1. 首先检查两个水壶的总容量是否小于目标容量z，如果是，则无法测量出z升的水，返回false。
2. 如果目标容量z为0，那么不需要任何操作就可以达到目标，返回true。
3. 如果其中一个水壶的容量为0，那么只有另一个水壶可以测量出z升的水，如果另一个水壶的容量等于z，则可以测量出z升的水，否则无法测量出z升的水，返回false。
4. 定义一个辅助函数shuihu(a, b)，用于计算两个数a和b的最大公约数。这个函数通过辗转相除法来计算最大公约数。
5. 最后，判断目标容量z是否能被x和y的最大公约数整除，如果能整除，说明可以通过这两个水壶测量出恰好z升的水，返回true；否则，返回false。