<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canMeasureWater</span><span class="hljs-params">(self, x: int, y: int, z: int)</span> -> bool:</span> <span class="hljs-keyword">if</span> x + y < z: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> queue = [(<span class="hljs-params">0</span>, <span class="hljs-params">0</span>)] seen = set((<span class="hljs-params">0</span>, <span class="hljs-params">0</span>)) <span class="hljs-keyword">while</span>(len(queue) > <span class="hljs-params">0</span>): a, b = queue.pop(<span class="hljs-params">0</span>) <span class="hljs-keyword">if</span> a ==z <span class="hljs-keyword">or</span> b == z <span class="hljs-keyword">or</span> a + b == z: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> states = set() states.add((x, b)) states.add((a, y)) states.add((<span class="hljs-params">0</span>, b)) states.add((a, <span class="hljs-params">0</span>)) states.add((min(x, b + a), <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> b < x - a <span class="hljs-keyword">else</span> b - (x - a))) states.add((<span class="hljs-params">0</span> <span class="hljs-keyword">if</span> a + b < y <span class="hljs-keyword">else</span> a - (y - b), min(b + a, y))) <span class="hljs-keyword">for</span> state <span class="hljs-keyword">in</span> states: <span class="hljs-keyword">if</span> state <span class="hljs-keyword">in</span> seen: <span class="hljs-keyword">continue</span>; queue.append(state) seen.add(state) <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> ``` ``` **復雜度分析** - 時間復雜度:由于狀態最多有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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canMeasureWater</span><span class="hljs-params">(self, x: int, y: int, z: int)</span> -> bool:</span> <span class="hljs-keyword">if</span> x + y < z: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">if</span> (z == <span class="hljs-params">0</span>): <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> (x == <span class="hljs-params">0</span>): <span class="hljs-keyword">return</span> y == z <span class="hljs-keyword">if</span> (y == <span class="hljs-params">0</span>): <span class="hljs-keyword">return</span> x == z <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">GCD</span><span class="hljs-params">(a, b)</span>:</span> smaller = min(a, b) <span class="hljs-keyword">while</span> smaller: <span class="hljs-keyword">if</span> a % smaller == <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> b % smaller == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> smaller smaller -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> z % GCD(x, y) == <span class="hljs-params">0</span> ``` ``` JavaScript: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number} x * @param {number} y * @param {number} z * @return {boolean} */</span> <span class="hljs-keyword">var</span> canMeasureWater = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">x, y, z</span>) </span>{ <span class="hljs-keyword">if</span> (x + y < z) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> (z === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span> (x === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> y === z; <span class="hljs-keyword">if</span> (y === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> x === z; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">GCD</span>(<span class="hljs-params">a, b</span>) </span>{ <span class="hljs-keyword">let</span> min = <span class="hljs-params">Math</span>.min(a, b); <span class="hljs-keyword">while</span> (min) { <span class="hljs-keyword">if</span> (a % min === <span class="hljs-params">0</span> && b % min === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> min; min--; } <span class="hljs-keyword">return</span> <span class="hljs-params">1</span>; } <span class="hljs-keyword">return</span> z % GCD(x, y) === <span class="hljs-params">0</span>; }; ``` ``` 實際上求最大公約數還有更好的方式,比如輾轉相除法: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">GCD</span><span class="hljs-params">(a, b)</span>:</span> <span class="hljs-keyword">if</span> b == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> a <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看