每日两题 T1

合一大师

发布于 2020-07-17 12:45:45

3600

发布于 2020-07-17 12:45:45

文章被收录于专栏：JavaScript全栈JavaScript全栈

算法

LeetCode T365. 水壶问题[1]

描述

有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。

你允许：

•装满任意一个水壶•清空任意一个水壶•从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1: (From the famous *"Die Hard"* example[2])

输入: x = 3, y = 5, z = 4
输出: True

示例 2:

输入: x = 2, y = 6, z = 5
输出: False

分析

首先我们要明确一点，每次操作仅仅会让桶中水的总量增加 x或增加 y，减少或减少 y。

因为在题目给定的条件下，两个桶不存在都有水并且都不满的情况，换言之，操作后，两个桶中水至少一个是空或者满。再者，我们分析易知：对一个不满的桶加水是没有什么意义的，为什么呢？因为给一个不满的桶加水其实就相当于将该桶初始化为满桶水；同理将一个未装满水桶的水倒掉也没有意义。

通过分析我们还能得出，两桶水的总量是否能满足给定的z是取决于x、y两桶容量的差值，也就是说差的制造是通过反复将大桶中的水倒入小桶产生的，整个操作描述如下：

1.往 y 壶倒水

2.把 y 壶的水倒入 x 壶 3.如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶 4.重复以上操作直至某一步时 x 壶进行了 m 次倒空操作，y 壶进行了 n 次倒水操作。

由贝祖定理可得：mx+ny=z，当且仅当z是x、y最大公约数的倍数时，成立，因此，我们只需找出x、y最大公约数即可。

源码

/**
 * @param {number} x
 * @param {number} y
 * @param {number} z
 * @return {boolean}
 */
var canMeasureWater = function(x, y, z) {
    if (x + y < z) {
        return false;
    }
    if (x === 0 || y === 0) {
        return (z === 0) || (x + y  === z);
    }
    return (z % calcGcd(x, y)) === 0;
};
function calcGcd(a, b) {
    if (b === 0) {
        return a;
    }
    return calcGcd(b, a % b);
}