JAVA 牛牛

365. 水壶问题

  • Mar 21, 2020
  • 0 views

题目 水壶问题

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

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

你允许：

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

示例

示例 1:

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

示例 2:

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

1. 欧几里得算法(辗转相除法)

这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。

  • 基于这条定理：

首先，我们先计算出a除以b的余数c，把问题转化成求出b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求出c和d的最大公约数；再然后计算出c除以d的余数e，把问题转化成求出d和e的最大公约数……以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。

欧几里得法(辗转相除法) 通过举例说明

举例： 105和85的最大公约数

  1. 第一轮计回算 105÷85=1…20
  2. 第二轮计算 85÷20=4…5
  3. 第三轮计算 20÷5=4
  4. 第三轮没有余数， 因此 105和85的最大公约数就是第三轮计算的被除数 5

解题思路

  • 求最大公约数 官方叫做 欧几里得法(辗转相除法)
  • 代码一目了然，不用文字赘述了

代码

class Solution:
    def canMeasureWater(self, a: int, b: int, c: int) -> bool:
        # 保证a>b
        if b>a:
            a , b = b ,a
        if c == 0: # 当c == 0 时 肯定满足
            return True
        if a + b < c: # 这个条件 题目中没说清楚
            return False
        if b == 0: # 当b=0时 a==c 才能满足条件
            return a==c
        # 求最大公约数，官方叫法 欧几里得法(辗转相除法)
        while b!=0:
            temp = a % b
            a = b
            b = temp
        if c%a!=0:
            return False
        return True

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if(z==0) { // 当z == 0 时 肯定满足
            return true;
        }
        if(x+y<z) { //这个条件 题目中没说清楚
            return false;
        }
        if (x==0) { // 当x=0时 z==y 才能满足条件
            return z==y;
        }
        // # 保证y>x
        if(x>y) {
            int c = x;
            x = y;
            y = c;
        }
        // 求最大公约数，官方叫法 欧几里得法(辗转相除法)
        while (y%x!=0) {
            int c = y;
            y = x;
            x = c%x;
        }
        return z%x==0;
    }
}

before (2020-04-29更新)

自己的思路

  • 找到x,y的最大公约数能否z被整除

自己的代码

java

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        boolean b1= false;
        boolean b2= false;
        boolean b3= false;
        if(z==0) {
            return true;
        }
        if(x+y<z) {
            return false;
        }
        if (x==0) {
            return z==y;
        }
        if(x>y) {
            int c = x;
            x = y;
            y = c;
        }
        while (y%x!=0) {
            int c = y;
            y = x;
            x = c%x;
        }
        return z%x==0;
    }
}

python

class Solution:
    def canMeasureWater(self, x, y, z):
        """
        :type x: int
        :type y: int
        :type z: int
        :rtype: bool
        """
        if z == 0:
            return True
        if x+y < z:
            return False
        if x>y:
            x,y=y,x
        if x == 0:
            return y==z
        while y%x != 0:
            y,x = x,y%x
        return z%x==0

用时

两小时

官方解题思路

思路及算法

首先对题目进行建模。观察题目可知，在任意一个时刻，此问题的状态可以由两个数字决定：X 壶中的水量，以及 Y 壶中的水量。

在任意一个时刻，我们可以且仅可以采取以下几种操作：

  • 把 X 壶的水灌进 Y 壶，直至灌满或倒空；
  • 把 Y 壶的水灌进 X 壶，直至灌满或倒空；
  • 把 X 壶灌满；
  • 把 Y 壶灌满；
  • 把 X 壶倒空；
  • 把 Y 壶倒空。 因此，本题可以使用深度优先搜索来解决。搜索中的每一步以 remain_x, remain_y 作为状态，即表示 X 壶和 Y 壶中的水量。在每一步搜索时，我们会依次尝试所有的操作，递归地搜索下去。这可能会导致我们陷入无止境的递归，因此我们还需要使用一个哈希结合（HashSet）存储所有已经搜索过的 remain_x, remain_y 状态，保证每个状态至多只被搜索一次。

在实际的代码编写中，由于深度优先搜索导致的递归远远超过了 Python 的默认递归层数（可以使用 sys 库更改递归层数，但不推荐这么做），因此下面的代码使用栈来模拟递归，避免了真正使用递归而导致的问题。

官方代码

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        stack = [(0, 0)]
        self.seen = set()
        while stack:
            remain_x, remain_y = stack.pop()
            if remain_x == z or remain_y == z or remain_x + remain_y == z:
                return True
            if (remain_x, remain_y) in self.seen:
                continue
            self.seen.add((remain_x, remain_y))
            # 把 X 壶灌满。
            stack.append((x, remain_y))
            # 把 Y 壶灌满。
            stack.append((remain_x, y))
            # 把 X 壶倒空。
            stack.append((0, remain_y))
            # 把 Y 壶倒空。
            stack.append((remain_x, 0))
            # 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
            stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))
            # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
            stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))
        return False

复杂度分析

  • 时间复杂度：$O(log(min(x, y)))$，取决于计算最大公约数所使用的辗转相除法。
  • 空间复杂度：$O(1)$，只需要常数个变量。
Search