[LeetCode] 231 Power of Two && 326 Power of Three && 342 Power of Four

这三道题目都是一个意思,就是判断一个数是否为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 - ) % == ;
}
};
上一篇:Leetcode 231 Power of Two 数论


下一篇:WTS 2.1.18124.1 彻底抛弃了 15063(Win 10 创意者更新)