乐趣区

关于算法:面试官祖玛游戏玩过么我来拷拷你

jiezi

题目地址（488. 祖玛游戏）

https://leetcode-cn.com/probl…

题目形容

回顾一下祖玛游戏。当初桌上有一串球，色彩有红色(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，这也是题目阐明的打消条件。

因而咱们只须要两个指针记录间断雷同色彩球的地位，如果能够打消，打消即可。

如图，咱们记录了间断红球的地位，如果手上有红球，则能够尝试将其革除，这一次决策就是回溯树（决策树）的一个分支。之后咱们会撤回到这个决策分支，尝试其余可行的决策分支。

以 board = RRBBRR，hand 为 RRBB 为例，其决策树为：

其中虚线示意无需手动干涉，零碎主动打消。叶子节点开端的黄色示意全副打消须要的手球个数。门路上的文字前面的数字示意此次打消须要的手球个数

如果你对回溯不相熟，能够参考下我之前写的几篇题解：比方 46.permutations。

能够看出，如果抉择先打消两头的蓝色，则只须要一步即可实现。

对于计算间断球地位的外围代码(Python3):

i = 0
while i < len(board):
    j = i + 1
    while j < len(board) and board[i] == board[j]: j += 1
    # 其余逻辑

    # 更新左指针
    i = j

具体算法：

  1. 用哈希表存储手上的球的品种和个数，这么做是为了前面 疾速判断间断的球是否能够被打消。因为题目限度手上求不会超过 5，因而哈希表的最大容量就是 5，能够认为这是一个常数的空间。
  2. 回溯。

    2.1 确认能够打消的地位，算法参考下面的代码。

    2.2 判断手上是否有足够雷同色彩的球能够打消。

    2.3 回溯的过程记录全局最小值。

代码

代码反对：Python3

Python3 Code:

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)))$，其中 C 为间断雷同色彩球的次数，比方 WWRRRR，C 就是 2，WRBDD，C 就是 4。min(C, 5) 是因为题目限定了手上球的个数不大于 5。
  • 空间复杂度：$O(min(C, 5) * Board)$，其中 C 为间断雷同色彩球的次数，Board 为 Board 的长度。

关键点解析

  • 回溯模板
  • 双指针写法

大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858…。目前曾经 36K star 啦。
大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

退出移动版