百度的算法面試題 * 祖瑪游戲 · ttttt

# 百度的算法面試題 \* 祖瑪游戲 # 百度的算法面試題 - 祖瑪游戲這是一道百度的算法面試題，讓我來拷拷你~。 ## 題目地址（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 = 0 while i < len(board): j = i + 1 while j < len(board) and board[i] == board[j]: j += 1 # 其他邏輯 # 更新左指針 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">``` class Solution: def findMinStep(self, board: str, hand: str) -> int: def backtrack(board): if not board: return 0 i = 0 ans = 6 while i < len(board): j = i + 1 while j < len(board) and board[i] == board[j]: j += 1 balls = 3 - (j - i) if counter[board[i]] >= balls: balls = max(0, balls) counter[board[i]] -= balls ans = min(ans, balls + backtrack(board[:i] + board[j:])) counter[board[i]] += balls i = j return ans counter = collections.Counter(hand) ans = backtrack(board) return -1 if ans > 5 else 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)