資訊專(zhuān)欄INFORMATION COLUMN
摘要：前言原題目，內(nèi)容如下你和你的朋友，兩個(gè)人一起玩游戲桌子上有一堆石頭，每次你們輪流拿掉塊石頭。編寫(xiě)一個(gè)函數(shù)，來(lái)判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲。
前言
原題目，內(nèi)容如下：
你和你的朋友，兩個(gè)人一起玩 Nim游戲：桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者。你作為先手。解題思路你們是聰明人，每一步都是最優(yōu)解。 編寫(xiě)一個(gè)函數(shù)，來(lái)判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲。
示例:
輸入: 4
輸出: false
解釋: 如果堆中有 4 塊石頭，那么你永遠(yuǎn)不會(huì)贏得比賽；
因?yàn)闊o(wú)論你拿走 1 塊、2 塊 還是 3 塊石頭，最后一塊石頭總是會(huì)被你的朋友拿走。
初看題目的時(shí)候可能會(huì)感覺(jué)無(wú)從下手，但是可以先把石頭的總數(shù)為1到20的輸贏情況（贏為true，輸為false）列出來(lái)，然后從中找到規(guī)律：
| 石頭數(shù) | 輸贏情況 | 石頭數(shù) | 輸贏情況 |
|---|---|---|---|
| 1 | true | 11 | true |
| 2 | true | 12 | false |
| 3 | true | 13 | true |
| 4 | false | 14 | true |
| 5 | true | 15 | true |
| 6 | true | 16 | false |
| 7 | true | 17 | true |
| 8 | false | 18 | true |
| 9 | true | 19 | true |
| 10 | true | 20 | false |
通過(guò)觀察輸贏情況表格，可以看出逢4必輸，為了更加清晰，對(duì)表格進(jìn)行了整理和補(bǔ)充：
| 石頭數(shù) | 輸贏情況 | 石頭數(shù) | 輸贏情況 | 石頭數(shù) | 輸贏情況 |
|---|---|---|---|---|---|
| 1 | true | 9 | true | 17 | true |
| 2 | true | 10 | true | 18 | true |
| 3 | true | 11 | true | 19 | true |
| 4 | false | 12 | false | 20 | false |
| 5 | true | 13 | true | 21 | true |
| 6 | true | 14 | true | 22 | true |
| 7 | true | 15 | true | 23 | true |
| 8 | false | 16 | false | 24 | false |
從整理的表格可以更加明顯看出逢4必輸的規(guī)律，即當(dāng)石頭數(shù)為4的倍數(shù)時(shí)必輸。
實(shí)現(xiàn)代碼public class Solution {
public boolean canWinNim(int n) {
return n%4!=0;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/76686.html
摘要：拿到最后一顆石頭的一方為剩方?，F(xiàn)給定一個(gè)石頭數(shù)量，判斷你最終是否能取得勝利。對(duì)方全拿，對(duì)方贏。因此，必輸無(wú)疑。當(dāng)剩下的石頭為的整數(shù)倍雙方都采取最優(yōu)策略時(shí)，先下手的一方為輸家。因此這個(gè)題目就很簡(jiǎn)單了，只要判斷給定的數(shù)字是否是的整數(shù)倍即可。 D64 292. Nim Game 題目鏈接 292. Nim Game 題目分析 假設(shè)你和朋友玩一個(gè)撿石頭的游戲，你和朋友輪流拿1~3顆石頭。拿到最...
摘要：題目鏈接思路博弈論類(lèi)型的題目?？偨Y(jié)規(guī)律得知，的倍數(shù)時(shí)，先走的必?cái) Ｋ惴◤?fù)雜度時(shí)間空間代碼 題目鏈接：Nim Game 思路：博弈論類(lèi)型的題目。我們知道，如果是1，2，3，則先走的必勝，4，則先走的必?cái)??？偨Y(jié)規(guī)律得知，4的倍數(shù)時(shí)，先走的必?cái) ?算法復(fù)雜度： 時(shí)間：O(n) 空間：O(1) 代碼： class Solution(object): def canWinNim(sel...
摘要：在線(xiàn)網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線(xiàn)網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...
閱讀 2647·2021-09-02 15:40
閱讀 1627·2019-08-30 15:54
閱讀 1138·2019-08-30 12:48
閱讀 3469·2019-08-29 17:23
閱讀 1102·2019-08-28 18:04
閱讀 3718·2019-08-26 13:54
閱讀 656·2019-08-26 11:40
閱讀 2471·2019-08-26 10:15
