Leetcode -292.Nim游戏
你和你的朋友，两个人一起玩 Nim 游戏：
桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例 1：
输入：n = 4
输出：false
解释：以下是可能的结果 :
- 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
- 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
- 你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。
示例 2：
输入：n = 1
输出：true
示例 3：
输入：n = 2
输出：true
提示：
1 <= n <= 231 - 1
- 递归（时间复杂度大，超时）
bool canWinNim(int n) { if (n >= 1 && n <= 3) return true; else if (n == 4) return false; else return canWinNim(n - 4); }
- 数学方法
从数学角度推理可得，只要在我拿石头时，n的值是4的倍数时，我就会输，否则，我就赢；
bool canWinNim(int n) { return n % 4 != 0; }
Leetcode -326. 3的幂
给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
示例 1：
输入：n = 27
输出：true
示例 2：
输入：n = 0
输出：false
示例 3：
输入：n = 9
输出：true
示例 4：
输入：n = 45
输出：false
提示：
- 2^31 <= n <= 2^31 - 1
- 递归
bool isPowerOfThree(int n) { //小于等于0返回falsse if (n <= 0) return false; //等于1即使3^0，返回true else if (n == 1) return true; //若n取模不为0，不是3的幂 else if (n % 3 != 0) return false; //除了以上三种情况，进入递归 else return isPowerOfThree(n / 3); }
- 试除法
我们的思路是，将n一直除以3，看它的余数是否等于0，若等于0，就取它的商继续除，直到它的余数等于1或者不能整除3；若等于1，即是3的幂；若不为1，返回false；
bool isPowerOfThree(int n) { if (n <= 0) return false; //用n一直除以3，直到n%3不等于0，即n不能整除3，就返回falses //若n能整除3，就取它的商，一直到n为1，当n为1，即是3的幂，返回true while (!(n % 3)) n /= 3; if (n == 1) return true; else return false; }
Leetcode -338.比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，
返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0, 1, 1]
解释：
0 – > 0
1 – > 1
2 – > 10
示例 2：
输入：n = 5
输出：[0, 1, 1, 2, 1, 2]
解释：
0 – > 0
1 – > 1
2 – > 10
3 – > 11
4 – > 100
5 – > 101
提示：
0 <= n <= 10^5
我们的思路是，判断每个数字上二进制的每个位是否是1，若是1，就用count++记录；否则，继续判断下一位；
int* countBits(int n, int* returnSize) { //开辟好返回的空间，长度为n+1 int* p = (int*)malloc(sizeof(int) * (n + 1)); assert(p); *returnSize = n + 1; //遍历0-n的数字 for (int i = 0; i <= n; i++) { //用count来记录每个数字二进制上1的个数 int count = 0; //判断每个数字二进制上的最后一位 //将它按位与1，就能知道最后一位是什么，如果是1，count就++ for (int j = 0; j < 32; j++) { if ((i >> j) & 1 == 1) { count++; } } //将count放进开辟好的数组 p[i] = count; } //最后返回这个数组 return p; }
