326. 3 的幂

🟢   🔖  递归 数学  🔗 力扣 LeetCode

题目

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3^x.

Example 1:

Input: n = 27

Output: true

Explanation: 27 = 3^3

Example 2:

Input: n = 0

Output: false

Explanation: There is no x where 3^x = 0.

Example 3:

Input: n = -1

Output: false

Explanation: There is no x where 3^x = (-1).

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

题目大意

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

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

示例 1：

输入： n = 27

输出： true

示例 2：

输入： n = 0

输出： false

示例 3：

输入： n = 9

输出： true

示例 4：

输入： n = 45

输出： false

提示：

• -2^31 <= n <= 2^31 - 1

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

解题思路

思路一：累除法

1. 如果 n 小于等于 0，直接返回 false，因为负数或零不可能是 3 的幂次方。
2. 对于一个正整数，如果它是 3 的幂次方，那么它应该可以不断被 3 整除，直到结果为 1。
3. 如果 n 不等于 1，并且能被 3 整除，就不断除以 3。
   • 最终若得到 1，说明 n 是 3 的幂次方。
   • 否则不是。

复杂度分析

• 时间复杂度：O(log_3(n))，每次除以 3，直到结果为 1，最多需要对数次操作。
• 空间复杂度：O(1)，只使用常数空间。

---

思路四：模运算与整数溢出

• 使用最大范围内的 3 的幂次方数（如 3^19 = 1162261467，因为 3^20 已超过 32 位整数范围）。
• 如果 n 是 3 的幂次方，则它一定能整除 3^19。

复杂度分析

• 时间复杂度：O(1)，只有一次取模操作。
• 空间复杂度：O(1)。

---

思路三：数学公式法

• 可以利用对数的性质，若 n 是 3 的幂次方，则对 n 取对数（底数为 3）后应该是整数。
• 公式：log_3(n) = log(n) / log(3)
• 如果 log_3(n) 是整数，则 n 是 3 的幂次方。

复杂度分析

• 时间复杂度：O(1)，只需要计算对数和指数操作。
• 空间复杂度：O(1)，只使用常数空间。

代码

累除法

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
	if (n <= 0) return false;
	while (n % 3 === 0) {
		n /= 3;
	}
	return n === 1;
};

预计算法

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
	return n > 0 && 1162261467 % n == 0;
};

数学公式法

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
	return n > 0 && Number.isInteger(Math.log(n) / Math.log(3));
};

相关题目

题号	标题	题解	标签	难度	力扣
231	2 的幂	[✓]	位运算 递归 数学	🟢	🀄️ 🔗
342	4的幂	[✓]	位运算 递归 数学	🟢	🀄️ 🔗
1780	判断一个数字是否可以表示成三的幂的和		数学	🟠	🀄️ 🔗