Leetcode292. Nim 游戏

news/2024/10/30 19:24:35/

Every day a leetcode

题目来源:292. Nim 游戏

解法1:数学推理

让我们考虑一些小例子。

显而易见的是,如果石头堆中只有一块、两块、或是三块石头,那么在你的回合,你就可以把全部石子拿走,从而在游戏中取胜;

如果堆中恰好有四块石头,你就会失败。因为在这种情况下不管你取走多少石头,总会为你的对手留下几块,他可以将剩余的石头全部取完,从而他可以在游戏中打败你。因此,要想获胜,在你的回合中,必须避免石头堆中的石子数为4的情况。

假设当前堆里只剩下五块、六块、或是七块石头,你可以控制自己拿取的石头数,总是恰好给你的对手留下四块石头,使他输掉这场比赛。但是如果石头堆里有八块石头,你就不可避免地会输掉,因为不管你从一堆石头中挑出一块、两块还是三块,你的对手都可以选择三块、两块或一块,以确保在再一次轮到你的时候,你会面对四块石头。

于是我们发现,该问题可以拆分成许多小问题(每个小问题有四块石头)。

设石头数量为n,当n是4的倍数时,我们总是会输;否则我们会赢。

代码:

/** @lc app=leetcode.cn id=292 lang=cpp** [292] Nim 游戏*/// @lc code=start
class Solution
{
public:bool canWinNim(int n){return n % 4;}
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(1)。

空间复杂度:O(1)。


http://www.ppmy.cn/news/58671.html

相关文章

【Python入门篇】——Python基础语法(字面量注释与变量)

作者简介: 辭七七,目前大一,正在学习C/C,Java,Python等 作者主页: 七七的个人主页 文章收录专栏: Python入门,本专栏主要内容为Python的基础语法,Python中的选择循环语句…

Python XML

XML(可扩展标记语言)是一种标记语言,用于存储和传输数据。Python提供了许多内置库来处理XML数据,包括: 1. xml.etree.ElementTree:一个用于解析和操作XML文件的Python标准库。 2. xml.dom:一个…

FreeRTOS 软件定时器

文章目录 一、软件定时器简介二、定时器服务/Daemon 任务三、单次定时器和周期定时器四、复位软件定时器1. 函数 xTimerReset()2. 函数 xTimerResetFromISR() 五、创建软件定时器1. 函数 xTiemrCreate()2. 函数 xTimerCreateStatic() 六、开启软件定时器1. 函数 xTimerStart()2…

【软考中级】2022下半年软件设计师综合知识真题与答案

1、以下关于R1SC(精简指令集计算机)特点的叙述中,错误的是()。 A.对存储器操作进行限制,使控制简单化 B.指令种类多,指令功能强 C.设置大量通用寄存器 D.选取使用频率较高的一些指令,提高执行速度 参考答案:B 2、…

Java 基础进阶篇(二)—— static 静态关键字与单例模式

文章目录 一、static 静态关键字1.1 静态成员变量与实例成员变量1.2 静态成员方法与实例成员方法1.3 static 访问注意事项1.4 内存使用情况 二、工具类三、代码块四、单例模式4.1 饿汉单例4.2 懒汉单例 一、static 静态关键字 static:代表静态的意思,可…

Python基础合集 练习21 (错误与异常处理语句)

‘’‘try: block1 except[ExceptionName]: block2 ‘’’ block1:执行代码,表示可能会出现错误的代码块 ExceptionName: 表示要捕获的异常名称,为可选参数.如果不指定异常名称,则表示捕获所有异常 block2:表示发生异常时执行的代码块 while True: try: num int(input(请输…

机器学习小结之KNN算法

文章目录 前言一、概念1.1 机器学习基本概念1.2 k 值1.3 距离度量1.4 加权方式 二、实现2.1 手写实现2.2 调库 Scikit-learn2.3 测试自己的数据 三、总结3.1 分析3.2 KNN 优缺点 参考 前言 ​ KNN (K-Nearest Neighbor)算法是一种最简单,也是一个很实用的机器学习的…

【C++】特殊类设计+单例模式+类型转换

目录 一、设计一个类,不能被拷贝 1、C98 2、C11 二、设计一个类,只能在堆上创建对象 1、将构造设为私有 2、将析构设为私有 三、设计一个类,只能在栈上创建对象 四、设计一个类,不能被继承 1、C98 2、C11 五、设计一个…