365.水壶问题

水壶问题"/>

365.水壶问题

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

例如x=3，y=5，z=4时return True，分析一下如果把5升的水壶装满水，然后倒入3升的水壶中，这时候5升的水壶里还剩2升水；然后把3升的水壶里的水都倒掉，再把5升水壶里的2升水倒入3升水壶中，再把5升的水壶装满，这时候3升的水壶里有2升水，5升的水壶里5升水，将5升的水壶里的水往3升水壶里倒，倒了一升后3升的水壶就满了，此时5升的水壶里有4升水，即为所求。

针对任意给出的x，y，z，可以假设用x与y分别往一个很大的容器里倒水和倒出水，那么如果z=m*x+n*y，找到合适的正整数m与n即为所求，其中m与n为负时，往外倒水，为正时，往里倒水。

若z<=x+y且z%d==0,说明存在m、n使得最终剩余水为z。根据贝祖等式，d为x、y的最大公约数。

 def canMeasureWater(self, x, y, z):""":type x: int:type y: int:type z: int:rtype: bool"""tmp=self.gcd(x,y)if z==0:return Trueif z>x+y:return Falsereturn z%tmp==0def gcd(self,x,y):if y==0:return xreturn self.gcd(y,x%y)