每日一题-21

题目描述

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

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

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)

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

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

解题思路

1.DFS遍历或BFS遍历。

• 本题python实现dfs会超过默认递归层数导致超时，所以利用栈模拟dfs。
• 利用队列实现bfs。
  本题遍历都基于水壶的六种状态操作，下方代码有描述。同时设置一个set，存储已经遍历过的状态，防止重复遍历。

2.利用贝祖定理。

• 裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
• 这题为什么能使用这个定理。
  是因为对于两个水壶的总量，它的变化情况只有四种。增加x;增加y;减少x;减少y;
  因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a,b，使得：ax+by=z。具体证明参考https://leetcode-cn.com/problems/water-and-jug-problem/solution/shui-hu-wen-ti-by-leetcode-solution/

代码

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        # # 把 X 壶的水灌进 Y 壶，直至灌满或倒空；
        # # 把 Y 壶的水灌进 X 壶，直至灌满或倒空；
        # # 把 X 壶灌满；
        # # 把 Y 壶灌满；
        # # 把 X 壶倒空；
        # # 把 Y 壶倒空；
        # stack = [(0, 0)]#存储两个水壶还剩多少水
        # s = set()#存储已经遍历过的情况
        # while len(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 s:
        #         continue
        #     s.add((remain_x, remain_y))
        #     #X壶倒空
        #     stack.append((0, remain_y))
        #     #Y壶倒空
        #     stack.append((remain_x, 0))
        #     #X壶灌满
        #     stack.append((x, remain_y))
        #     #Y壶灌满
        #     stack.append((remain_x, y))
        #     #X壶的水倒到Y壶中，X倒空或Y倒满
        #     stack.append((remain_x-min(remain_x, y-remain_y), min(remain_x+remain_y, y)))
        #     #Y壶的水倒到X壶中，Y壶倒空或X倒满
        #     stack.append((min(remain_x+remain_y, x), remain_y-min(remain_y, x-remain_x)))
        # return False

        if x + y < z:
            return False
        if x == 0 or y == 0:
            return z == 0 or x + y == z
        return z % math.gcd(x, y) == 0