LeetCode Power of Three Given an integer, write a function to determine if it is a power of three. Follow up: Could you do it without using any loop / recursion?

---

判断一个数是否是3的幂次方，能否不用递归或迭代的方法。 递归和迭代的方法都类似，就是不断除以3，看能否整除直到最后为1。完整代码如下： [cpp] class Solution { public: bool isPowerOfThree(int n) { if(n <= 0) return false; if(n == 1) return true; if(n % 3 == 0) return isPowerOfThree(n / 3); else return false; } }; [/cpp] 本代码提交AC，用时65MS。 网上题解有一些有意思的方法，摘录几个如下。 因为传入的n的范围是int，int范围内最大的3的幂次方的数是1162261467，所以任意一个3的幂，都应该能被1162261467整除，所以只要除一下就可以判断。完整代码如下： [cpp] class Solution { public: bool isPowerOfThree(int n) { return n > 0 ? (1162261467 % n == 0) : false; } }; [/cpp] 本代码提交AC，用时59MS。 当然还有一种更简单粗暴的方法，int范围内3的幂就20个，直接枚举出来用if判断就好了。。。 还有一种思路是用log，如果n是3的幂，则$$log_3(n)$$一定是整数，$$log_3$$可以用换底公式换成$$log_{10}$$。完整代码如下： [cpp] class Solution { public: bool isPowerOfThree(int n) { double p = log10(n) / log10(3); return (p – int(p)) == 0; } }; [/cpp] 本代码提交AC，用时62MS。]]>