5.13 一行代码就能解决的算法问题
5.13.1 Nim游戏
你和你的朋友，两个人一起玩 Nim 游戏：
桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/nim-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 解决这种问题的思路一般都是反着思考
如果我能赢，那么最后轮到我拿石子的时候必须剩下1~3颗，这样我才能一次全部拿完
如何逼迫对方面对4颗石子呢？要想办法，让我选择的时候还有5~7颗石头，这样我就有把握让对方不得不面对4颗石头
如何营造57颗石头的局面呢?让对手面对8颗石头，无论它怎么拿，都会给我剩下57颗，我就能赢
我们想一下，对手都是什么情况?都是剩下4的倍数颗的时候，他一定会到我们的圈套里面!
public boolean canWinNim(int n) {
return n%4 != 0;
}5.13.2 石子游戏
Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。
Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。
假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/stone-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 注意:并不是简单地调数字大的选，比如说
piles=[2,1,9,5]你先拿，可以先拿2颗或者5颗，你选择两颗 [1,9,5]轮到对手，你可以拿到1颗或者5颗[1,9]，轮到你，你可以拿9颗- 如此下来，你总共有2+9颗石子，而你的对手只有5+1颗石子
看起来很头痛，但是仔细分析发现，题干说他们都发挥出最佳水平，只要你足够聪明，你是必胜的
为什么先手总是必胜，因为题目有两个条件很重要
- 石子一共有偶数堆
- 石子的总数总是奇数
我们以piles=[2,1,9,5]为例讲解，假设这4堆石子从左到右的索引分别是1,2,3,4，如果我们把这4堆石子按照索引的奇偶分为两组，也就是第1、3堆和第2/4堆，那么这两组石子的数量肯定是不一样的，也就是一堆多一堆少，因为石子的总数是奇数，不能够被平分
而作为第一个拿石子的人，你可以控制自己拿到所有的偶数堆，或者拿到所有的奇数堆。
最开始可以选择第一堆或者第4堆，如果你想要偶数堆，就拿第四堆，这样留给对手的选择只有第1、3堆，它不管怎么拿，第二堆都会暴露出来，你就可以拿。奇数堆也是同理
也就是说，你可以在第一步就观察号，奇数堆的石子总数多，还是偶数堆的石子总数多，然后步步为营，就一切尽在掌控之中了
5.13.3 电灯开关问题
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。
第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/bulb-switcher
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
第1轮操作是把每一盏灯的开关按一下
第2轮操作是把每两盏灯的开关按一下(2,4,6,8)
第3轮操作是把每三盏灯的开关按一下(3,6,9)
如此往复，直到第n轮，即只按一下第n盏灯的开关
问经过n轮操作后，这些电灯有多少盏是亮的?
首先，因为电灯一开始都是关闭的，所以某一盏灯最后如果是点亮的，必然会被按奇数次开关
假设只有6盏灯，而且只看第6盏灯，而且进行6轮操作，请问对于第6栈灯，会被按下几次开关呢?
6=1*6=2*3也就是说第一轮会被按，第6轮会被按，第2轮会被按，第3轮会被按，一般情况下因子都成对出现的，也就是说被按开关的次数一般都会是偶数次，但是有特殊情况，也就是出现了重复因子的时候，这时候因子成对出现但是有重复，这时候因子数目就会变成奇数个
假设现在总共有16栈灯，求16的平方根，等于4，这就说明最后有4栈灯会亮着，它们分别是1*1=1,2*2=4,3*3=9,4*4=16
平方根结果有可能是小数，强转为int型，也就相当于一个最大整数的上界，比这个上界小的所有整数，平方后的索引都是最后亮着的灯的索引，所以直接把平方根转成整数，就是这个问题的答案
public int bulbSwitch(int n) {
return (int)(Math.sqrt(n));
}
