这三道题目都是一个意思,就是判断一个数是否为2/3/4的幂,这几道题里面有通用的方法,也有各自的方法,我会分别讨论讨论。
原题地址:
231 Power of Two:https://leetcode.com/problems/power-of-two/description/
326 Power of Three:https://leetcode.com/problems/power-of-three/description/
342 Power of Four :https://leetcode.com/problems/power-of-four/description/
解法:
先说一下这类题型的通用解法:
首先肯定是循环了,将n一直除以3,当n最后为1的时候说明这是3的次方数;假如不是3的倍数,即n%3不为0,则不是3的幂。这里要注意的是两个if的顺序不能调转。因为任意数的0次方都为1,所以1肯定是。下面是代码(以Power of Three为例):
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= ) return false;
for (;;) {
if (n == ) return true;
if (n % != ) return false;
n /= ;
}
}
};
也可以用递归实现,原理其实大同小异(以Power of Four为例):
class Solution {
public:
bool isPowerOfFour(int num) {
if (num <= ) return false;
if (num == ) return true;
if (num % != ) return false;
else return isPowerOfFour(num / );
}
};
最后一种通用的方法很巧妙,是利用数学的方法来实现的(以Power of Three为例)。首先要知道的是,假如一个数是3的幂,那log3n一定是整数,接着利用高中数学中的换底公式(logab = logcb / logca),我们取c=10,则有log10n / log103一定是一个整数。那么我们只需判断log10n / log103是否为整数即可。是,n就是一个3的幂,反之亦然。
给定一个数m,怎么判断它是否整数呢?在C++中,只要m - (int)m == 0,即可说明它是整数。
综上,代码如下:
class Solution {
public:
bool isPowerOfThree(int n) {
return (n > && int(log10(n) / log10()) - log10(n) / log10() == );
}
};
上面就是这类算法题的通用解法了,总结一下,就是循环、递归和数学知识——换底公式的利用。接下来看看各自的特殊解法:
1.Power of Two
我们可以观察一下2的次方数的二进制形式:
1 1
2 10
4 100
8 1000
16 10000
可以看出来,每个2的次方数的二进制形式都仅含一个1,其余为0;根据这个规律,我们可以想出两种方法:
(1)
判断传入的n的最右一位(最低位)是否为1,然后向右一位,统计1的个数,最后加入1的个数为1,那么肯定是2的幂了。代码如下:
class Solution {
public:
bool isPowerOfTwo(int n) {
int cnt = ;
while (n > ) {
cnt += n & ;
n = n >> ;
}
return cnt == ;
}
};
(2)
将这个数-1,然后两个数按位相与,假如这个数是2的幂,所得的数肯定是0。
以8为例。8的二进制为1000,7的二进制为0111,按位相与结果为0。
根据这个方法,代码如下:
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n > && !(n & (n - )));
}
};
2.Power of Three
很可惜,这个没有属于自己的特殊解法。看回上面的通用解法吧!
3.Power of Four
(1)
假如一个数是4的幂指数,那么它首先肯定是2的幂。
因此,这个题目的特殊解法是在Power of Two的特殊解法(2)的基础上拓展的,观察:
1 1
4 100
16 10000
64 1000000
与Power of Two相比,这些二进制数也是只有一个1,但同时也要注意到1的位置全是处于基数位。因此假如一个数是4的幂,它肯定在满足2的幂的条件下,又满足与0x55555555(10101010101.....)按位相与等于它本身的条件。因此实现代码如下:
class Solution {
public:
bool isPowerOfFour(int num) {
return num > && !(num & (num - )) && (num & 0x55555555) == num;
}
};
(2)
观察2的幂:1,2,4,8,16,32,64
观察4的幂:1,4,16,64
可以发现,在2的幂的基础上,只要一个数-1可以被3整除,那么这个数就是4的幂了。(3,15,63可以,7,31不行)
因此实现代码如下:
class Solution {
public:
bool isPowerOfFour(int num) {
return num > && !(num & (num - )) && (num - ) % == ;
}
};