資訊專(zhuān)欄INFORMATION COLUMN
摘要：腦筋急轉(zhuǎn)彎復(fù)雜度時(shí)間空間思路這題往小說(shuō)可以追溯到小學(xué)奧數(shù)或者腦筋急轉(zhuǎn)彎的書(shū)中，往大說(shuō)可以深究到博弈論。代碼如果一開(kāi)始就是的倍數(shù)，你就輸了，因?yàn)閷?duì)方可以用同樣的策略
Nim Game
腦筋急轉(zhuǎn)彎 復(fù)雜度You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
時(shí)間 O(1) 空間 O(1)
思路這題往小說(shuō)可以追溯到小學(xué)奧數(shù)或者腦筋急轉(zhuǎn)彎的書(shū)中，往大說(shuō)可以深究到博弈論。然而編程在這里并沒(méi)有卵用，策略在于，因?yàn)槊總€(gè)人都取不到4個(gè)，假設(shè)自己后走，要保證每輪自己和對(duì)方取得數(shù)量的和是4，這樣就能確保每輪完后都有4的倍數(shù)個(gè)石頭被取走。這樣，如果我們先走的話，先把n除4的余數(shù)個(gè)石頭拿走，這樣不管怎樣，到最后都會(huì)留4個(gè)下來(lái)，對(duì)方取1個(gè)你就取3個(gè)，對(duì)方取2個(gè)你就取2個(gè)，就必贏了。
代碼public class Solution {
public boolean canWinNim(int n) {
// 如果一開(kāi)始就是4的倍數(shù)，你就輸了，因?yàn)閷?duì)方可以用同樣的策略
return n % 4 != 0;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64683.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顆石頭。拿到最...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(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ū)別...
摘要：題目鏈接思路博弈論類(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...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：代碼記錄下當(dāng)前區(qū)域的上界，以便待會(huì)更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的下界后續(xù)如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)可以使用，并根據(jù)一個(gè)全局最短步數(shù)維護(hù)一個(gè)全局最短路徑，當(dāng)搜索完所有可能后返回這個(gè)全局最短路徑。 Jump Game I 最新解法請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/01/... Given an array of non-negat...
閱讀 620·2021-11-22 14:45
閱讀 3118·2021-10-15 09:41
閱讀 1638·2021-10-11 10:58
閱讀 2823·2021-09-04 16:45
閱讀 2645·2021-09-03 10:45
閱讀 3270·2019-08-30 15:53
閱讀 1250·2019-08-29 12:28
閱讀 2171·2019-08-29 12:14
