企业官网建设流程全解析

LeetCode 365. 水壶问题

题意

有两个水壶，容量分别为 x 和 y 升。允许以下操作：

· 装满任意一个水壶
· 倒空任意一个水壶
· 将一个水壶的水倒入另一个，直到源壶空或目标壶满

判断能否恰好量出 z 升水。

思路一：数学（裴蜀定理 / Bézout’s Identity）⭐推荐

关键结论：能得到的任意水量一定是 gcd(x, y) 的倍数。

· 因为每一步操作只涉及加/减 x 或 y，相当于在求 ax + by 的线性组合。
· 由裴蜀定理，ax + by 能取到的所有值恰好是 gcd(x, y) 的倍数。

因此判定条件：

1. z <= x + y（水总量上限）
2. z 能被 gcd(x, y) 整除

classSolution{publicbooleancanMeasureWater(intx,inty,intz){// 水量超过两壶总容量，不可能if(z>x+y)returnfalse;// 两壶容量都为 0 时，只能量出 0if(x==0&&y==0)returnz==0;// 目标必须是 gcd(x, y) 的倍数returnz%gcd(x,y)==0;}privateintgcd(inta,intb){while(b!=0){intt=a%b;a=b;b=t;}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(z>x+y)returnfalse;if(z==0)returntrue;Set<Long>visited=newHashSet<>();Deque<int[]>queue=newArrayDeque<>();queue.offer(newint[]{0,0});visited.add(0L);while(!queue.isEmpty()){int[]cur=queue.poll();inta=cur[0],b=cur[1];if(a==z||b==z||a+b==z)returntrue;// 六种操作得到的所有可能的下一个状态List<int[]>next=newArrayList<>();next.add(newint[]{x,b});// 装满 xnext.add(newint[]{a,y});// 装满 ynext.add(newint[]{0,b});// 倒空 xnext.add(newint[]{a,0});// 倒空 y// x -> yintpour=Math.min(a,y-b);next.add(newint[]{a-pour,b+pour});// y -> xpour=Math.min(b,x-a);next.add(newint[]{a+pour,b-pour});for(int[]s:next){longkey=(long)s[0]*(y+1)+s[1];if(visited.add(key)){queue.offer(s);}}}returnfalse;}}

复杂度：时间/空间 O(x * y)（状态数最多为 (x+1)(y+1)）。

小结

方法 时间复杂度 说明
数学（gcd） O(log(min(x,y))) 面试首选，结论简洁优雅
BFS O(x*y) 通用搜索思路，便于理解

易错点：

· z > x + y 直接返回 false
· x == 0 && y == 0 时 gcd 为 0 会导致除零，需要特判
· z == 0 恒为 true（初始即为 0 升）