iT邦幫忙

2024 iThome 鐵人賽

DAY 14
0

Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.

Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice's turn).

Assuming both players play optimally, return true if Alice wins and false if Bob wins.


題目表示Alice和Bob(以下簡稱A和B)在玩一個遊戲:

  1. A先開始移除石頭。
  2. 玩家可以從中移除任意一顆石頭。
  3. 如果移除石頭的總和可以被3整除,移除這顆石頭的玩家將輸掉。
  4. 如果所有石頭都移除完畢,B獲勝。
    我們需要判斷A是否有辦法獲勝,可以的話返回true,否則返回false。
  • A要獲勝的關鍵在於他可以強迫B在下一步選擇的任何石頭都導致總和為3的倍數。
  • 而A必敗的情況則是當前只有剩一顆可以被3整除的石頭給A選。
  • A在奇數回合行動;B在偶數回合行動。

我的解題思路是
0.因為玩家可以隨意選擇石頭,所以遍歷所有可能性會很暴力...要另尋他方!!

  1. 把石頭依照除以3後的餘數分成三種(餘數為0或1或2)
  2. 統計石頭餘數
  3. 餘數為0的石頭可以直接對勝負造成影響
  4. 當餘數為0的石頭數量是偶數,代表它們對結果的影響可抵銷
    4-1. A只要餘1和餘2的石頭數量不為0就能赢。
  5. 當餘數為0的石頭數量是奇數......
    5-1.經過我多次模擬後,如果餘0是奇數,而且餘1和餘2的石頭數量差超過2,B就會贏
    5-2.餘1和餘2的石頭數量差是偶數,B也會贏

class Solution {
    public boolean stoneGameIX(int[] stones) {
        int c0 = 0, c1 = 0, c2 = 0;
        
        // 計算各個餘數的石頭個數
        for (int stone : stones) {
            if (stone % 3 == 0) {
                c0++;
            } else if (stone % 3 == 1) {
                c1++;
            } else {
                c2++;
            }
        }
        
        // 如果餘數為0的石頭數目為偶數
        if (c0 % 2 == 0) {
            if (c1 == 0 || c2 == 0) {
                return false;
            }
            return true;
        } else {
            // 如果餘數為0的石頭數目為奇數
            if (Math.abs(c1 - c2) > 2 || Math.abs(c1 - c2)%2 == 0) {
                return false;
            }
            return true;
        }
    }
}

好累,我覺得好難。
其實我的邏輯錯了好幾次,陸續修正了一個小時才成功。晚安。https://ithelp.ithome.com.tw/upload/images/20240929/20169432Or2AeBdFdl.png


上一篇
day-13[medium.2063]vowels all substrings
下一篇
day-15[medium.2593]find score of array after marking all element
系列文
轉生理工組後從零開始的leetcode刷題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言