问题描述

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?
Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

思路分析

虽然是Easy题，但感觉并没有很简单，主要的点在于不能使用循环。
解法是用log函数，由于log函数返回的值是近似值（小数点后11位小数），因此要将其与取整的值进行比较，差值小于10^-11即可认为log函数返回的是整数，即n是3的整数次幂。
想了一下，能否利用差值小于δ来判断log函数得到的值是整数，在于最小的可能差值是多少。
log₃(2³¹-1) = 19.5588...
因此最大的3次幂值是3¹⁹ = 1162261467
而log₃1162261468 = 19.0000000007831...
该值与19相差超过0.0000000001。
因此在32位整数范围内，如果log函数返回值与其取整值差别小于0.0000000001，那么它就是一个真实的整数。

AC代码

class Solution(object):
    def isPowerOfThree(self, n):
        if n > 0:
            a = math.log(n, 3)
        else:
            return False
        if abs(a - round(a)) < 0.00000000001:
            return True
        else:
            return False

Runtime: 436 ms, which beats 54.03% of Python submissions.