你和你的朋友,两个人一起玩 Nim 游戏:
桌子上有一堆石头。 你们轮流进行自己的回合, 你作为先手 。 每一回合,轮到的人拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回 true;否则,返回 false 。
示例 1: 输入:n = 4 输出:false 解释:以下是可能的结果 :
示例 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;
}
给定一个整数,写一个函数来判断它是否是 3 的幂次方。如果是,返回 true ;否则,返回 false 。
整数 n 是 3 的幂次方需满足:存在整数 x 使得 n == 3x
示例 1: 输入:n = 27 输出:true
示例 2: 输入:n = 0 输出:false
示例 3: 输入:n = 9 输出:true
示例 4: 输入:n = 45 输出:false
提示:
递归
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;
}
给你一个整数 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;
}