Nim 游戏
你和你的朋友,两个人一起玩 Nim游戏:
- 桌子上有一堆石头。
- 你们轮流进行自己的回合,你作为先手。
- 每一回合,轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n
的情况下赢得游戏。如果可以赢,返回 true
;否则,返回 false
。
示例 1:
输入:n = 4
输出:false
解释:如果堆中有 4 块石头,那么你永远不会赢得比赛;
因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。
有题意可以得到下表:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
T | T | T | F | T | T | T | F | T |
解释:
只有三个石子,全拿走就行了,结果自然为 T。
但是四个的话,无论你拿走几个,对方都会有1 ~ 3个可以拿,也就是说:
① 你拿一个,对方的视角就是还有三个石子,参考表中,他必赢;
② 你拿两个,对方的视角就是还有两个石子,参考表中,他必赢;
② 你拿三个,对方的视角就是还有一个石子,参考表中,他必赢;
可以发现规律,就是 只要 n - 1 == T || n - 2 == T || n - 3 == T 有一个满足条件,变为 T;
class Solution { public: bool canWinNim(int n) { if(n % 4 == 0)return false; else return true; } };
石子游戏
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i]
。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。
亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true
,当李赢得比赛时返回 false
。
示例:
输入:[5,3,4,5] 输出:true 解释: 亚历克斯先开始,只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗,这一行就变成了 [3,4,5] 。 如果李拿走前 3 颗,那么剩下的是 [4,5],亚历克斯拿走后 5 颗赢得 10 分。 如果李拿走后 5 颗,那么剩下的是 [3,4],亚历克斯拿走后 4 颗赢得 9 分。 这表明,取前 5 颗石子对亚历克斯来说是一个胜利的举动,所以我们返回 true 。
纯思维题:
class Solution { public: bool stoneGame(vector<int>& piles) { return true; } };