LeetCode0365.水和水壶问题【中】【Python】【BFS】【数学】问题LeetCode给你两个容量为x和y升的水壶。有无限量的供水可用。您需要确定是否可以使用这两个水壶精确测量z升。如果可以测量z升水，则到最后，一个或两个水桶中必须装有z升水。允许的操作：将任何一个水罐装满水。清空任何一个水罐。将水从一个水罐倒入另一个水罐中tilltheotherjugiscompletelyfullorthefirstjugisempty.Example1:(Fromthefamous"DieHard"example)Input:x=3,y=5,z=4Output:TrueExample2:Input:x=2,y=6,z=5Output:False问题虎胆龙威有两个体积x升和y升的水壶和无限量的水。请判断用这两个水壶是否可以恰好得到z升水？最后，如果可以的话，使用上述一个或两个罐子来装你得到的z升。您允许：装满任何水罐清空任何水罐将水从一个水罐倒入另一个水罐，直到满或空示例1：（来自著名的“虎胆龙威”示例）输入：x=3,y=5,z=4输出：True示例2：输入：x=2,y=6,z=5输出：False解的思路——BFS每个水壶都有三个操作：装水、倒水、互相倒水。Python3代码类解决方案：defcanMeasureWater(self,x:int,y:int,z:int)->bool:#解决方案一：BFSfromcollectionsimportdequequeue=deque([[0,0]])visited=set([(0,0)])whilequeue:cur_x,cur_y=queue.pop()ifzin[cur_x,cur_y,cur_x+cur_y]:returnTrueforitemin[#x装满水，y装满withwater(x,cur_y),(cur_x,y),#x清空水，y清空水(0,cur_y),(cur_x,0),#用jugy填充jugx直到它满或空（cur_x+cur_y-y,y)ifcur_x+cur_y>=yelse(0,cur_x+cur_y),#将X壶中的水倒入Y壶中，直到满或空(x,cur_x+cur_y-x)ifcur_x+cur_y>=xelse(cur_x+cur_y,0)]:ifitemnotinvisited:queue.appendleft(item)#从队列左侧添加元素visited.add(item)returnFalse找到整数a,b使得方程ax+by=z有解。有整数解当且仅当z是a和b的最大公约数d的倍数.Python3codeclassSolution:defcanMeasureWater(self,x:int,y:int,z:int)->bool:#方案二：裴树定理importmathifx+y
