遊戲互動題 移除顏色相同的字卡 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
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
題目敘述 給定一個piles陣列,裡面對應到每堆石頭的數量。 Alice 和 Bob玩輪流取石頭的遊戲,總共有n堆石頭,每堆的石頭數量有多有少。 Alice先取,接著Bob,反覆交替,每回合輪到的人可以從當下的第一堆或者最後一堆,拿走那堆對應的石頭。 最後比誰拿到的石頭總數量比較多就獲勝。
Thumbnail
題目敘述 給定一個piles陣列,裡面對應到每堆石頭的數量。 Alice 和 Bob玩輪流取石頭的遊戲,總共有n堆石頭,每堆的石頭數量有多有少。 Alice先取,接著Bob,反覆交替,每回合輪到的人可以從當下的第一堆或者最後一堆,拿走那堆對應的石頭。 最後比誰拿到的石頭總數量比較多就獲勝。
Thumbnail
題目敘述 題目會給定我們一個比賽紀錄陣列matches,裡面以pair的方式儲存,每個pair的第一個欄位代表這場比賽的贏家ID,第二個欄位代表這場比賽的輸家ID。 題目要求我們找出所有沒有輸的玩家ID,和只輸一場的玩家ID。 計算時,只考慮有比賽紀錄的玩家。 輸出時,依照遊戲玩家的ID,從
Thumbnail
題目敘述 題目會給定我們一個比賽紀錄陣列matches,裡面以pair的方式儲存,每個pair的第一個欄位代表這場比賽的贏家ID,第二個欄位代表這場比賽的輸家ID。 題目要求我們找出所有沒有輸的玩家ID,和只輸一場的玩家ID。 計算時,只考慮有比賽紀錄的玩家。 輸出時,依照遊戲玩家的ID,從
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,
Thumbnail
題目會給們一個陣列,還有一個k值。 接著進行比大小的遊戲,規則如下: 每次取陣列前兩個元素值比大小,比較小的會被重新安排到陣列最後方,陣列前兩個元素值比大小,同樣的,比較小的會被重新安排到陣列最後方。依此類推,反覆進行比大小的遊戲。 請問第一個能連贏k回合的是哪個數字?
Thumbnail
題目會給們一個陣列,還有一個k值。 接著進行比大小的遊戲,規則如下: 每次取陣列前兩個元素值比大小,比較小的會被重新安排到陣列最後方,陣列前兩個元素值比大小,同樣的,比較小的會被重新安排到陣列最後方。依此類推,反覆進行比大小的遊戲。 請問第一個能連贏k回合的是哪個數字?
Thumbnail
題目會給定兩個字串s,t,把裡面的井字號#視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部依照規則處理完以後,s,t剩下的字串內容兩者是否相等?
Thumbnail
題目會給定兩個字串s,t,把裡面的井字號#視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部依照規則處理完以後,s,t剩下的字串內容兩者是否相等?
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目會給定我們一個輸入陣列,裡面的字母A和字母B分別代表兩種顏色的卡片。 假如某張卡片的左右都是相同的,例如AAA,Alice可以抽掉中間那張A。 同樣的,假如某張卡片的左右都是相同的,例如BBB,Bob可以抽掉中間那張B。 請問Alice和Bob輪流玩抽卡遊戲, 請問最後是誰贏?
Thumbnail
題目會給定我們一個輸入陣列,裡面的字母A和字母B分別代表兩種顏色的卡片。 假如某張卡片的左右都是相同的,例如AAA,Alice可以抽掉中間那張A。 同樣的,假如某張卡片的左右都是相同的,例如BBB,Bob可以抽掉中間那張B。 請問Alice和Bob輪流玩抽卡遊戲, 請問最後是誰贏?
Thumbnail
雖然表面是一道移除元素的題目,但實際上考的還是搬移。 題目要求的是把val目標值移除,等價於 把非目標值的搬到前面,並且回傳這些剩下來的元素個數(也就是 陣列裡面,非目標值的元素總數​)。 請看下方範例,會更好理解。
Thumbnail
雖然表面是一道移除元素的題目,但實際上考的還是搬移。 題目要求的是把val目標值移除,等價於 把非目標值的搬到前面,並且回傳這些剩下來的元素個數(也就是 陣列裡面,非目標值的元素總數​)。 請看下方範例,會更好理解。
Thumbnail
題目給定兩個字串s和t,t是s隨機打散後的字串,並且在t裡面額外多加了一個字元, 要求我們找出額外多加入的那個字元。
Thumbnail
題目給定兩個字串s和t,t是s隨機打散後的字串,並且在t裡面額外多加了一個字元, 要求我們找出額外多加入的那個字元。
Thumbnail
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
Thumbnail
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News