LeetCode 365. 水壺問題題意有兩個(gè)水壺容量分別為 x 和 y 升。允許以下操作· 裝滿任意一個(gè)水壺· 倒空任意一個(gè)水壺· 將一個(gè)水壺的水倒入另一個(gè)直到源壺空或目標(biāo)壺滿判斷能否恰好量出 z 升水。思路一數(shù)學(xué)裴蜀定理 / Bézout’s Identity?推薦關(guān)鍵結(jié)論能得到的任意水量一定是 gcd(x, y) 的倍數(shù)。· 因?yàn)槊恳徊讲僮髦簧婕凹?減 x 或 y相當(dāng)于在求 ax by 的線性組合。· 由裴蜀定理ax by 能取到的所有值恰好是 gcd(x, y) 的倍數(shù)。因此判定條件z x y水總量上限z 能被 gcd(x, y) 整除classSolution{publicbooleancanMeasureWater(intx,inty,intz){// 水量超過兩壺總?cè)萘坎豢赡躨f(zxy)returnfalse;// 兩壺容量都為 0 時(shí)只能量出 0if(x0y0)returnz0;// 目標(biāo)必須是 gcd(x, y) 的倍數(shù)returnz%gcd(x,y)0;}privateintgcd(inta,intb){while(b!0){intta%b;ab;bt;}returna;}}復(fù)雜度時(shí)間 O(log(min(x, y)))空間 O(1)。思路二BFS狀態(tài)搜索把 (a, b) 看作狀態(tài)a、b 為兩壺當(dāng)前水量從 (0,0) 出發(fā)做 BFS看是否到達(dá)某個(gè)狀態(tài)滿足 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;// 六種操作得到的所有可能的下一個(gè)狀態(tài)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;}}復(fù)雜度時(shí)間/空間 O(x * y)狀態(tài)數(shù)最多為 (x1)(y1)。小結(jié)方法 時(shí)間復(fù)雜度 說明數(shù)學(xué)gcd O(log(min(x,y))) 面試首選結(jié)論簡潔優(yōu)雅BFS O(x*y) 通用搜索思路便于理解易錯(cuò)點(diǎn)· z x y 直接返回 false· x 0 y 0 時(shí) gcd 為 0 會(huì)導(dǎo)致除零需要特判· z 0 恒為 true初始即為 0 升