LeetCode日常-中等-365-水壶问题

本文最后更新于：2020年9月27日 晚上

题目

　　有两个容量分别为 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        statues = set()
        stack = {(0, 0)}

        while stack:
            now_x, now_y = stack.pop()

            if now_x==z or now_y==z or now_x+now_y==z:
                return True

            if (now_x, now_y) not in statues:
                statues.add((now_x, now_y))

                # 倒光其中一个
                stack.add((0, now_y))
                stack.add((now_x, 0))
                # 装满其中一个
                stack.add((x, now_y))
                stack.add((now_x, y))
                # 一个倒入另一个, 判断是否会超出容量
                # 全入y
                if now_x+now_y < y:
                    stack.add((0, now_x+now_y))
                else:
                    now_x = now_x - (y - now_y)
                    stack.add((now_x, y))
                # 全入x
                if now_x+now_y < x:
                    stack.add((now_x+now_y, 0))
                else:
                    now_y = now_y - (x - now_x)
                    stack.add((x, now_y))
        return False

思路

运用set(集合)不会有重复元素的功能。
通过深度优先的方法迭代获得结果。
O(xy)

数学解法

思路

这是一道关于数论的题目，确切地说是关于裴蜀定理（英语：Bézout’s identity）的题目。
裴蜀定理

　　我们认为，每次操作只会让桶里的水总量增加x，增加 y，减少x，或者减少y。

　　你可能认为这有问题：如果往一个不满的桶里放水，或者把它排空呢？那变化量不就不是x或者y了吗？接下来我们来解释这一点：

  • 首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的
  • 其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；
  • 再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。

　　因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a,ba，使得

ax+by=z

而只要满足 z≤x+y，且这样的 a,b 存在，那么我们的目标就是可以达成的。这是因为：

  • 若 a≥0,b≥0，那么显然可以达成目标。
  • 若 a<0，那么可以进行以下操作：
    1. 往 y 壶倒水；
    2. 把 y 壶的水倒入 x 壶；
    3. 如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。
    4. 重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。
  • 若 b<0，方法同上，x 与 y 互换。

而贝祖定理告诉我们，ax+by=z 有解当且仅当 z 是 x,y 的最大公约数的倍数。因此我们只需要找到 x,y 的最大公约数并判断 z 是否是它的倍数即可。

参考：