前往
大廳
主題

LeetCode - 1025. Divisor Game 解題心得

Not In My Back Yard | 2021-03-13 00:00:06 | 巴幣 0 | 人氣 475

題目連結:


題目意譯:
Alice 和 Bob 輪流玩著一場遊戲,由 Alice 作為先手。

一開始,黑板上有一個數字 N。每個玩家的回合,該玩家做出一操作:
選擇任一 x 值滿足 0 < x < N 且 N % x == 0。
將黑板上的數字 N 替換為 N - x。

此外,如果玩家無法做出任何操作,該玩家則輸了此局遊戲。

回傳真(True)若且唯若 Alice 必贏,假設兩個玩家都是依照最佳策略遊玩。
 
注:
1 ≦ N ≦ 1000



範例測資:
範例 1:
輸入: 2
輸出: true
解釋: Alice 選擇 1,而 Bob 接下來沒有任何可能的操作。

範例 2:
輸入: 3
輸出: false
解釋: Alice 選擇 1 、 Bob 選擇 1 ,而 Alice 沒有任何可能的操作。


解題思維:
稍作變形的拈(Nim),做法有點像這題。不過現在對於每個數字(石頭)N 只能拿走他的因數 x 且該因數不能為 N 自己。

而 LeetCode 上面解題雖然格式找這樣(以下以 C++ 為例):
class Solution {
public:
    bool divisorGame(int N) {

    }
};
但是你其實可以在 class 外面寫東西,例如宣告變數或甚至是在全域跑 Lambda 語法(因此可以建表或是採取一些輸出入最佳化),例如
static const auto TEST = []{
    // 略
    return nullptr;
}();
[]{} 這種神祕的格式就是 C++ 的 Lambda 運算式,詳細可以參見微軟的文件或是 StackOverFlow 的這篇文章




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作