Skip to content

LeetCode: 1510-Stone Game IV 解題紀錄

Last Updated on 2022-01-22 by Clay

題目

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Constraints:

  • 1 <= n <= 105

題目給定數量為 n 的石子(或棋子,圍棋棋子也被稱為 stone),Alice 和 Bob 可以拿走不為 0 的 i 平方的石子,i 可以自己決定。

最好無法拿走石子的情況就算輸掉,由 Alice 先攻,在雙方都做出最佳決策的情況下,如果 Alice 可以獲勝就回傳 true,否則回傳 false。


解題思路

DP。今天因忙碌暫時跳過紀錄。但這個方法比我一開始想的地回來得好。)

複雜度

Time ComplexityO(n^1.5)(註記:我不確定該如何估算這題!但我看到此解法他人的估計複雜度為此...... 我會再繼續研究
Space ComplexityO(1)


C++ 範例程式碼

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<bool> dp(n+1);
        
        for (int i=1; i<=n; ++i){
            for (int j=1; j*j <= i; ++j){
                if(dp[i-j*j] == false) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
};

References


Read More

Leave a Reply取消回覆

Exit mobile version