一、題目描述
- Alice 和 Bob 再次設計了一款新的石子游戲，現有一行 n 個石子，每個石子都有一個關聯的數字表示它的價值，給你一個整數陣列 stones ，其中 stones[i] 是第 i 個石子的價值，
- Alice 和 Bob 輪流進行自己的回合，Alice 先手，每一回合，玩家需要從 stones 中移除任一石子，
-
- 如果玩家移除石子后，導致所有已移除石子的價值總和可以被 3 整除，那么該玩家就輸掉游戲；
-
- 如果不滿足上一條，且移除后沒有任何剩余的石子，那么 Bob 將會直接獲勝（即便是在 Alice 的回合），
- 假設兩位玩家均采用最佳決策，如果 Alice 獲勝，回傳 true；如果 Bob 獲勝，回傳 false，
- 示例 1：
輸入：stones = [2,1]
輸出：true
解釋：游戲進行如下：
- 回合 1：Alice 可以移除任意一個石子，
- 回合 2：Bob 移除剩下的石子，
已移除的石子的值總和為 1 + 2 = 3 且可以被 3 整除，因此，Bob 輸，Alice 獲勝，
- 示例 2：
輸入：stones = [2]
輸出：false
解釋：Alice 會移除唯一一個石子，已移除石子的值總和為 2 ，
由于所有石子都已移除，且值總和無法被 3 整除，Bob 獲勝，
- 示例 3：
輸入：stones = [5,1,2,4,3]
輸出：false
解釋：Bob 總會獲勝，其中一種可能的游戲進行方式如下：
- 回合 1：Alice 可以移除值為 1 的第 2 個石子，已移除石子值總和為 1 ，
- 回合 2：Bob 可以移除值為 3 的第 5 個石子，已移除石子值總和為 = 1 + 3 = 4 ，
- 回合 3：Alices 可以移除值為 4 的第 4 個石子，已移除石子值總和為 = 1 + 3 + 4 = 8 ，
- 回合 4：Bob 可以移除值為 2 的第 3 個石子，已移除石子值總和為 = 1 + 3 + 4 + 2 = 10.
- 回合 5：Alice 可以移除值為 5 的第 1 個石子，已移除石子值總和為 = 1 + 3 + 4 + 2 + 5 = 15.
Alice 輸掉游戲，因為已移除石子值總和（15）可以被 3 整除，Bob 獲勝，
二、求解演算法：構造移除序列，計算回合數
- 由于只關心總和能否被 3 整除，我們可以將 stones 按照模 3 的結果分為 3 組，即 0、1 和 2，
- 根據題意，第一回合不能移除 0，否則直接輸掉游戲，因此第一回合只能移除 1 或者 2，可以列舉這兩種情況，如果其中一種可以讓 Alice 獲勝就回傳 true，否則回傳 false，
- 下面以第一回合移除 1 來說明，在不考慮移除 0 的前提下，后面的移除由于要滿足總和不能被 3 整除，因此移除的石子是固定的，整體構成一個 112121212… 回圈的序列，
- 對于 0，由于移除之后不會改變總和模 3 的結果，因此不會改變后續 1 和 2 的移除順序，所以可以在序列的任意非開頭位置插入 0，
- 兩人為了不讓自己輸掉，必然會按照上述序列進行，直到沒有石子，或某一方只能移除導致總和被 3 整除的石子時分出勝負，因此需要求出讓總和不能被 3 整除的最大的回合數，這相當于 112121212… 序列的最長長度，加上 0 的個數，
- 若該回合數為奇數，且還有剩余石子，那么下一回合要輪到 Bob 移除石子，且他只能移除一枚讓總和被 3 整除的石子，于是 Alice 獲勝；否則 Bob 獲勝，
- 對于第一回合移除 2 的情況，同樣會構成一個 221212121… 回圈的序列，做法同上，
- 演算法示例如下：
func check(c [3]int) bool {
if c[1] == 0 {
return false
}
c[1]-- // 開頭為 1
turn := 1 + min(c[1], c[2])*2 + c[0] // 計算回合數
if c[1] > c[2] { // 序列末尾可以再加個 1
turn++
c[1]--
}
return turn%2 == 1 && c[1] != c[2] // 回合數為奇數，且還有剩余石子
}
func stoneGameIX(stones []int) bool {
c := [3]int{}
for _, v := range stones {
c[v%3]++
}
return check(c) || check([3]int{c[0], c[2], c[1]}) // 列舉第一回合移除的是 1 還是 2
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
- 注意到對于回合數，只需考慮其奇偶性，因此可以去掉恒為偶數的 min(c[1], c[2])*2，然后按照 c[0] 的奇偶性分類討論：
-
- 若 c[0] 為偶數，要使回合數為奇數，c[1] > c[2] 必須不成立，可以選擇 c[1] 和 c[2] 中的較小值當作第一回合移除的石子，這樣做除了讓 c[1] > c[2] 不成立外，由于 c[1]-- 的緣故，還可以使 c[1] != c[2] 成立，因此在 c[0] 為偶數的情況下，需要滿足 min(c[1],c[2])>0，即 c[1]>0 且 c[2]>0 時 Alice 才可以獲勝；
-
- 若 c[0] 為奇數，要使回合數為奇數，c[1] > c[2] 必須成立，在執行了兩次 c[1]-- 后，由于要滿足最后的 c[1] != c[2]，相當于在初始時滿足 c[1] - 2 > c[2]，因此在 c[0] 為奇數的情況下，需要滿足 c[1]?2>c[2] 或 c[2]?2>c[1] 時 Alice 才可以獲勝，
func stoneGameIX(stones []int) bool {
c := [3]int{}
for _, v := range stones {
c[v%3]++
}
if c[0]%2 == 0 {
return c[1] > 0 && c[2] > 0 // min(c[1], c[2]) > 0
}
return c[1]-2 > c[2] || c[2]-2 > c[1]
}
三、博客之星
- 今年是我第一次參加博客之星，需要各位大佬的支持，麻煩百忙之中，抽出一點寶貴的時間，給我投一下票：https://bbs.csdn.net/topics/603955258 給我一個五星（串列會一一全部回復），不勝感激！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/402565.html
標籤：其他
上一篇：【投石問路】Unity內置管線升級URP之色彩空間（伽馬、sRGB、Gamma Space和Linear Space）