1.Nim游戏

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:
输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

这道题很简单，我在中学时候就见过，一方只需要拿完石头后剩下石头数量为4的倍数，就一定胜利。因为接下来对手如果拿k块石头，我们只需拿4-k块石头，使继续保持剩下的石头为4的倍数，直至最后剩余石头数量为0。

所以判断自己能否胜利的条件就是自己最开始拿石头的时候，石头数量是否为4的倍数。如果不是4的倍数，只需拿掉相应的数量，使剩余石头数量为4的倍数，则自己能够赢得胜利。相反，如果石头数量为4的倍数，则不管你拿几块（1-3）石头，则你拿完之后剩余石头数量都不可能是4的倍数，则对手只需继续拿掉对应数量的石头使剩余石头数量为4的倍数(比如你拿1，他就拿3)，则他一定胜利。

代码也很直接了：

class Solution {
public:
    bool canWinNim(int n) {
        return n%4;
    }
};

2.灯泡开关

初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。

示例:

输入: 3
输出: 1 
解释: 
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

首先思考：灯泡i会被按几次？这其实相当于求i有几个因子 比如灯泡8,一共会被按4次，分别是第一轮 第二轮 第四轮 第八轮。

如果灯泡被按奇数次，则此灯泡最后亮着，如果为偶数次则最后熄灭。即如果i有奇数个因子，则第i个灯泡最后亮着，如果i有偶数个因子。则第i个灯泡最后熄灭。

那么很容易想到，可以用穷举法求出每个位置的因子数，再判断因字数的奇偶性，则可以得到对应灯泡的亮灭，再统计亮灯的个数。

当然，这种做法是很慢的，那么有没有什么方法改进呢？我们要知道，一个数的因子总是成对存在的，比如8的因子，1×8，2×4。只有平方数的因子数为偶数，比如4，9，16。因此，我们不需要求出一个数的因子，只需要判断它是否是平方数，就可以知道它的因子数量是奇是偶，这省去了求因子的过程。

那么还有没有更简洁的方法呢？当然有，不然怎么能叫脑筋急转弯。我们试想一下，对于n=16，会有多少灯最后亮着？我们找其奇数个因子的数，有1，4，9，16，正好对应1-4的平方，那么对于n=16-24之间，有奇数个因子的数仍然是这4个，即sqrt(n)。所以判断有多少个数有奇数个因子，我们只需对n开根号即可。

代码同样简洁：

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

3.飞机座位分配概率

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，
当他们自己的座位被占用时，随机选择其他座位
n 位乘客坐在自己的座位上的概率是多少？

示例 1：
输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：
输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

这道题最直观的可以求递推公式，这里不多讲。我们只讲一个最简化的方法，

• 我们只关注第1个和第n个位置，每一个人坐到这两个位置上的几率都是相等的，下面我们对这一点加以说明。
• 比如对于第一个人，坐到第一个和第n个位置的几率都是1/n，
• 对于第i个人，如果他位置没有被占，那么他只会坐到第i个位置，如果它的位置被占了，证明第1个位置和第n个位置此时一定没有人坐。
• 为什么此时第1和n个位置一定没有人坐？因为从i=2开始，当前i个人坐下之后，第i个位置一定有人坐，所以前i个人坐下后，第2到i-1的位置一定都有人坐，如果i的位置被占了，只能证明前i-1个人坐的2-i的位置，所以第1个和第n个位置一定没有人坐。
• 所以此时第i个人坐到第1和第个位置的几率仍然相等。
• 对于第n个人来说，他只可能坐到第1个位置和第n个位置(因为2到n-1位置的人都有票)，而前面每个人坐到第1和n位置的几率都相等，所以1和n位置空下来的几率也相等。所以第n个人坐到第n个位置几率为0.5。

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        if(n==1)return 1;
        return 0.5;
    }
};

 

以上题目来自均leetcode