[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 <= 0) return false;
        for (;;) {
            if (n == 1) return true;
            if (n % 3 != 0) return false;
            n /= 3;
        }
    }
};

也可以用递归实现，原理其实大同小异（以Power of Four为例）：

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        if (num == 1) return true;
        if (num % 4 != 0) return false;
        else return isPowerOfFour(num / 4);
    }
};

最后一种通用的方法很巧妙，是利用数学的方法来实现的（以Power of Three为例）。首先要知道的是，假如一个数是3的幂，那log₃n一定是整数，接着利用高中数学中的换底公式（log_ab = log_cb / log_ca），我们取c=10，则有log₁₀n / log₁₀3一定是一个整数。那么我们只需判断log₁₀n / log₁₀3是否为整数即可。是，n就是一个3的幂，反之亦然。

给定一个数m，怎么判断它是否整数呢？在C++中，只要m - (int)m == 0，即可说明它是整数。

综上，代码如下：

class Solution {
public:
    bool isPowerOfThree(int n) {
        return (n > 0 && int(log10(n) / log10(3)) - log10(n) / log10(3) == 0);
    }
};

上面就是这类算法题的通用解法了，总结一下，就是循环、递归和数学知识——换底公式的利用。接下来看看各自的特殊解法：

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 = 0;
        while (n > 0) {
            cnt += n & 1;
            n = n >> 1; 
        }
        return cnt == 1;
    }
};

（2）

将这个数-1，然后两个数按位相与，假如这个数是2的幂，所得的数肯定是0。

以8为例。8的二进制为1000,7的二进制为0111，按位相与结果为0。

根据这个方法，代码如下：

class Solution {
public:
    bool isPowerOfTwo(int n) {
       return (n > 0 && !(n & (n -  1)));
    }
};

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 > 0 && !(num & (num - 1)) && (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 > 0 && !(num & (num - 1)) && (num - 1) % 3 == 0;
    }
};