国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Leetcode PHP題解--D64 292. Nim Game

XGBCCC / 1672人閱讀

摘要:拿到最后一顆石頭的一方為剩方。現給定一個石頭數量,判斷你最終是否能取得勝利。對方全拿,對方贏。因此,必輸無疑。當剩下的石頭為的整數倍雙方都采取最優策略時,先下手的一方為輸家。因此這個題目就很簡單了,只要判斷給定的數字是否是的整數倍即可。

D64 292. Nim Game 題目鏈接

292. Nim Game

題目分析

假設你和朋友玩一個撿石頭的游戲,你和朋友輪流拿1~3顆石頭。拿到最后一顆石頭的一方為剩方。第一輪由你開始撿石頭。
同時假設你和你的朋友都足夠聰明,每次都能采取最優策略。

現給定一個石頭數量,判斷你最終是否能取得勝利。

思路

我們先從少一點開始推廣到n個石頭。

如果有1~3顆石頭,因為規定了是你開始、還假設會采取最優策略,那么你是能獲勝的。也即,對方不會在拿走石頭后剩下1

假設有4顆石頭。
你拿1顆,會剩下3顆。對方全拿,對方贏
你拿2顆,會剩下2顆。對方全拿,對方贏
你拿3顆,會剩下1顆。對方全拿,對方贏
即,怎么拿都是你輸。

假設有5顆石頭。
你拿1顆,會剩下4顆。
對方拿走1顆,剩下3顆給你,你全拿,你贏。
對方拿走2顆,剩下2顆給你,你全拿,你贏。
對方拿走3顆,剩下1顆給你,你全拿,你贏。
你拿2顆,會剩下3顆。對方全拿,對方贏
你拿3顆,會剩下2顆。對方全拿,對方贏
因此,這一輪你會選擇拿1顆,剩下4顆。

假設有6顆石頭。
你拿1顆,會剩下5顆。
對方拿走1顆,剩下4顆給你,參考一開始就只有4顆的情況,對方贏
對方拿走2顆,剩下3顆給你,你全拿,你贏。
對方拿走3顆,剩下2顆給你,你全拿,你贏。
你拿2顆,會剩下4顆。
對方拿走1顆,剩下3顆給你,你全拿,你贏。
對方拿走2顆,剩下2顆給你,你全拿,你贏。
對方拿走3顆,剩下1顆給你,你全拿,你贏。
你拿3顆,會剩下3顆。對方全拿,對方贏
因此,這一輪你會選擇拿2顆,剩下4顆。

假設有7顆石頭。
你拿1顆,會剩下6顆。
對方拿走1顆,剩下5顆給你,參考一開始就只有5顆的情況,你贏。
對方拿走2顆,剩下4顆給你,對方贏
對方拿走3顆,剩下3顆給你,你全拿,你贏。
你拿2顆,會剩下5顆。
對方拿走1顆,剩下4顆給你,對方贏
對方拿走2顆,剩下3顆給你,你全拿,你贏。
對方拿走3顆,剩下2顆給你,你全拿,你贏。
你拿3顆,會剩下4顆。
對方拿走1顆,剩下3顆給你,你全拿,你贏。
對方拿走2顆,剩下2顆給你,你全拿,你贏。
對方拿走3顆,剩下1顆給你,你全拿,你贏。
因此,這一輪你會選擇拿3顆,剩下4顆。

假設有8顆石頭。
你拿1顆,會剩下7顆。
對方拿走1顆,剩下6顆給你,參考一開始就只有6顆的情況,你贏。
對方拿走2顆,剩下5顆給你,參考一開始就只有5顆的情況,你贏。
對方拿走3顆,剩下4顆給你,對方贏
你拿2顆,會剩下6顆。
對方拿走1顆,剩下5顆給你,你贏。
對方拿走2顆,剩下4顆給你,對方贏。
對方拿走3顆,剩下3顆給你,你全拿,你贏。
你拿3顆,會剩下5顆。
對方拿走1顆,剩下4顆給你,對方贏。
對方拿走2顆,剩下3顆給你,你全拿,你贏。
對方拿走3顆,剩下2顆給你,你全拿,你贏。
因此,必輸無疑。

我們可以得出規律。當剩下的石頭為4的整數倍、雙方都采取最優策略時,先下手的一方為輸家。

因此這個題目就很簡單了,只要判斷給定的數字是否是4的整數倍即可。

最終代碼

</>復制代碼

  1. 若覺得本文章對你有用,歡迎用愛發電資助。

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

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

相關文章

  • 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 評論0 收藏0
  • 292. Nim Game

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

    April 評論0 收藏0
  • Leetcode PHP題解--D37 682. Baseball Game

    摘要:題目鏈接題目分析給定一個字符串數組,每一個字符串有以下形式數字。直接計算得分。。代表上一輪分數無效。思路這題沒什么好說的了。用區分各種情況,進行相應處理即可。最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 682. Baseball Game 題目鏈接 682. Baseball Game 題目分析 給定一個字符串數組,每一個字符串有以下形式: 數字。直接計算得分。 +。代表本輪...

    wzyplus 評論0 收藏0
  • [Leetcode] Nim Game 尼姆游戲

    摘要:腦筋急轉彎復雜度時間空間思路這題往小說可以追溯到小學奧數或者腦筋急轉彎的書中,往大說可以深究到博弈論。代碼如果一開始就是的倍數,你就輸了,因為對方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

    cartoon 評論0 收藏0
  • 前端 | 每天一個 LeetCode

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

    張漢慶 評論0 收藏0

發表評論

0條評論

XGBCCC

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<