Shinkai005

V1

2022/02/12阅读:28主题:红绯

# 【leetcode】292.nim游戏

【leetcode】292.nim游戏.md

image-20220212085245101
image-20220212085245101

题目描述

image-20211224231907510
image-20211224231907510

题目思路

巴什博奕(Bash Game):

只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个.最后取光者得胜

结论:若(m+1) % n,则先手必败,否则先手必胜

显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜

因此我们发现了如何取胜的法则:

如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,

如果后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,

以后保持这样的取法,那么先取者肯定获胜总之,要保持给对手留下(m+1)的倍数,就能最后获胜。

个人题解

/**
 * @param {number} n
 * @return {boolean}
 */

var canWinNim = function(n{
 return n%4!= 0;
};

总结优化

自己作为先手,那么如果有4块, 那么无论如何都赢不了.

因此,只要让 n%m+1 !=0 即可 m是最多拿多少.

这是现实中的一个游戏,只要让队友拿到的时候一直保持 m+1的倍数即可 这道题就是 4的倍数.

时间复杂度(time complexity)

空间复杂度(space complexity)

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai