共计 2676 个字符，预计需要花费 7 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
292.Nim 游戏
877. 石子游戏
319. 灯泡开关
———–
下文是我在 LeetCode 刷题过程中总结的三道乏味的「脑筋急转弯」题目，能够应用算法编程解决，但只有稍加思考，就能找到法则，间接想出答案。
一、Nim 游戏
游戏规则是这样的：你和你的敌人背后有一堆石子，你们轮流拿，一次至多拿一颗，最多拿三颗，谁拿走最初一颗石子谁获胜。
假如你们都很聪慧，由你第一个开始拿，请你写一个算法，输出一个正整数 n，返回你是否能赢（true 或 false）。
比方当初有 4 颗石子，算法应该返回 false。因为无论你拿 1 颗 2 颗还是 3 颗，对方都能一次性拿完，拿走最初一颗石子，所以你肯定会输。
首先，这道题必定能够应用动静布局，因为显然原问题存在子问题，且子问题存在反复。然而因为你们都很聪慧，波及到你和对手的博弈，动静布局会比较复杂。
咱们解决这种问题的思路个别都是反着思考 ：
如果我能赢，那么最初轮到我取石子的时候必须要剩下 1~3 颗石子，这样我能力一把拿完。
如何营造这样的一个场面呢？显然，如果对手拿的时候只剩 4 颗石子，那么无论他怎么拿，总会剩下 1~3 颗石子，我就能赢。
如何逼迫对手面对 4 颗石子呢？要想方法，让我抉择的时候还有 5~7 颗石子，这样的话我就有把握让对方不得不面对 4 颗石子。
如何营造 5~7 颗石子的场面呢？让对手面对 8 颗石子，无论他怎么拿，都会给我剩下 5~7 颗，我就能赢。
这样始终循环上来，咱们发现只有踩到 4 的倍数，就落入了陷阱，永远逃不出 4 的倍数，而且肯定会输。所以这道题的解法非常简单：
bool canWinNim(int n) {
// 如果上来就踩到 4 的倍数，那就认输吧
// 否则，能够把对方管制在 4 的倍数，必胜
return n % 4 != 0;
}二、石头游戏
游戏规则是这样的：你和你的敌人背后有一排石头堆，用一个数组 piles 示意，piles[i] 示意第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，然而只能拿走最右边或者最左边的石头堆。所有石头被拿完后，谁领有的石头多，谁获胜。
假如你们都很聪慧 ，由你第一个开始拿，请你写一个算法，输出一个数组 piles，返回你是否能赢（true 或 false）。
留神，石头的堆的数量为偶数，所以你们两人拿走的堆数肯定是雷同的。石头的总数为奇数，也就是你们最初不可能领有雷同多的石头，肯定有输赢之分。
举个例子，piles=[2, 1, 9, 5]，你先拿，能够拿 2 或者 5，你抉择 2。
piles=[1, 9, 5]，轮到对手，能够拿 1 或 5，他抉择 5。
piles=[1, 9] 轮到你拿，你拿 9。
最初，你的对手只能拿 1 了。
这样下来，你总共领有 2 + 9 = 11 颗石头，对手有 5 + 1 = 6 颗石头，你是能够赢的，所以算法应该返回 true。
你看到了，并不是简略的挑数字大的选，为什么第一次抉择 2 而不是 5 呢？因为 5 前面是 9，你要是贪图一时的利益，就把 9 这堆石头裸露给对手了，那你就要输了。
这也是强调单方都很聪慧的起因，算法也是求最优决策过程下你是否能赢。
这道题又波及到两人的博弈，也能够用动静布局算法暴力试，比拟麻烦。但咱们只有对规定深刻思考，就会大惊失色：只有你足够聪慧，你是必胜无疑的，因为你是后手。
boolean stoneGame(int[] piles) {return true;} 这是为什么呢，因为题目有两个条件很重要：一是石头总共有偶数堆，石头的总数是奇数。这两个看似减少游戏公平性的条件，反而使该游戏成为了一个割韭菜游戏。咱们以 piles=[2, 1, 9, 5] 解说，假如这四堆石头从左到右的索引别离是 1，2，3，4。
如果咱们把这四堆石头按索引的奇偶分为两组，即第 1、3 堆和第 2、4 堆，那么这两组石头的数量肯定不同，也就是说一堆多一堆少。因为石头的总数是奇数，不能被平分。
而作为第一个拿石头的人，你能够管制本人拿到所有偶数堆，或者所有的奇数堆。
你最开始能够抉择第 1 堆或第 4 堆。如果你想要偶数堆，你就拿第 4 堆，这样留给对手的抉择只有第 1、3 堆，他不管怎么拿，第 2 堆又会裸露进去，你就能够拿。同理，如果你想拿奇数堆，你就拿第 1 堆，留给对手的只有第 2、4 堆，他不管怎么拿，第 3 堆又给你裸露进去了。
也就是说，你能够在第一步就察看好，奇数堆的石头总数多，还是偶数堆的石头总数多，而后步步为营，就所有尽在掌控之中了。晓得了这个破绽，能够整一整不知情的同学了。
三、电灯开关问题
这个问题是这样形容的：有 n 盏电灯，最开始时都是关着的。当初要进行 n 轮操作：
第 1 轮操作是把每一盏电灯的开关按一下（全副关上）。
第 2 轮操作是把每两盏灯的开关按一下（就是按第 2，4，6… 盏灯的开关，它们被敞开）。
第 3 轮操作是把每三盏灯的开关按一下（就是按第 3，6，9… 盏灯的开关，有的被敞开，比方 3，有的被关上，比方 6）…
如此往返，直到第 n 轮，即只按一下第 n 盏灯的开关。
当初给你输出一个正整数 n 代表电灯的个数，问你通过 n 轮操作后，这些电灯有多少盏是亮的？
咱们当然能够用一个布尔数组示意这些灯的开关状况，而后模仿这些操作过程，最初去数一下就能出后果。然而这样显得没有灵性，最好的解法是这样的：
int bulbSwitch(int n) {return (int)Math.sqrt(n);
}什么？这个问题跟平方根有什么关系？其实这个解法挺精妙，如果没人通知你解法，还真不好想明确。
首先，因为电灯一开始都是敞开的，所以某一盏灯最初如果是点亮的，必然要被按奇数次开关。
咱们假如只有 6 盏灯，而且咱们只看第 6 盏灯。须要进行 6 轮操作对吧，请问对于第 6 盏灯，会被按下几次开关呢？这不难得出，第 1 轮会被按，第 2 轮，第 3 轮，第 6 轮都会被按。
为什么第 1、2、3、6 轮会被按呢？因为 6=1*6=2*3。个别状况下，因子都是成对呈现的，也就是说开关被按的次数个别是偶数次。然而有非凡状况，比如说总共有 16 盏灯，那么第 16 盏灯会被按几次?
16=1*16=2*8=4*4
其中因子 4 反复呈现，所以第 16 盏灯会被按 5 次，奇数次。当初你应该了解这个问题为什么和平方根无关了吧？
不过，咱们不是要算最初有几盏灯亮着吗，这样间接平方根一下是啥意思呢？略微思考一下就能了解了。
就假如当初总共有 16 盏灯，咱们求 16 的平方根，等于 4，这就阐明最初会有 4 盏灯亮着，它们别离是第 1*1=1 盏、第 2*2=4 盏、第 3*3=9 盏和第 4*4=16 盏。
就算有的 n 平方根后果是小数，强转成 int 型，也相当于一个最大整数上界，比这个上界小的所有整数，平方后的索引都是最初亮着的灯的索引。所以说咱们间接把平方根转成整数，就是这个问题的答案。
