題目描述: Alice 和 Bob 輪流從石子堆中取石子(Alice 先手)。每次取一顆石子後,若已取石子的總和能被 3 整除,則取該石子的玩家輸。若所有石子都取完仍無人輸,則 Alice 輸。判斷 Alice 是否能在雙方都最優策略下獲勝。
解題思路: 關鍵觀察是我們只需關注每顆石子對 3 的餘數(0、1、2)。設 c0、c1、c2 分別為餘數為 0、1、2 的石子數量。
時間複雜度:O(n) — 遍歷一次陣列統計每個餘數的數量。
空間複雜度:O(1) — 只使用三個計數變數。
1. Count stones by remainder mod 3: c0, c1, c2. 2. If c1 == 0 and c2 == 0, return false (Alice loses). 3. If c1 == 0, return c2 > 2 and c0 is even. 4. If c2 == 0, return c1 > 2 and c0 is even. 5. If c0 is even, return c1 != c2. 6. If c0 is odd, return |c1 - c2| > 2.
模擬博弈法:用遞迴或動態規劃模擬所有可能的取石子順序,判斷勝負。時間複雜度 O(n!) 或使用記憶化搜索優化到 O(c0 * c1 * c2),但仍遠不如數學解法高效。
分類討論窮舉法:枚舉 Alice 第一步選擇(mod 1 或 mod 2),然後貪心模擬後續流程。每種起始選擇模擬 O(n) 次操作,總共 O(n)。這種方法更直觀但實現較冗長。