這是悅樂書的第203次更新锁蠕，第213篇原創(chuàng)
01 看題和準備
你和你的朋友正在玩下面的Nim游戲：桌子上有一堆石頭，每次你輪流去除1到3塊石頭贴浙。 移除最后一塊石頭的人將成為贏家豺总。 你是第一個取出石塊的匀归。
你們兩個都非常聰明，并且擁有最佳的游戲策略运敢。 編寫一個函數(shù)來確定你是否可以在堆中的石頭數(shù)量的情況下贏得游戲校仑。例如：
輸入：4
輸出：false
說明：如果堆中有4塊石頭，那么你永遠不會贏得游戲;無論你刪除了1,2或3塊石頭传惠，你的朋友都能去除它迄沫。
本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8涉枫，環(huán)境是win7 64位系統(tǒng)邢滑，使用Java語言編寫和測試腐螟。
02 解題
這道題有點像排列組合愿汰，給定一個整數(shù)n，在1到3之間進行隨機組合乐纸，判斷能否在奇數(shù)次移除石頭的組合下衬廷，將n變?yōu)?。當n等于1,2,3時汽绢，你都可以一次將其移除吗跋。當n等于4的時候，你無論怎么移都會輸宁昭。當n等于5的時候跌宛，第一次移動一塊，剩下4塊給另外一個人移除积仗，另外一個人就會陷入4的死局疆拘，你就能在第二次移除的時候贏，當n等于6和7的時候寂曹，結(jié)局是一樣的哎迄。當n等于8的時候，結(jié)局和n等于4一樣隆圆，怎么選都會輸漱挚。對此，只要是4的倍數(shù)渺氧，都是輸局旨涝，所以簡單的判斷就變成了n對4取余是否等于0。
public boolean canWinNim(int n) {
if (n <= 4) {
return n == 1 || n == 2 || n == 3;
}
return n%4 != 0;
}
此解法的時間復雜度是O(1)侣背，空間復雜度是O(1)白华。
03 小結(jié)
算法專題目前已連續(xù)日更超過二個月哩治，算法題文章69+篇，公眾號對話框回復【數(shù)據(jù)結(jié)構(gòu)與算法】衬鱼、【算法】业筏、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集鸟赫。
以上就是全部內(nèi)容蒜胖，如果大家有什么好的解法思路、建議或者其他問題抛蚤，可以下方留言交流台谢，點贊、留言岁经、轉(zhuǎn)發(fā)就是對我最大的回報和支持朋沮！
