365. 水壶问题

作者: 人一己千 | 来源:发表于2020-03-31 03:30 被阅读0次

题目

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/water-and-jug-problem
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

重点是参悟到 每次增加或者减少的水量要么是x要么是y。

以下解释来自官方题解

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

  • 首先要清楚,在题目所给的操作下,两个桶不可能同时有水且不满。因为观察所有题目中的操作,操作的结果都至少有一个桶是空的或者满的;

  • 其次,对一个不满的桶加水是没有意义的。因为如果另一个桶是空的,那么这个操作的结果等价于直接从初始状态给这个桶加满水;而如果另一个桶是满的,那么这个操作的结果等价于从初始状态分别给两个桶加满;

  • 再次,把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的,那么这个操作的结果等价于回到初始状态;而如果另一个桶是满的,那么这个操作的结果等价于从初始状态直接给另一个桶倒满。

因此,我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成:找到一对整数 a, ba,b,使得
ax+by=z
剩下的就是找x和y的最大公因数,如果z是他们最大公因数的倍数的话那就是有解了。

代码


class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if z == 0: return True
        if x + y < z: return False
        if x == 0 and y == 0: return z == 0
        if x == 0 or y == 0 : return z == x+y
        while x%y != 0:
            t = x%y
            x = y
            y = t
        return z%y==0

总结

边界值判断。
辗转相除找最大公因数。

相关文章

  • 365. 水壶问题

    【Description】有两个容量分别为 x升 和* y*升 的水壶以及无限多的水。请判断能否通过使用这两个水壶...

  • 365.水壶问题

    解题思路 裴蜀定理(或贝祖定理),说明了对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性不定方程(称为...

  • 365. 水壶问题

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

  • leetcode 365. 水壶问题

    这道题我没有提交,原因是我还不能完全理解。

  • LeetCode 365. 水壶问题

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

  • LeetCode 365.水壶问题

    题目 水壶问题链接可能点不进去,所以我把完整的题目写在了下面。 分析 题意非常清晰,没有异议。对于示例 1我们可以...

  • LeetCode-python 365. 水壶问题

    题目链接[https://leetcode.cn/problems/water-and-jug-problem] ...

  • 每日一题-leetcode 365. 水壶问题

    有两个水壶,容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可...

  • 水壶问题

    题目: 题目的理解: 起初设想的解决方式:(1)x和y的相差,求得所有相差的值,即每一个值与所有的值相减,直到不会...

  • 水壶问题通解

    有两个容量分别为a升和b升的水壶以及无限多的水。请判断能否通过使用这个两个水壶,从而可以得到恰好z升的水?你允许进...

网友评论

    本文标题:365. 水壶问题

    本文链接:https://www.haomeiwen.com/subject/dmjiuhtx.html