【Leetcode -292.Nim游戏 -326. 3的幂 -338.比特位计数】
【Leetcode -292.Nim游戏 -326. 3的幂 -338.比特位计数】
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;
}腾讯云开发者
