LeetCode.1025-除數遊戲(Divisor Game)

這是小川的第382次更新，第411篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第244題（順位題号是1025）。Alice和Bob輪流玩遊戲，Alice首先出發。

最初，黑闆上有一個數字

N

. 在每個玩家的回合中，該玩家進行以下操作：

選擇

0 < x <N

且

N％x == 0

的任何

x

。

用

N - x

替換黑闆上的數字

N

.

此外，如果玩家無法移動，他們将輸掉遊戲。

當且僅當Alice赢得比賽時才傳回True，假設兩個玩家都達到最佳狀态。

例如：

輸入：2

輸出：true

說明：Alice選擇1，Bob沒有更多動作。

輸入：3

輸出：false

說明：Alice選擇1，Bob選擇1，Alice不再移動。

注意：

• 1 <= N <= 1000

02 解題

N=1

，0 < x < 1且1％x == 0，沒有符合的數，Alice輸。

N=2

，0 < x < 2且2％x == 0，Alice取1，N變成1，輪到Bob，Bob無法選擇合适的數，Alice赢。

N=3

，0 < x < 3且3％x == 0，Alice取1，N變成2，輪到Bob，Bob選1，N變成1，輪到Alice再選，沒有符合的數，Alice輸。

N=4

，0 < x < 4且4％x == 0，Alice取1，N變成3，輪到Bob，Bob選1，N變成2，輪到Alice再選1，N變成1，再輪到Bob選，沒有符合的數，Alice赢。

N=5

，0 < x < 5且5％x == 0，Alice取1，N變成4，輪到Bob，Bob選1，N變成3，再輪到Alice選，和前面N等于3結果一樣，Alice輸。

N=6

，0 < x < 6且6％x == 0，Alice取1，N變成5，輪到Bob，Bob選1，N變成4，再輪到Alice選，和前面N等于4結果一樣，Alice赢。

從上面依次計算的例子來看，當N為奇數的時候，誰先開始，誰就輸，因為對方肯定會讓你繼續變成奇數，直到N變成1。

當N為偶數的時候，誰先開始，誰就赢，第一步取1，将N變成奇數，對方隻能繼續取1或者其他奇數，奇數減去奇數變為偶數，開始的那一方再取1，直到N變成1。

public boolean divisorGame(int N) {
    return N%2 == 0;
}
           

03 小結

算法專題目前已連續日更超過七個月，算法題文章250+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！