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

32次阅读

共计 2321 个字符,预计需要花费 6 分钟才能阅读完成。

题目地址(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 啦。
大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

正文完
 0