当前位置: 首页 > 后端技术 > Python

力扣-0365.水和水壶问题【Python】

时间:2023-03-26 00:36:23 Python

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