题目描述：

LeetCode 365. Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

• Fill any of the jugs completely.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1:

Input: x = 2, y = 6, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

题目大意：

给定两个容量分别为x和y升的罐子。提供无限容量的水。你需要判断用这两个罐子是否可以恰好量出z升的体积。

如果可以量出z升水，你最终需要将这些水装在其中的一个或者两个罐子中。

允许的操作包括：

• 将任意罐子灌满。
• 将任意罐子清空。
• 将任意罐子的水倒入另一个罐子，直到另一个罐子倒满或者自己为空为止。

测试用例如题目描述。

解题思路：

求最大公约数GCD（Greatest Common Divisor)。

如果x与y互质（最大公约数为1），则容量范围[1, x + y]之内的任意整数体积均可以通过适当的操作得到。

否则，记x与y的最大公约数为gcd，则可以获得的容量z只能为gcd的整数倍，且z <= x + y

简单的证明：

假设最终体积z = m * x + n * y（m与n为整数，可以为0或者为负）

令x = p * gcd, y = q * gcd，可知p与q互质。

则z = (m * p + n * q) * gcd

可以证明一定存在m, n，使得m * p + n * q = 1（p与q互质的性质，参见：裴蜀定理）

由此可知z一定是gcd的整数倍

Python代码：

class Solution(object):
    def canMeasureWater(self, x, y, z):
        """
        :type x: int
        :type y: int
        :type z: int
        :rtype: bool
        """
        if x > y: x, y = y, x
        gcd = self.gcd(x, y)
        if gcd == 0: return z == 0
        return z % gcd == 0 and z <= x + y

    def gcd(self, a, b):
        if a == 0: return b
        return self.gcd(b % a, a)

 

本文链接：http://bookshadow.com/weblog/2016/06/24/leetcode-water-and-jug-problem/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码