DeepSeek LeetCode 365. 水壶问题 Java实现

LeetCode 365. 水壶问题题意有两个水壶容量分别为 x 和 y 升。允许以下操作· 装满任意一个水壶· 倒空任意一个水壶· 将一个水壶的水倒入另一个直到源壶空或目标壶满判断能否恰好量出 z 升水。思路一数学裴蜀定理 / Bézout’s Identity⭐推荐关键结论能得到的任意水量一定是 gcd(x, y) 的倍数。· 因为每一步操作只涉及加/减 x 或 y相当于在求 ax by 的线性组合。· 由裴蜀定理ax by 能取到的所有值恰好是 gcd(x, y) 的倍数。因此判定条件z x y水总量上限z 能被 gcd(x, y) 整除classSolution{publicbooleancanMeasureWater(intx,inty,intz){// 水量超过两壶总容量不可能if(zxy)returnfalse;// 两壶容量都为 0 时只能量出 0if(x0y0)returnz0;// 目标必须是 gcd(x, y) 的倍数returnz%gcd(x,y)0;}privateintgcd(inta,intb){while(b!0){intta%b;ab;bt;}returna;}}复杂度时间 O(log(min(x, y)))空间 O(1)。思路二BFS状态搜索把 (a, b) 看作状态a、b 为两壶当前水量从 (0,0) 出发做 BFS看是否到达某个状态满足 a z || b z || a b z。importjava.util.*;classSolution{publicbooleancanMeasureWater(intx,inty,intz){if(zxy)returnfalse;if(z0)returntrue;SetLongvisitednewHashSet();Dequeint[]queuenewArrayDeque();queue.offer(newint[]{0,0});visited.add(0L);while(!queue.isEmpty()){int[]curqueue.poll();intacur[0],bcur[1];if(az||bz||abz)returntrue;// 六种操作得到的所有可能的下一个状态Listint[]nextnewArrayList();next.add(newint[]{x,b});// 装满 xnext.add(newint[]{a,y});// 装满 ynext.add(newint[]{0,b});// 倒空 xnext.add(newint[]{a,0});// 倒空 y// x - yintpourMath.min(a,y-b);next.add(newint[]{a-pour,bpour});// y - xpourMath.min(b,x-a);next.add(newint[]{apour,b-pour});for(int[]s:next){longkey(long)s[0]*(y1)s[1];if(visited.add(key)){queue.offer(s);}}}returnfalse;}}复杂度时间/空间 O(x * y)状态数最多为 (x1)(y1)。小结方法 时间复杂度 说明数学gcd O(log(min(x,y))) 面试首选结论简洁优雅BFS O(x*y) 通用搜索思路便于理解易错点· z x y 直接返回 false· x 0 y 0 时 gcd 为 0 会导致除零需要特判· z 0 恒为 true初始即为 0 升