292.Nim游戏 | 877.石子游戏 | 319.灯泡开关

一行代码就能解决的算法题 :: labuladong的算法小抄 (gitee.io)

292.Nim游戏

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4
输出：false 
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。

思路：

 如果石头数是4的倍数，那么我先手肯定输
 如果不是4的倍数，那么我先手，就可以让我取完的石头数是4的倍数，那么对方必输
 所以推得——n%(m+1)==0?false:true，m是可以取的石头的最大值

class Solution {
public:
    bool canWinNim(int n) {
        return n%4==0?false:true;
    }
};

877.石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

示例 1：

输入：piles = [5,3,4,5]
输出：true
解释：
Alice 先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

思路：

先手必赢，因为共有偶数堆石子，石子总数是奇数

piles = [5,3,4,5],因为有偶数堆石子,所以按索引的奇偶可以均分成两堆,奇数堆[5,4]和偶数堆[3,5]

因为石子总数是奇数，所以必不能平分，例中奇数堆比偶数堆大

所以先手的人可以先判断奇数堆和偶数堆谁的总数大，然后一步步拿到所有的奇数堆或偶数堆，获胜

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

319.灯泡开关

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

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

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

 思路：

初始时灯泡都是灭的，所以灯泡要亮着，需要按奇数次

若n=6，按6轮，则第六个灯泡被按的轮次有（1,2,3,6）共4次，因为6=1*6=2*3，所以是因子时会被按到

又因为因子是成对出现的，所以一般都是按偶数次，灯还是灭的

而平方数的因子是重复的，1=1*1，4=2*2，相当于只按了一次，那么总因子的数量就是奇数个了，灯就会亮（一个整数n是另一整数的平方的充分必要条件是除尽n的正整数的数目为奇数）

即小于等于n的平方数位置的灯泡n轮后还会亮着

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

754. 到达终点数字

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

• 每次你可以选择向左或向右移动。
• 第 i 次移动（从  i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

示例 1:

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。

示例 2:

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。

 思路：数学法

首先只朝一个方向移动，只有当移动的总距离 num 的值大于等于 t ，并且 num 减 t 是偶数，
才满足到达 target 所需的最小移动次数。
因为 1 + 2 + 3 + 4 = 10
而     1 + 2 - 3 + 4 = 4
两者之差为6，即2 * 3，所以变换方向走一次会使当前位置减小一个偶数(2，4，6，8，10...任意偶数均可凑成)
故目前的位置比target领先的是一个偶数时，说明可以在前面路径上选择一个或几个点，变换方向往回走，这样就能凑出target了 。

class Solution {
public:
    int reachNumber(int target) {
        int num=0;
        int res=1;
        int t=abs(target);//不论最终目标是正还是负，走的最小步数是相同的
        while(num2!=0)//当num
        {
            num+=res;//num=1+2+3+4+5...
            res++;
        }
        return res-1;
    }
};
//一开始思路为BFS，但超时了，用例中-10^9
// 1 2 3 4 5 6 7 8 9 10 11
//                  0
//          1              -1 
//      3     -1       -3      1
//    6   0  2  -4   0   -6  4  -2

89. 格雷编码

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

思路：格雷码计算方法：第i 位格雷码= i 异或 i>>1 

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        for(int i=0;i<1<
            int gray=i^(i>>1);
            res.push_back(gray);
        }
        return res;
    }
};