给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1:
输入: 27
输出: true
示例 2:
输入: 0
输出: false
示例 3:
输入: 9
输出: true
示例 4:
输入: 45
输出: false
方法一：
用最常规的方法，直接用除余来判断
- 如果余数为零就直接除3，一直循环到n为3为止
- n == 1是因为一开始传过来的n就是1，3的0次方等于1，所以1也是对的
复杂度
- 时间复杂度：O(log3n)，除数是用对数表示的。
- 空间复杂度：O(1)，没有使用额外的空间。
func isPowerOfThree(n int) bool {
if n == 0 {return false}
for {
if n==1 || n==3 {
return true
}
if n % 3 == 0 {
n = n / 3
} else {
return false
}
}
// return n > 0 && 1162261467 % n == 0;
if n < 1 {
return false
}
s := strconv.FormatInt(int64(n), 3)
return s[0:1] == "1" && strings.Count(s, "0") == len(s)-1
}
进阶：
你能不使用循环或者递归来完成本题吗？
方法二：
利用3进制来判断
- 将n转化为3进制数的字符串，只要只有第一个数字为1，其他都为0，说明这个数是3的幂次方
复杂度
- 时间复杂度：O(log3n)。
假设：
strconv.FormatInt() - 转换为3进制数，和方法一类似，都是求余。复杂性应该类似于方法一：O(log3n)的复杂性。
regexp.MatchString - 方法迭代整个字符串。n 以 3 为基数表示的位数是O(log3n)。 - 空间复杂度：O(log3n)。我们使用两个附加变量。
以 3 为基数表示数字的字符串（大小为log3n） 正则表达式的字符串（常量大小）
func isPowerOfThree(n int) bool {
if n < 1 {
return false
}
s := strconv.FormatInt(int64(n), 3)
//正则表达式,检查字符串是否以1 ^1 开头，后跟 0 或 多个 0* 并且不包含任何其他值 $。
a,_ := regexp.MatchString("^10*$",s)
return a
}
执行用时：108 ms, 在所有 Go 提交中击败了8.55%的用户
内存消耗：6.9 MB, 在所有 Go 提交中击败了11.48%的用户
能看到其实上面的效率会有点慢，我们可以优化一下
func isPowerOfThree(n int) bool {
if n < 1 {
return false
}
s := strconv.FormatInt(int64(n), 3)
//直接用字符串来判断，开头为一，其他都为0
return s[0:1] == "1" && strings.Count(s, "0") == len(s)-1
}
执行用时：28 ms, 在所有 Go 提交中击败了75.09%的用户
内存消耗：6 MB, 在所有 Go 提交中击败了100.00%的用户
还有一种适用于该题的数学解法，在int范围内的3的幂只有19个，分别是
1, 3, 9, 45, 99, 111, 153, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721,
129140163, 387420489, 1162261467
最大的第19个为1162261467
因为 3 是质数，所以 3^19 的除数只有 33,31, …3 ^19，因此我们只需要将 3^19 除以 n。若余数为 0 意味着 n 是 3^19的除数，因此是 3 的幂。
复杂度
- 时间复杂度：O(1)。
- 空间复杂度：O(1)。
func isPowerOfThree(n int) bool {
return n > 0 && 1162261467 % n == 0;
}
执行用时：24 ms, 在所有 Go 提交中击败了84.39%的用户
内存消耗：6.1 MB, 在所有 Go 提交中击败了29.51%的用户
