企业网站建设和管理,微信开发者工具如何使用,建设九九网站,色流网站如何做【LetMeFly】292.Nim 游戏#xff1a;脑筋急转弯
力扣题目链接#xff1a;https://leetcode.cn/problems/nim-game/
你和你的朋友#xff0c;两个人一起玩 Nim 游戏#xff1a;
桌子上有一堆石头。你们轮流进行自己的回合#xff0c; 你作为先手 。每一回合#xff0c…【LetMeFly】292.Nim 游戏脑筋急转弯
力扣题目链接https://leetcode.cn/problems/nim-game/
你和你的朋友两个人一起玩 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 231 - 1
方法一脑筋急转弯看能否整除4
这种题可以模拟几个试试。当轮到我时
1、2、3必胜4必输不论拿多少个剩下的必定是1、2、3下一个人必胜5、6、7必胜5、6、7都有办法在一次拿石子后剩下4个下一个人必输8必输不论拿多少个剩下的必定是5、6、7下一个人必胜…
相信聪明的你一定已经发现规律了。轮到自己时 4 4 4的倍数必输否则必胜。
由于自己是先手就看初始数量是否为 4 4 4的倍数若是则必输否则就一次操作将剩下的石子数量变成 4 4 4的倍数。
时间复杂度 O ( 1 ) O(1) O(1)空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
public:bool canWinNim(int n) {return n % 4;}
};Python
class Solution:def canWinNim(self, n: int) - bool:return n % 4 ! 0 # 注意这里不能像C一样只return一个n%4同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136024724
