0365. 水壺問題 · ttttt

# 0365. 水壺問題 ## 題目地址(365. 水壺問題) <https://leetcode-cn.com/problems/water-and-jug-problem/> ## 題目描述 ``` <pre class="calibre18">``` 有兩個容量分別為 x升和 y升的水壺以及無限多的水。請判斷能否通過使用這兩個水壺，從而可以得到恰好 z升的水？如果可以，最后請用以上水壺中的一或兩個來盛放取得的 z升水。你允許：裝滿任意一個水壺清空任意一個水壺從一個水壺向另外一個水壺倒水，直到裝滿或者倒空示例 1: (From the famous "Die Hard" example) 輸入: x = 3, y = 5, z = 4 輸出: True 示例 2: 輸入: x = 2, y = 6, z = 5 輸出: False ``` ``` ## BFS（超時） ## 前置知識 - BFS - 最大公約數 ## 公司 - 阿里 - 百度 - 字節 ### 思路兩個水壺的水我們考慮成狀態，然后我們不斷進行倒的操作，改變狀態。那么初始狀態就是（0 0）目標狀態就是（any, z）或者 (z, any)，其中any 指的是任意升水。已題目的例子，其過程示意圖，其中括號表示其是由哪個狀態轉移過來的： 0 0 3 5(0 0) 3 0 (0 0 )0 5(0 0) 3 2(0 5) 0 3(0 0) 0 2(3 2) 2 0(0 2) 2 5(2 0) 3 4(2 5) bingo ### 代碼 ``` <pre class="calibre18">``` class Solution: def canMeasureWater(self, x: int, y: int, z: int) -> bool: if x + y < z: return False queue = [(0, 0)] seen = set((0, 0)) while(len(queue) > 0): a, b = queue.pop(0) if a ==z or b == z or a + b == z: return True states = set() states.add((x, b)) states.add((a, y)) states.add((0, b)) states.add((a, 0)) states.add((min(x, b + a), 0 if b < x - a else b - (x - a))) states.add((0 if a + b < y else a - (y - b), min(b + a, y))) for state in states: if state in seen: continue; queue.append(state) seen.add(state) return False ``` ``` **復雜度分析** - 時間復雜度：由于狀態最多有O((x+1)?(y+1))O((x + 1) \* (y + 1))O((x+1)?(y+1)) 種，因此總的時間復雜度為O(x?y)O(x \* y)O(x?y)。 - 空間復雜度：我們使用了隊列來存儲狀態，set 存儲已經訪問的元素，空間復雜度和狀態數目一致，因此空間復雜度是O(x?y)O(x \* y)O(x?y)。上面的思路很直觀，但是很遺憾這個算法在 LeetCode 的表現是 TLE(Time Limit Exceeded)。不過如果你能在真實面試中寫出這樣的算法，我相信大多數情況是可以過關的。我們來看一下有沒有別的解法。實際上，上面的算法就是一個標準的 BFS。如果從更深層次去看這道題，會發現這道題其實是一道純數學問題，類似的純數學問題在 LeetCode 中也會有一些，不過大多數這種題目，我們仍然可以采取其他方式 AC。那么讓我們來看一下如何用數學的方式來解這個題。 ## 數學法 - 最大公約數 ### 思路這是一道關于`數論`的題目，確切地說是關于`裴蜀定理`（英語：Bézout's identity）的題目。摘自wiki的定義： ``` <pre class="calibre18">``` 對任意兩個整數 a、b，設 d是它們的最大公約數。那么關于未知數 x和 y的線性丟番圖方程（稱為裴蜀等式）： ax+by=m 有整數解 (x,y) 當且僅當 m是 d的整數倍。裴蜀等式有解時必然有無窮多個解。 ``` ``` 因此這道題可以完全轉化為`裴蜀定理`。還是以題目給的例子`x = 3, y = 5, z = 4`，我們其實可以表示成`3 * 3 - 1 * 5 = 4`, 即`3 * x - 1 * y = z`。我們用a和b分別表示3 升的水壺和5升的水壺。那么我們可以： - 倒滿a（**1**） - 將a倒到b - 再次倒滿a（**2**） - 再次將a倒到b（a這個時候還剩下1升） - 倒空b（**-1**） - 將剩下的1升倒到b - 將a倒滿（**3**） - 將a倒到b - b此時正好是4升上面的過程就是`3 * x - 1 * y = z`的具體過程解釋。 **也就是說我們只需要求出x和y的最大公約數d，并判斷z是否是d的整數倍即可。** ### 代碼代碼支持：Python3，JavaScript Python Code： ``` <pre class="calibre18">``` class Solution: def canMeasureWater(self, x: int, y: int, z: int) -> bool: if x + y < z: return False if (z == 0): return True if (x == 0): return y == z if (y == 0): return x == z def GCD(a, b): smaller = min(a, b) while smaller: if a % smaller == 0 and b % smaller == 0: return smaller smaller -= 1 return z % GCD(x, y) == 0 ``` ``` JavaScript： ``` <pre class="calibre18">``` /** * @param {number} x * @param {number} y * @param {number} z * @return {boolean} */ var canMeasureWater = function(x, y, z) { if (x + y < z) return false; if (z === 0) return true; if (x === 0) return y === z; if (y === 0) return x === z; function GCD(a, b) { let min = Math.min(a, b); while (min) { if (a % min === 0 && b % min === 0) return min; min--; } return 1; } return z % GCD(x, y) === 0; }; ``` ``` 實際上求最大公約數還有更好的方式，比如輾轉相除法： ``` <pre class="calibre18">``` def GCD(a, b): if b == 0: return a return GCD(b, a % b) ``` ``` **復雜度分析** - 時間復雜度：O(log(max(a,b)))O(log(max(a, b)))O(log(max(a,b))) - 空間復雜度：空間復雜度取決于遞歸的深度，因此空間復雜度為 O(log(max(a,b)))O(log(max(a, b)))O(log(max(a,b))) ## 關鍵點分析 - 數論 - 裴蜀定理更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經接近30K star啦。大家也可以關注我的公眾號《腦洞前端》獲取更多更新鮮的LeetCode題解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg)