[Leetcode] Nim Game 尼姆游戲

cartoon 發布于2019-08-14 12:45 / 3160人閱讀

摘要：腦筋急轉彎復雜度時間空間思路這題往小說可以追溯到小學奧數或者腦筋急轉彎的書中，往大說可以深究到博弈論。代碼如果一開始就是的倍數，你就輸了，因為對方可以用同樣的策略

Nim Game

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.

腦筋急轉彎 復雜度

時間 O(1) 空間 O(1)

思路

這題往小說可以追溯到小學奧數或者腦筋急轉彎的書中，往大說可以深究到博弈論。然而編程在這里并沒有卵用，策略在于，因為每個人都取不到4個，假設自己后走，要保證每輪自己和對方取得數量的和是4，這樣就能確保每輪完后都有4的倍數個石頭被取走。這樣，如果我們先走的話，先把n除4的余數個石頭拿走，這樣不管怎樣，到最后都會留4個下來，對方取1個你就取3個，對方取2個你就取2個，就必贏了。

代碼

public class Solution {
    public boolean canWinNim(int n) {
        // 如果一開始就是4的倍數，你就輸了，因為對方可以用同樣的策略
        return n % 4 != 0;
    }
}

GPU云服務器云服務器 Nim 尼姆 LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64683.html

Leetcode PHP題解--D64 292. Nim Game

摘要：拿到最后一顆石頭的一方為剩方。現給定一個石頭數量，判斷你最終是否能取得勝利。對方全拿，對方贏。因此，必輸無疑。當剩下的石頭為的整數倍雙方都采取最優策略時，先下手的一方為輸家。因此這個題目就很簡單了，只要判斷給定的數字是否是的整數倍即可。 D64 292. Nim Game 題目鏈接 292. Nim Game 題目分析假設你和朋友玩一個撿石頭的游戲，你和朋友輪流拿1~3顆石頭。拿到最...

XGBCCC 2019-07-01 12:48 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
292. Nim Game

摘要：題目鏈接思路博弈論類型的題目。總結規律得知，的倍數時，先走的必敗。算法復雜度時間空間代碼題目鏈接：Nim Game 思路：博弈論類型的題目。我們知道，如果是1，2，3，則先走的必勝，4，則先走的必敗。總結規律得知，4的倍數時，先走的必敗。算法復雜度：時間：O(n) 空間：O(1) 代碼： class Solution(object): def canWinNim(sel...

April 2019-07-30 17:02 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[Leetcode] Jump Game 跳躍游戲

摘要：代碼記錄下當前區域的上界，以便待會更新下一個區域的上界更新下一個區域的上界更新下一個區域的下界后續如果要求返回最短跳躍路徑，如何實現可以使用，并根據一個全局最短步數維護一個全局最短路徑，當搜索完所有可能后返回這個全局最短路徑。 Jump Game I 最新解法請見：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

venmos 2019-08-14 12:24 評論0 收藏0