题目: Nim 游戏
你和你的朋友, 两个人一起玩 Nim 游戏: 桌子上有一堆石头, 每次你们轮流拿掉 1 - 3 块石头. 拿掉最后一块石头的人就是获胜者. 你作为先手.
你们是聪明人, 每一步都是最优解. 编写一个函数, 来判断你是否可以在给定石头数量的情况下赢得游戏.
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头, 那么你永远不会赢得比赛;
因为无论你拿走 1 块, 2 块 还是 3 块石头, 最后一块石头总是会被你的朋友拿走.
思考:
如果石头为 1,2,3, 你先手都可以一次拿走获胜, 而 4 块时无论你拿几块, 对手下次都可以一次拿完.
5 块石头时你可以只拿 1 块, 剩给对手 4 块, 这样你就可以获胜. 6 块 7 块同样可以先手拿 2 块和 3 块, 给对手剩下 4 块, 自己获胜.
而 8 块时无论你拿多少块, 对手都可以剩下 4 块给你, 这样你就输了.
接下来 9 块同样可以先拿 1 块, 剩下对手随便拿几块你都可以剩下 4 块给对手, 最终你会获胜. 以此类推当石头数为 4,8,12,16... 即为 4 的倍数时会输, 其他数量时可以获胜.
实现:
- class Solution {
- int count = 0;
- public boolean canWinNim(int n) {
- if (n % 4 == 0)
- return false;
- else
- return true;
- }
- }
时间复杂度: O(1), 只进行了一次检查.
空间复杂度: O(1), 没有使用额外的空间.
来源: https://juejin.im/post/5c8682916fb9a049f81a1f75