leetcode292. Nim 游戲(博弈論 - java)

Nim 游戲

  • Nim 游戲
    • 題目描述
    • 博弈論
  • 上期經典算法

Nim 游戲

難度 - 簡單
原題鏈接 - Nim游戲

題目描述

你和你的朋友,兩個人一起玩 Nim 游戲:
桌子上有一堆石頭。
你們輪流進行自己的回合, 你作為先手 。
每一回合,輪到的人拿掉 1 - 3 塊石頭。
拿掉最后一塊石頭的人就是獲勝者。
假設你們每一步都是最優解。請編寫一個函數,來判斷你是否可以在給定石頭數量為 n 的情況下贏得游戲。如果可以贏,返回 true;否則,返回 false 。

示例 1:
輸入:n = 4
輸出:false
解釋:以下是可能的結果:

  1. 移除1顆石頭。你的朋友移走了3塊石頭,包括最后一塊。你的朋友贏了。
  2. 移除2個石子。你的朋友移走2塊石頭,包括最后一塊。你的朋友贏了。
    3.你移走3顆石子。你的朋友移走了最后一塊石頭。你的朋友贏了。
    在所有結果中,你的朋友是贏家。

示例 2:
輸入:n = 1
輸出:true

示例 3:
輸入:n = 2
輸出:true

提示:
1 <= n <= 2e31 - 1

在這里插入圖片描述

博弈論

在不知曉博弈論結論前,可以先通過找規律得到猜想,然后再從「何種情況下,先手會處于必勝態」的角度來進行分析。

根據題意,我們嘗試從小范圍數據的情況進行討論:

  1. 如果落到先手的局面為「石子數量為 - 」的話,那么先手必勝;
  2. 如果落到先手的局面為「石子數量為 」的話,那么先手決策完(無論何種決策),交到后手的局面為「石子數量為 - 」,即此時后手必勝,對應先手必敗(到這里我們有一個推論:如果交給先手的局面為 的話,那么先手必敗);
  3. 如果落到先手的局面為「石子數量為 - 」的話,那么先手可以通過控制選擇石子的數量,來使得后手處于「石子數量為 」的局面(此時后手必敗),因此先手必勝;
  4. 如果落到先手的局面為「石子數量為 」的話,由于每次只能選 - 個石子,因此交由后手的局面為 - ,根據流程 我們知道此時先手必敗;

到這里,我們猜想 當起始局面石子數量為 的倍數,則先手必敗,否則先手必勝(即 n % 4 != 0 時,先手必勝)。

代碼

    public boolean canWinNim(int n) {if(n <= 3){return true;}return n % 4 != 0;}

上期經典算法

leetcode-413. 等差數列劃分

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/41474.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/41474.shtml
英文地址,請注明出處:http://en.pswp.cn/news/41474.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

494. 目標和

494. 目標和 原題鏈接&#xff1a;完成情況&#xff1a;解題思路&#xff1a;數組回溯法動態規劃 參考代碼&#xff1a;數組回溯法__494目標和__動態規劃 經驗吸取 原題鏈接&#xff1a; 494. 目標和 https://leetcode.cn/problems/target-sum/description/ 完成情況&#…

Android進階之多級列表

遇到一個需求需要顯示多級列表&#xff0c;因為界面是在平板上的&#xff0c;所以層級是從左向右往下排的&#xff0c;類似于 我當時的寫法是在xml布局里一個個RecyclerView往下排的 當然前提是已經規定好最大的層級我才敢如此去寫界面&#xff0c;如果已經明確規定只有兩級或…

69 # 強制緩存的配置

強制緩存 強制緩存&#xff1a;以后的請求都不需要訪問服務器&#xff0c;狀態碼為 200協商緩存&#xff1a;每次都判斷一下&#xff0c;告訴是否需要找緩存&#xff0c;狀態碼為 304 默認強制緩存&#xff0c;不緩存首頁&#xff08;如果已經斷網&#xff0c;那這個頁面應該…

Python發送QQ郵件

使用Python的smtplib可以發送QQ郵件&#xff0c;代碼如下 #!/usr/bin/python3 import smtplib from email.mime.text import MIMEText from email.header import Headersender 111qq.com # 發送郵箱 receivers [222qq.com] # 接收郵箱 auth_code "abc" # 授權…

Dockerfile概念、鏡像原理、制作及案例講解

1.Docker鏡像原理 Linux文件操作系統講解 2.鏡像如何制作 3.Dockerfile概念 Docker網址&#xff1a;https://hub.docker.com 3.1 Dockerfile關鍵字 4.案例

【數據結構OJ題】鏈表分割

原題鏈接&#xff1a;https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8&&tqId11004&rp2&ru/activity/oj&qru/ta/cracking-the-coding-interview/question-ranking 目錄 1. 題目描述 2. 思路分析 3. 代碼實現 1. 題目描述 2…

AMD卡啟動Stable Diffusion AI繪畫的方法

WindowsAMD安裝法 1.安裝python 3.10.6&#xff0c;在python官網上下載安裝程序&#xff0c;***重要*** 在安裝的第一個窗口下方勾選“將python添加到path”。 2.安裝git 3.WindowsAMD使用AUTOMATIC1111的directml這一個fork&#xff0c;在這個頁面的第一段&#xff1a;https:/…

題目:2614.對角線上的質數

??題目來源&#xff1a; leetcode題目&#xff0c;網址&#xff1a;2614. 對角線上的質數 - 力扣&#xff08;LeetCode&#xff09; 解題思路&#xff1a; 遍歷對角線上的元素&#xff0c;返回最大的質數或 0 即可。 解題代碼&#xff1a; class Solution {public int dia…

e.target.value和 binding.value 區別

e.target.value 和 binding.value 都是在 Vue.js 中用于處理事件綁定時的值&#xff0c;但它們的使用場景和含義有所不同&#xff0c;分別用于普通的 DOM 事件和自定義指令。 e.target.value&#xff1a; 這是常用于原生 DOM 事件處理函數中的一個屬性&#xff0c;用于獲取事件…

爬蟲逆向實戰(十七)--某某丁簡歷登錄

一、數據接口分析 主頁地址&#xff1a;某某丁簡歷 1、抓包 通過抓包可以發現數據接口是submit 2、判斷是否有加密參數 請求參數是否加密&#xff1f; 通過查看“載荷”模塊可以發現有一個enPassword加密參數 請求頭是否加密&#xff1f; 通過查看請求頭可以發現有一個To…

【面試高頻題】難度 3/5,字典樹熱門運用題

題目描述 這是 LeetCode 上的 「745. 前綴和后綴搜索」 &#xff0c;難度為 「困難」。 Tag : 「字典樹」 設計一個包含一些單詞的特殊詞典&#xff0c;并能夠通過前綴和后綴來檢索單詞。 實現 WordFilter 類&#xff1a; WordFilter(string[] words) 使用詞典中的單詞 words 初…

單片機之從C語言基礎到專家編程 - 4 C語言基礎 - 4.9 變量與常量

基本數據類型可以作為變量與常量使用,顧名思義&#xff0c;變量運行時可以改變其值&#xff0c;常量運行時不會改變其值。 常量分為整型常量、浮點型常量、字符常量、字符串常量和符號常量。 通常用#define來定義一個標識符來表示一個常量 用type name 常量來定義一個變量,…

無法將“環境變量”項識別為 cmdlet、函數、腳本文件或可運行程序的名稱(pycharm)

無法將“配置的任何一個環境變量”項識別為 cmdlet、函數、腳本文件或可運行程序的名稱。 記錄解決“無法將“C:......conda.exe”項識別為 cmdlet、函數、腳本文件或可運行程序的名稱”以及“表達式或語句中包含意外的標記”的系列問題(VSCode開發環境)一、Conda.exe無法正常識…

ROS2 學習(三)話題

話題 節點之間的通信。 叫話題很形象。發布者發布一定數據類型的話題&#xff0c;訂閱者訂閱發布者。 訂閱者發布者不唯一。 異步通信&#xff0c;適用于周期發布的數據而不是邏輯性強的數據。 .msg 格式的消息結構&#xff0c;一種通信接口。 每個話題 topic 有話題名&a…

【Java高級開發高頻面試題】面試者角度的口述版

文章目錄 1.具備扎實的Java基礎集合HashMap底層工作原理HashMap版本問題HashMap并發修改異常HashMap影響HashMap性能的因素HashMap使用優化 SynchronizedThreadLocalAQS線程池JVM內存模型類加載機制與雙親委派垃圾回收算法、垃圾回收器、空間分配擔保策略引用計數器算法、可達性…

創建 Web 內容目錄

創建 Web 內容目錄 按照下方所述&#xff0c;創建一個名為 /home/curtis/ansible/webcontent.yml 的 playbook &#xff1a; 該 playbook 在 dev 主機組中的受管節點上運行 創建符合下列要求的目錄 /webdev &#xff1a; 所有者為 webdev 組 具有常規權限&#xff1a;ownerread…

Nginx反向代理

目錄 一.簡介1.反向代理 二.案例1.案例12.案例2 一.簡介 1.反向代理 1.1反向代理&#xff1a; 是指代理服務器來接收Internet上的客戶端請求&#xff0c;然后將請求轉發給內部網絡上的服務器&#xff0c;并將從服務器上得到的結果返回給客戶端。此時代理服務器對外就表現為一…

循環隊列的實現(c語言)

前言 循環隊列是隊列的一種特殊的結構&#xff0c;在生產者——消費者模型中常常使用它&#xff0c; 它在邏輯上是一個環形的連續的結構。在物理可以使用數組來實現。 目錄 1.循環隊列的邏輯結構 2.空的循環隊列和滿的循環隊列 3.循環隊列插入和刪除 4.代碼實現 …

淺談Redis的maxmemory設置以及淘汰策略

推薦閱讀 AI文本 OCR識別最佳實踐 AI Gamma一鍵生成PPT工具直達鏈接 玩轉cloud Studio 在線編碼神器 玩轉 GPU AI繪畫、AI講話、翻譯,GPU點亮AI想象空間 資源分享 「java、python面試題」來自UC網盤app分享&#xff0c;打開手機app&#xff0c;額外獲得1T空間 https://dr…

音視頻實時通話解決方案

1、問題提出 想要實現音視頻通話,對于大部分人可能會覺得很難,但是實際上,有些事情并沒有大家想的那樣困難,只要功夫深,鐵杵磨成針。 機緣巧合下,在業務中,我也遇到了一個業務場景需要實現音視頻通話,我們不可能自己從零開始干,我本次用到的核心是WebRTC。 2、WebRT…