Leetcode 365. Water and Jug Problem

可以想象有一个无限大的水罐，如果我们有两个杯子x和y，那么原来的问题等价于是否可以通过往里面注入或倒出水从而剩下z。

z =? m*x + n*y

如果等式成立，那么z%gcd(x,y) == 0。

 class Solution(object):

     def canMeasureWater(self, x, y, z):

         """

         :type x: int

         :type y: int

         :type z: int

         :rtype: bool

         """

         if z == 0 or (z<= x+y and z%self.gcd(x,y) == 0):

             return True

         else:

             return False

     def gcd(self, x, y):

         while y != 0:

             (x, y) = (y, x % y)

         return x

巴特西

Leetcode 365. Water and Jug Problem

最新文章

热门文章