遊戲互動題 移除顏色相同的字卡 Leetcode #2038

閱讀時間約 6 分鐘
raw-image

這題的題目在這裡

題目敘述

題目會給定我們一個輸入陣列,裡面的字母A和字母B分別代表兩種顏色的卡片。

假如某張卡片的左右都是相同的,例如AAA,Alice可以抽掉中間那張A。

同樣的,假如某張卡片的左右都是相同的,例如BBB,Bob可以抽掉中間那張B。

請問Alice和Bob輪流玩抽卡遊戲,每回合都用最優解的方式去玩。Alice和Bob輪流各抽一張卡片,Alice先手。
假如輪到某個回合,已經無法再抽出卡牌,則當下這個玩家就輸了。

請問最後是誰贏?
如果Alice贏的話回傳True,如果是Bob贏回傳False。


測試範例

Example 1:

Input: colors = "AAABABB"
Output: true
Explanation:
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.

Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.

Example 2:

Input: colors = "AA"
Output: false
Explanation:
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.

Example 3:

Input: colors = "ABBBBBBBAAA"
Output: false
Explanation:
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.

ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.

On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.



約束條件

Constraints:

  • 1 <= colors.length <= 105
  • colors consists of only the letters 'A' and 'B'

演算法

其實仔細模擬幾個範例之後可以發現,Alice和Bob的局面在開局後就固定下來,勝負已知,而且彼此的操作不影響對方

為什麼?

下文中的'這著記號只是為了向讀者說明抽了哪張卡片,其實還是原本的顏色。

比如說
AA'ABBBAA
這局Alice抽掉左方的A'之後變成

AABB'BAA
這局再換Bob抽掉中間的B',之後變成

AABBAA
此時Alice 無法再操作,判定Bob獲勝。Bob上一局也無法讓Alice左右兩側的AA和AA互相串連成更大一組的AAAA。

其他的例子也是,開局時的A、B分布已經固定,之後兩個玩家的操作已經無法改變局面。

關鍵就在於AAA和BBB總共有多少個,如果AAA的數目比BBB還多,那麼Alice最後必勝。反之,就是Bob必勝。


程式碼

class Solution:
 def winnerOfGame(self, colors: str) -> bool:
  
  n = len(colors)

  # number of pieces alice can take
  # number of pieces bob bob can take
  alice, bob = 0, 0

  for i in range(1, n-1):

   if colors[i-1] == colors[i] and colors[i] == colors[i+1]:

    if colors[i] == "A":
     alice += 1
    
    else:
     bob += 1

  # Judge whether Alice can win or not
  return alice > bob
   



複雜度分析

時間複雜度:

O( n ) 從左到右掃描一次,掃描並且計算AAA和BBB的總數目。

空間複雜度:

O(1) 只有使用固定的臨時變數,所耗費的記憶體空間為常數級別O(1)


關鍵知識點

這題的關鍵在於先模擬幾個小範例,發現局面在開局已經固定,勝負已分,之後的抽卡操作並不影響勝負局面

關鍵在於AAA和BBB的總數。

如果 AAA的數目 > BBB的數目,代表Alice每次可以從AAA抽走一張A,相對的Bob能抽B的次數比較少,兩人輪流,一定是Bob先走到死局,所以Alice必勝。

有點類似腦筋急轉彎的題目,如果太早落入一定要使用DP動態規劃,或者Greedy貪心法的先入為主刻板印象,反而落入陷阱。


Reference:

[1] Python O(n) by pattern scan - Remove Colored Pieces if Both Neighbors are the Same Color - LeetCode

avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目給定一個輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目會給定兩個參數,一個是底數x,一個是次方n。要求我們計算出x^n。 要求實作myPow(self, x: float, n: int) -> float 函數的內部邏輯。 也就是說,不可以呼叫程式語言內建計算指數的library
1. 競賽題 或者 面試題 Medium Hard 以上題目,一開始在第一時間想不出解題思路,或者最佳解是很平常的事情。 通過官方解答、討論區的高手分享解題,進而學到新的解題思路,或者更泛用的演算法框架,就是最大的收穫。 2. 但是Easy分類的題目,通常就是該領域最基礎的題目,應該要
題目會給定我們一個陣列,要求我們找出裡面出現次數最多的數字。 出現次數最多的數字也就是我們在統計上所謂的 眾數 mode
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目給定一個輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目會給定兩個參數,一個是底數x,一個是次方n。要求我們計算出x^n。 要求實作myPow(self, x: float, n: int) -> float 函數的內部邏輯。 也就是說,不可以呼叫程式語言內建計算指數的library
1. 競賽題 或者 面試題 Medium Hard 以上題目,一開始在第一時間想不出解題思路,或者最佳解是很平常的事情。 通過官方解答、討論區的高手分享解題,進而學到新的解題思路,或者更泛用的演算法框架,就是最大的收穫。 2. 但是Easy分類的題目,通常就是該領域最基礎的題目,應該要
題目會給定我們一個陣列,要求我們找出裡面出現次數最多的數字。 出現次數最多的數字也就是我們在統計上所謂的 眾數 mode
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
你可能也想看
Google News 追蹤
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
分享一個猜數字的遊戲題目,給予提示讓玩家找出正確的四位數密碼。
Thumbnail
本週桌遊活動再起,玩了三國殺、犯人在跳舞、UNO疊疊樂、推倒提基、誰是內鬼、奶烙大盜......等。歡樂整個早上。 這些桌遊有些是歡樂的、是派對的,有些是邏輯推理思考的。這一團孩子比較大一點,可以玩些比較難的桌遊,所以就推了不少邏輯思考的桌遊。 看她們的思維還不錯,推了一款很新的桌遊-
Thumbnail
C同學說想玩撲克牌遊戲。於是,昨夜大家都洗完澡後,到我們帳篷集合開打。 剛開始她拿出一幅陌生的紙牌桌遊,兩個年輕人把兩個老人家電的慘兮兮。她們在學校就玩過的,反應也比我們夫妻快多了,為了挽回自信心,我建議玩一般撲克牌裡,“大老二遊戲”。
Thumbnail
謎題由模式組合而成,是用來破解的,永遠都有預定的秩序,永遠都有明確的答案。憑藉技巧和堅持的精神,一定能把謎題填完。遊戲的輸贏常常是靠運氣和隨機的環境,有偶然的成分,就算擁有全世界的天賦和決心,也未必能在遊戲中取勝。兩者有極大的差異。
Thumbnail
飛行棋 紅、黃、藍及綠色的棋子各四顆將紅=英國領 空、黃=法國、藍=中華民國、綠=美國骰子一個 傳統玩法 ·兩至四人,輪流擲骰子。 •輪至自己時,擲骰子開始,擲到6時才可以「起 飛」(部分版本擲到偶數(即2、4、6)便可起飛)把自己其中一顆棋放到「起飛」處。下一次再擲 便可按骰
Thumbnail
這是一款考驗眼力的與反應力的卡牌遊戲,每張卡牌都有數種圖案,然後兩張卡片中一定會有一個圖案相同,這款遊戲的目的就是要找到卡牌中相同的圖案是哪一個,市面上有許多類似的桌遊。 就像下面範例兩張一組的卡片中,找出相同的圖案 第一組:閃電 第二組:貓咪 第三組:烏龜 看這個範例感覺很簡單,其實
Thumbnail
團體生活,如何追求「公平」。 最令學生心服口服的,大概,勉強,就是「抽籤」決定了! 但我一直覺得這有一點點瞎, 但也是沒有辦法中的辦法了吧?! 聽聞某班, 凡事皆以抽籤解決, 抽籤決定座位、 抽籤決定整潔工作、 抽籤決定幹部、 抽籤決定各項班際競賽派誰上場? 抽籤決定誰當
02/20/2021 妙語說書人   妙語說書人,不是遊戲,而是回憶。   妙語說書人是個規則很簡單的桌遊。 由說書人暗打出一張卡片,並用一個詞來描述卡片的內容。 其餘參加者再依據描述,就手上所有的卡片,找出一張最符合描述的,暗打出來。 說書人再將自己和參加者們的卡片混合在一起,翻開
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
分享一個猜數字的遊戲題目,給予提示讓玩家找出正確的四位數密碼。
Thumbnail
本週桌遊活動再起,玩了三國殺、犯人在跳舞、UNO疊疊樂、推倒提基、誰是內鬼、奶烙大盜......等。歡樂整個早上。 這些桌遊有些是歡樂的、是派對的,有些是邏輯推理思考的。這一團孩子比較大一點,可以玩些比較難的桌遊,所以就推了不少邏輯思考的桌遊。 看她們的思維還不錯,推了一款很新的桌遊-
Thumbnail
C同學說想玩撲克牌遊戲。於是,昨夜大家都洗完澡後,到我們帳篷集合開打。 剛開始她拿出一幅陌生的紙牌桌遊,兩個年輕人把兩個老人家電的慘兮兮。她們在學校就玩過的,反應也比我們夫妻快多了,為了挽回自信心,我建議玩一般撲克牌裡,“大老二遊戲”。
Thumbnail
謎題由模式組合而成,是用來破解的,永遠都有預定的秩序,永遠都有明確的答案。憑藉技巧和堅持的精神,一定能把謎題填完。遊戲的輸贏常常是靠運氣和隨機的環境,有偶然的成分,就算擁有全世界的天賦和決心,也未必能在遊戲中取勝。兩者有極大的差異。
Thumbnail
飛行棋 紅、黃、藍及綠色的棋子各四顆將紅=英國領 空、黃=法國、藍=中華民國、綠=美國骰子一個 傳統玩法 ·兩至四人,輪流擲骰子。 •輪至自己時,擲骰子開始,擲到6時才可以「起 飛」(部分版本擲到偶數(即2、4、6)便可起飛)把自己其中一顆棋放到「起飛」處。下一次再擲 便可按骰
Thumbnail
這是一款考驗眼力的與反應力的卡牌遊戲,每張卡牌都有數種圖案,然後兩張卡片中一定會有一個圖案相同,這款遊戲的目的就是要找到卡牌中相同的圖案是哪一個,市面上有許多類似的桌遊。 就像下面範例兩張一組的卡片中,找出相同的圖案 第一組:閃電 第二組:貓咪 第三組:烏龜 看這個範例感覺很簡單,其實
Thumbnail
團體生活,如何追求「公平」。 最令學生心服口服的,大概,勉強,就是「抽籤」決定了! 但我一直覺得這有一點點瞎, 但也是沒有辦法中的辦法了吧?! 聽聞某班, 凡事皆以抽籤解決, 抽籤決定座位、 抽籤決定整潔工作、 抽籤決定幹部、 抽籤決定各項班際競賽派誰上場? 抽籤決定誰當
02/20/2021 妙語說書人   妙語說書人,不是遊戲,而是回憶。   妙語說書人是個規則很簡單的桌遊。 由說書人暗打出一張卡片,並用一個詞來描述卡片的內容。 其餘參加者再依據描述,就手上所有的卡片,找出一張最符合描述的,暗打出來。 說書人再將自己和參加者們的卡片混合在一起,翻開