Leetcode -292.Nim游戏

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

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

示例 1：
输入：n = 4
输出：false
解释：以下是可能的结果 :

1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3. 你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
   在所有结果中，你的朋友是赢家。

示例 2：
输入：n = 1
输出：true

示例 3：
输入：n = 2
输出：true

提示：
1 <= n <= 231 - 1

1. 递归（时间复杂度大，超时）

    	bool canWinNim(int n){if (n >= 1 && n <= 3)return true;else if (n == 4)return false;elsereturn canWinNim(n - 4);}
   

2. 数学方法

从数学角度推理可得，只要在我拿石头时，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

1. 递归

    	bool isPowerOfThree(int n){//小于等于0返回falsseif (n <= 0)return false;//等于1即使3^0，返回trueelse if (n == 1)return true;//若n取模不为0，不是3的幂else if (n % 3 != 0)return false;//除了以上三种情况，进入递归elsereturn isPowerOfThree(n / 3);}
   

2. 试除法

我们的思路是，将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的幂，返回truewhile (!(n % 3))n /= 3;if (n == 1)return true;elsereturn 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+1int* 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;}

中国互联网产业年会