0326. Power of Three ==================== 题目信息 -------- :题号: 0326 :难度: Easy :主题: 整数、幂、指数、正数边界 :原题: `LeetCode 0326 `_ :重点: 指数必须是整数、``3^0`` 等于 1、零和负数都不是三的幂 题目重述 -------- 给定 32 位有符号整数 ``n``,判断是否存在整数 ``x`` 使 ``n = 3^x``。由于结果需要是整数且三的整数次幂为正数,只有正整数可能满足条件。 ``n`` 位于 ``[-2^31, 2^31-1]``。指数 ``x`` 可以为 ``0``,所以 ``1 = 3^0`` 应返回 ``true``;``0``、负数以及含有其他质因子的正整数都应返回 ``false``。进阶问题询问能否不使用循环或递归完成判断。 自建示例 -------- 较高次幂: .. code-block:: text 输入:n = 81 输出:true 解释:81 = 3^4,因此存在整数指数满足条件。 零不是三的幂: .. code-block:: text 输入:n = 0 输出:false 解释:任意整数指数下的 3 的幂都不会等于 0。 指数为零: .. code-block:: text 输入:n = 1 输出:true 解释:1 = 3^0。 反复除以 3 验证质因子 ---------------------- 正数 ``n`` 若是 3 的幂,连续除以 3 后一定恰好得到 1;过程中只要出现不能整除 3 的余数,就说明还含有其他质因子,不能再成为三的幂。先排除非正数,``n == 1`` 会自然地在循环前通过。 这里不使用对数判断,因为浮点对数在整数幂附近可能有舍入误差;除法循环直接操作整数,也清楚地覆盖 ``3^0`` 的边界。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool isPowerOfThree(int n) { if (n <= 0) return false; while (n % 3 == 0) n /= 3; return n == 1; } }; 代码分析 -------- 每次循环都去掉一个 3 因子;如果原数是 ``3^x``,最终只剩 1,如果不是,剩余数会大于 1。循环次数为 ``O(log_3 n)``,额外空间为 ``O(1)``。这没有采用题目进阶中“不使用循环”的常数技巧,但避免了把一个未解释的最大幂常量当作结论。