共计 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
具体算法:
- 用哈希表存储手上的球的品种和个数,这么做是为了前面 疾速判断间断的球是否能够被打消。因为题目限度手上求不会超过 5,因而哈希表的最大容量就是 5,能够认为这是一个常数的空间。
- 回溯。
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 啦。
大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。