No.326 3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

• -231 <= n <= 231 - 1

进阶：

• 你能不使用循环或者递归来完成本题吗？

思路分析

这题其实很简单，不管递归与否

递归就是常规想法，一直除3，如果除得只剩下1，那么就是3的幂次，如果还剩点别的就不是。

非递归也是常规想法，幂次有一个特性，就是它的因子包含比它更小（或者相等）的3的所有幂次。所以我们只需要选出来一个可能出现的最大的3的幂次N（在32位整数条件下为1162261467），判断给入的数字是否是N的因子，如果是，那么一定是3的幂次。

Rust代码

#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn is_power_of_three(n: i32) -> bool {
        if n % 3 == 0 && n != 0 {
            Self::is_power_of_three(n / 3)
        } else {
            n == 1
        }
    }
}
}

C++代码

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}