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. 等差数列划分

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/77665.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MySQL 中 不等于 会过滤掉 Null 的问题

null值与任意值比较时都为fasle not in 、"!"、"not like"条件过滤都会过滤掉null值的数据 SELECT * from temp; SELECT * from temp where score not in (70); 返回null解决方法: SELECT * from temp where score not in (70) or score is null;SELECT…

OC调用Swift编写的framework

一、前言 随着swift趋向稳定&#xff0c;越来越多的公司都开始用swift来编写苹果相关的业务了&#xff0c;关于swift的利弊这里就不多说了。这里详细介绍OC调用swift编写的framework库的步骤 二、制作framework 1、新建项目&#xff0c;选择framework 2、填写framework的名称…

Excel革命,基于电子表格开发的新工具,不是Access和Power Fx

深谙其道 在日常工作中&#xff0c;Excel是许多人不可或缺的办公工具。 是微软的旗下产品&#xff0c;属于Microsoft 365套件中的一部分&#xff0c;强大的数据处理和计算功能&#xff0c;被普遍应用在全球各行各业的人群当中&#xff0c;是一款强大且普及的电子表格软件。 于…

Salient主题 - 创意多用途和WooCommerce商城主题

Salient主题是下一代WordPress主题&#xff0c;给任何人带来专业的设计结果&#xff0c;而不需要任何编码。Salient 提供永久更新的专业剖面模板库&#xff0c;目前有超过425个可供选择 – 所有这些都充满热情并坚持高标准的审美质量。 网址: Salient主题 - 创意多用途和WooCo…

Google play应用成功上架要点——如何防止封号、拒审、下架?

Google Play是全球最大的移动应用商店之一&#xff0c;它是运行Android操作系统的设备的官方应用商店。它提供各种数字内容&#xff0c;包括应用程序&#xff08;应用&#xff09;、游戏、音乐、书籍等&#xff0c;包括免费和付费选项。这也为许多游戏/APP出海的企业或开发者提…

Vue CLI创建Vue项目详细步骤

&#x1f680; 一、安装Node环境&#xff08;建议使用LTS版本&#xff09; 在开始之前&#xff0c;请确保您已经安装了Node.js环境。您可以从Node.js官方网站下载LTS版本&#xff0c;以确保稳定性和兼容性。 中文官网下载 确认已安装 Node.js。可以在终端中运行 node -v 命令…

【AI大模型】训练Al大模型 (上篇)

大模型超越AI 前言 洁洁的个人主页 我就问你有没有发挥&#xff01; 知行合一&#xff0c;志存高远。 目前所指的大模型&#xff0c;是“大规模深度学习模型”的简称&#xff0c;指具有大量参数和复杂结构的机器学习模型&#xff0c;可以处理大规模的数据和复杂的问题&#x…

缓存平均的两种算法

引言 线边库存物料的合理性问题是物流仿真中研究的重要问题之一,如果线边库存量过多,则会对生产现场的布局产生负面影响,增加成本,降低效益。 写在前面 仿真分析后对线边Buffer的使用情况进行合理的评估就是一个非常重要的事情。比较关心的参数包括:缓存位最大值…

探索网络架构的关键角色:六种常用的服务器类型

在今天的数字时代&#xff0c;服务器是支撑各种在线服务和应用的基石。不同类型的服务器在网络架构中扮演着不同的角色&#xff0c;从网页传输到电子邮件交换&#xff0c;再到文件传输和内容分发。本文将深入探讨六种最常用的服务器类型&#xff0c;解释它们的功能和重要性&…

力扣301周赛C~DABC299 D、E、G

第 301 场周赛 C&#xff1a; 思路&#xff1a; 经典双指针问题&#xff0c;用i表示字符串start当前枚举到的位置&#xff0c;用j表示字符串target当前枚举到的位置&#xff1a; i从当前位置向后跑&#xff0c;跑到start串下标i之后的第一个不为_的位置 j从当前位置向后跑&a…

node获取抖音直播间Id

node获取抖音直播间Id 信息位置 直播间信息存放在id是RENDER_DATA的script标签里 安装依赖 npm install fetch cheerio # 或 pnpm install fetch cheerionode代码 // room.js const fetch require("fetch"); const cheerio require("cheerio"); // co…

Qt读写Excel--QXlsx编译为静态库2

1、概述&#x1f954; 在使用QXlsx时由于源码文件比较多&#xff0c;如果直接加载进项目里面&#xff0c;会增加每次编译的时间&#xff1b; 直接将源码加载进项目工程中&#xff0c;会导致项目文件非常多&#xff0c;结构变得更加臃肿&#xff1b; 所以在本文中将会将QXlsx编译…

什么是字体堆栈(font stack)?如何设置字体堆栈?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 什么是字体堆栈&#xff08;Font Stack&#xff09;&#xff1f;⭐ 如何设置字体堆栈&#xff1f;⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 …

解密人工智能:线性回归 | 逻辑回归 | SVM

文章目录 1、机器学习算法简介1.1 机器学习算法包含的两个步骤1.2 机器学习算法的分类 2、线性回归算法2.1 线性回归的假设是什么&#xff1f;2.2 如何确定线性回归模型的拟合优度&#xff1f;2.3 如何处理线性回归中的异常值&#xff1f; 3、逻辑回归算法3.1 什么是逻辑函数?…

解析Python爬虫常见异常及处理方法

作为专业爬虫程序猿长期混迹于爬虫ip解决方案中&#xff0c;我们经常会遇到各种各样的异常情况。在爬虫开发过程中&#xff0c;处理这些异常是不可或缺的一部分。本文将为大家总结常见的Python爬虫异常&#xff0c;并分享相应的处理方法&#xff0c;帮助你避免绊倒在爬虫之路上…

题目:售货员的难题(状压dp)

售货员的难题 题目描述输入输出格式输入格式&#xff1a;输出格式&#xff1a; 输入输出样例输入样例#1&#xff1a;输出样例#1&#xff1a; 思路AC代码&#xff1a; 题目描述 某乡有n个村庄( 1 < n < 16 )&#xff0c;有一个售货员&#xff0c;他要到各个村庄去售货&am…

每天一道leetcode:433. 最小基因变化(图论中等广度优先遍历)

今日份题目&#xff1a; 基因序列可以表示为一条由 8 个字符组成的字符串&#xff0c;其中每个字符都是 A、C、G 和 T 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如&#xff0c;&quo…

数据结构----哈夫曼树

这里写目录标题 基本概念引子基本概念各种路径长度各种带权路径长度结点的带权路径长度树的带权路径长度哈夫曼树 哈夫曼树的构造理论基础构造思想总结 哈夫曼树的实现哈夫曼编码前缀编码哈夫曼编码的思想案例代码实现 编码与解码 基本概念 引子 哈夫曼树就是寻找构造最优二叉…

k8s RBAC授权普通系统用户对namespace访问权限

背景&#xff1a;最近遇到一个问题&#xff0c;那就是需要给别人共享一下 Kubernetes 的某个资源的使用和访问权限&#xff0c;这个仅仅存在于某个 namespace 下&#xff0c;但是我又不能把管理员权限全都给它&#xff0c;我想只给他授予这一个 Namespace 下的权限&#xff0c;…

OpenShift 4 - 基于 MinIO 安装 Red Hat Quay 镜像仓库

《OpenShift / RHEL / DevSecOps 汇总目录》 说明&#xff1a;本文已经在 OpenShift 4.13 Quay 3.9 的环境中验证 本文适合在单机 OpenShift 环境安装 Red Hat Quay 镜像仓库。 另外《OpenShift 4 - 安装 ODF 并部署红帽 Quay (1 Worker)》也可以在单节点部署。 而《OpenShif…