LeetCode题练习与总结：水壶问题--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 <= 10^3

二、解题思路

这个问题可以通过数学的方法来解决。具体来说，可以使用“贝祖定理”（Bézout’s identity），该定理指出，对于任意两个整数 a 和 b，存在整数 x 和 y，使得 ax + by = gcd(a, b)，其中 gcd(a, b) 是 a 和 b 的最大公约数。

在这个问题中，我们可以将 x 和 y 看作是两个整数，而我们需要找到的是否能通过某种方式得到 target 升水，等价于寻找整数 x 和 y，使得 ax + by = target。

解题思路如下：

1. 如果 target 大于 x 和 y 的总和，那么不可能得到 target 升水。
2. 如果 x 或 y 之一是 target，那么显然可以。
3. 如果 x 和 y 互质（即 gcd(x, y) = 1），那么根据贝祖定理，我们可以得到任意小于 x + y 的整数。
4. 如果 target 是 x 和 y 的最大公约数的倍数，那么我们可以得到 target 升水。

三、具体代码

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        // 边界条件处理
        if (x + y < target) return false;
        if (x == 0 || y == 0) return target == 0 || x + y == target;
        
        // 计算 x 和 y 的最大公约数
        return target % gcd(x, y) == 0;
    }
    
    // 辗转相除法求最大公约数
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

在这段代码中，gcd 函数使用辗转相除法来计算两个数的最大公约数。canMeasureWater 函数首先处理了一些边界情况，然后检查 target 是否是 x 和 y 的最大公约数的倍数。如果是，则返回 true，表示可以测量出 target 升水；否则返回 false。

四、时间复杂度和空间复杂度

1. 时间复杂度

• gcd函数：

  • gcd 函数使用辗转相除法来计算两个数的最大公约数。
  • 在最坏的情况下，辗转相除法需要执行 O(log(min(a, b))) 次迭代，其中 a 和 b 是输入的两个整数。
  • 因此，gcd 函数的时间复杂度是 O(log(min(x, y)))。

• canMeasureWater函数：

  • 该函数调用了 gcd 函数一次，除此之外没有其他的循环或递归操作。
  • 因此，canMeasureWater 函数的时间复杂度与 gcd 函数相同，即 O(log(min(x, y)))。

2. 空间复杂度

• gcd函数：

  • 该函数使用了固定数量的额外空间，即 temp 变量用于存储中间结果。
  • 因此，gcd 函数的空间复杂度是 O(1)。

• canMeasureWater函数：

  • 除了调用 gcd 函数外，该函数只使用了几个基本类型的变量（x、y、target）。
  • 因此，canMeasureWater 函数的空间复杂度也是 O(1)。

综上所述，整个代码的时间复杂度和空间复杂度如下：

• 时间复杂度：O(log(min(x, y)))
• 空间复杂度：O(1)

这里的 min(x, y) 表示 x 和 y 中的较小值。时间复杂度中的对数表示辗转相除法迭代的次数，它取决于输入值的大小，而不是问题的规模。空间复杂度为常数，表示无论输入值如何变化，所需的空间量保持不变。

五、总结知识点

• 函数定义：

  • 在 Java 中，使用 public 关键字定义一个方法，使其可以被其他类访问。
  • private 关键字用于定义一个私有方法，该方法只能在定义它的类内部被访问。

• 递归算法：

  • gcd 方法是一个递归算法，尽管它使用的是循环而不是直接递归调用，但它的逻辑是递归的，因为它不断将问题分解为更小的子问题。

• 辗转相除法：

  • gcd 方法实现了辗转相除法（也称为欧几里得算法），这是一种计算两个整数最大公约数（Greatest Common Divisor, GCD）的经典算法。

• 模运算符 %：

  • 使用 % 运算符计算一个数除以另一个数后的余数。

• 条件语句：

  • 使用 if 语句来处理边界条件，例如当 x 或 y 为 0 时，或者 target 大于 x 和 y 的总和时。

• 逻辑运算：

  • 在 canMeasureWater 方法中，使用了逻辑与 && 和逻辑或 || 运算符来判断多个条件。

• 算术运算：

  • 代码中使用了加法 + 和赋值运算符 = 来执行算术操作。

• 类型转换：

  • 在 gcd 方法中，使用了类型转换来确保余数操作正确执行。

• 返回值：

  • canMeasureWater 方法返回一个布尔值 true 或 false，表示是否可以测量出 target 升水。
  • gcd 方法返回一个整数，表示两个数的最大公约数。

• 数学原理：

  • 代码利用了贝祖定理的原理，即对于任意两个整数 a 和 b，它们的最大公约数 gcd(a, b) 能够整除它们的任何线性组合 ax + by。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。