<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>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 百度的算法面試題 \* 祖瑪游戲 # 百度的算法面試題 - 祖瑪游戲 這是一道百度的算法面試題, 讓我來拷拷你~。 ## 題目地址(488. 祖瑪游戲) <https://leetcode-cn.com/problems/zuma-game/> ## 題目描述 ``` <pre class="calibre18">``` 回憶一下祖瑪游戲。現在桌上有一串球,顏色有紅色(R),黃色(Y),藍色(B),綠色(G),還有白色(W)。 現在你手里也有幾個球。 每一次,你可以從手里的球選一個,然后把這個球插入到一串球中的某個位置上(包括最左端,最右端)。接著,如果有出現三個或者三個以上顏色相同的球相連的話,就把它們移除掉。重復這一步驟直到桌上所有的球都被移除。 找到插入并可以移除掉桌上所有球所需的最少的球數。如果不能移除桌上所有的球,輸出 -1 。 示例: 輸入: "WRRBBW", "RB" 輸出: -1 解釋: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW (翻譯者標注:手上球已經用完,桌上還剩兩個球無法消除,返回-1) 輸入: "WWRRBBWW", "WRBRW" 輸出: 2 解釋: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty 輸入:"G", "GGGGG" 輸出: 2 解釋: G -> G[G] -> GG[G] -> empty 輸入: "RBYYBBRRB", "YRBGB" 輸出: 3 解釋: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty 標注: 你可以假設桌上一開始的球中,不會有三個及三個以上顏色相同且連著的球。 桌上的球不會超過20個,輸入的數據中代表這些球的字符串的名字是 "board" 。 你手中的球不會超過5個,輸入的數據中代表這些球的字符串的名字是 "hand"。 輸入的兩個字符串均為非空字符串,且只包含字符 'R','Y','B','G','W'。 ``` ``` ## 前置知識 - 回溯 - 哈希表 - 雙指針 ## 公司 - 百度 ## 思路 面試題困難難度的題目常見的題型有: - DP - 設計題 - 圖 - 游戲 本題就是游戲類題目。 如果你是一個前端, 說不定還會考察你如何實現一個 zuma 游戲。這種游戲類的題目,可以簡單可以困難, 比如力扣經典的石子游戲,寶石游戲等。這類題目沒有固定的解法。我做這種題目的思路就是先暴力模擬,再嘗試優化算法瓶頸。 注意下數據范圍球的數目 <= 5,因此暴力法就變得可行。基本思路是暴力枚舉手上的球可以消除的地方, 我們可以使用回溯法來完成暴力枚舉的過程,在回溯過程記錄最小值即可。由于回溯樹的深度不會超過 5,因此這種解法應該可以 AC。 上面提到的`可以消除的地方`,指的是**連續相同顏色 + 手上相同顏色的球大于等于 3**,這也是題目說明的消除條件。 因此我們只需要兩個指針記錄連續相同顏色球的位置,如果可以消除,消除即可。 ![](https://img.kancloud.cn/cd/2a/cd2a0e2ef76c44e4ccf060a9f9114fb2_1586x571.jpg) 如圖,我們記錄了連續紅球的位置, 如果手上有紅球, 則可以嘗試將其清除,這一次決策就是回溯樹(決策樹)的一個分支。之后我們會撤回到這個決策分支, 嘗試其他可行的決策分支。 以 board = RRBBRR , hand 為 RRBB 為例,其決策樹為: ![](https://img.kancloud.cn/20/62/20620858c36257ece91bd57b38c2b137_1080x1164.jpg) 其中虛線表示無需手動干預,系統自動消除。葉子節點末尾的黃色表示全部消除需要的手球個數。路徑上的文字后面的數字表示此次消除需要的手球個數 > 如果你對回溯不熟悉,可以參考下我之前寫的幾篇題解:比如 [46.permutations](https://github.com/azl397985856/leetcode/blob/master/problems/46.permutations.md "46.permutations")。 可以看出, 如果選擇先消除中間的藍色,則只需要一步即可完成。 關于計算連續球位置的核心代碼(Python3): ``` <pre class="calibre18">``` i = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i < len(board): j = i + <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j < len(board) <span class="hljs-keyword">and</span> board[i] == board[j]: j += <span class="hljs-params">1</span> <span class="hljs-title"># 其他邏輯</span> <span class="hljs-title"># 更新左指針</span> i = j ``` ``` ![](https://img.kancloud.cn/f3/ac/f3ac261cf95b9fa01ca192df4fe4b035_1526x826.jpg) 具體算法: 1. 用哈希表存儲手上的球的種類和個數,這么做是為了后面**快速判斷連續的球是否可以被消除**。由于題目限制手上求不會超過 5,因此哈希表的最大容量就是 5,可以認為這是一個常數的空間。 2. 回溯。 2.1 確認可以消除的位置,算法參考上面的代碼。 2.2 判斷手上是否有足夠相同顏色的球可以消除。 2.3 回溯的過程記錄全局最小值。 ## 代碼 代碼支持:Python3 Python3 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">findMinStep</span><span class="hljs-params">(self, board: str, hand: str)</span> -> int:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">backtrack</span><span class="hljs-params">(board)</span>:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> board: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> i = <span class="hljs-params">0</span> ans = <span class="hljs-params">6</span> <span class="hljs-keyword">while</span> i < len(board): j = i + <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j < len(board) <span class="hljs-keyword">and</span> board[i] == board[j]: j += <span class="hljs-params">1</span> balls = <span class="hljs-params">3</span> - (j - i) <span class="hljs-keyword">if</span> counter[board[i]] >= balls: balls = max(<span class="hljs-params">0</span>, balls) counter[board[i]] -= balls ans = min(ans, balls + backtrack(board[:i] + board[j:])) counter[board[i]] += balls i = j <span class="hljs-keyword">return</span> ans counter = collections.Counter(hand) ans = backtrack(board) <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span> <span class="hljs-keyword">if</span> ans > <span class="hljs-params">5</span> <span class="hljs-keyword">else</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(2(min(C,5)))O(2^(min(C, 5)))O(2(min(C,5))),其中 C 為連續相同顏色球的次數,比如 WWRRRR, C 就是 2, WRBDD, C 就是 4。min(C, 5) 是因為題目限定了手上球的個數不大于 5。 - 空間復雜度:O(min(C,5)?Board)O(min(C, 5) \* Board)O(min(C,5)?Board),其中 C 為連續相同顏色球的次數,Board 為 Board 的長度。 ## 關鍵點解析 - 回溯模板 - 雙指針寫法 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 36K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.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>

                              哎呀哎呀视频在线观看