365. 水壶问题（使用栈做深度遍历 / 数学方法）

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

BFS+剪枝

class Solution:def canMeasureWater(self, x: int, y: int, z: int) -> bool:#5 5 2 2 5 4 get#3 0 3 0 2 3'''利用栈做深度遍历·出栈x_thisC,y_thisC·判断条件；if x_thisC==z or y_thisC==z or x_thisC+y_thisC ==z: return True·共六种情况：1.x->y倒水 2.y->x倒水3.x倒满  4.y倒满5.x倒空  6.y倒空分别加入栈中，并且用res_store保存走过的路径，用于剪枝·到最后都没有找到，则没有，return False'''res_store = set()zhan = [[x,y],[0,y],[x,0]]def daoshui(i,i_max,j,j_max):#i->jtemp = ii -= j_max-jj += tempj = j_max if j>=j_max else ji = 0 if i<0 else ireturn i,jwhile(zhan):temp = zhan.pop(0)x_thisC,y_thisC = temp[0],temp[1]if x_thisC==z or y_thisC==z or x_thisC+y_thisC ==z:return Trueif (x_thisC,y_thisC) in res_store:continueres_store.add( (x_thisC,y_thisC) )#1x_now,y_now = daoshui(x_thisC,x,y_thisC,y)zhan.append([x_now,y_now])#2y_now,x_now = daoshui(y_thisC,y,x_thisC,x)        zhan.append([x_now,y_now])#3zhan.append([x,y_thisC])#4zhan.append([x_thisC,y])#5zhan.append([0,y_thisC])#6zhan.append([x_thisC,0])return False

 数学方法（还没看

 水壶问题官方题解

class Solution:def canMeasureWater(self, x: int, y: int, z: int) -> bool:if x + y < z:return Falseif x == 0 or y == 0:return z == 0 or x + y == zreturn z % math.gcd(x, y) == 0