【LeetCode: 365. 水壶问题 + 数学】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 365. 水壶问题

⛲ 题目描述

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

示例 2:

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

示例 3:

输入: x = 1, y = 2, target = 3
输出: true
解释：同时倒满两个水壶。现在两个水壶中水的总量等于 3。

提示:

1 <= x, y, target <= 103

🌟 求解思路&实现代码&运行结果

⚡ 数学

🥦 求解思路

1. 如果 z 大于 x + y，则无法得到 z 升水，直接返回 false。
2. 如果 x 或 y 为 0，则只有当 z 为 0 或 z 等于 x + y 时才返回 true。
3. 否则，判断 z 是否是 x 和 y 的最大公约数（GCD）的倍数。如果是，则返回 true；否则返回 false。
4. 有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z) {
            return false; // 边界条件：z 大于 x + y
        }
        if (x == 0 || y == 0) {
            return z == 0 || x + y == z; // 边界条件：x 或 y 为 0
        }
        return z % gcd(x, y) == 0; // 判断 z 是否是 x 和 y 的最大公约数的倍数
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a; // 递归终止条件
        }
        return gcd(b, a % b); // 递归计算最大公约数
    }
}

🥦 运行结果

💬 共勉