Leetcode 365. 水壶问题

¶题意

一个水杯容量为$x$，另一个水杯容量为$y$，每次只能装满或者清空，问能否凑出$z$升水（一个水杯为$z$，或两个水杯加起来为$z$）。

¶做法

这边有一个非常关键的观察点是：

• 水量的变化只可能是$+x, -x, +y, -y$。

考虑一个水杯处于半满状态，此时不管是装满还是清空都是没有意义的。

所以题目就变成了$ax + by = z$，找出$a$和$b$，注意$z$显然要$\le x + y$。显然根据裴蜀定理，只需要$z % gcd(x, y) == 0$即可。

fn gcd(x: i32, y : i32) -> i32 {
    if y == 0 {
        return x;
    }
    gcd(y, x % y)
}

impl Solution {
    pub fn can_measure_water(jug1_capacity: i32, jug2_capacity: i32, target_capacity: i32) -> bool {
        if target_capacity > jug1_capacity + jug2_capacity {
            return false;
        }
        target_capacity % gcd(jug1_capacity, jug2_capacity) == 0
    }
}

由于$z\le x + y$，直接记忆化搜索也是可以的。