TNotes.leetcode

Appearance

0326. 3 的幂【简单】

0326. 3 的幂【简单】 ​

1. 📝 题目描述 ​

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

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

示例 1：

txt
输入：n = 27
输出：true

示例 2：

txt
输入：n = 0
输出：false

示例 3：

txt
输入：n = 9
输出：true

示例 4：

txt
输入：n = 45
输出：false

提示：

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

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

2. 🎯 s.1 - 循环除法 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
  // 3 的幂必须是正整数
  if (n <= 0) return false

  // 不断除以 3，直到不能整除为止
  while (n % 3 === 0) {
    n /= 3
  }

  // 如果最后结果是 1，说明原来是 3 的幂
  return n === 1
}
  • 时间复杂度：O(log3⁡n)
  • 空间复杂度：O(1)

3. 🎯 s.2 - 递归法 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
  // 3 的幂必须是正整数
  if (n <= 0) return false

  // 1 是 3 的幂 (3^0)
  if (n === 1) return true

  // 不能被 3 整除，不是 3 的幂
  if (n % 3 !== 0) return false

  // 递归检查
  return isPowerOfThree(n / 3)
}
  • 时间复杂度：O(log3⁡n)
  • 空间复杂度：O(log3⁡n)，递归调用栈

4. 🎯 s.3 - 最大幂取余法 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
  // 3 的幂必须是正整数
  if (n <= 0) return false

  // 在 32 位整数范围内，最大的 3 的幂是 3^19 = 1162261467
  // 如果 n 是 3 的幂，那么 1162261467 能被 n 整除
  return 1162261467 % n === 0
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)
  • 对于 2、3、5、7、11、13……只要是质数，都可以用这个方法！

5. 🎯 s.4 - 对数 - 换底公式法 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function (n) {
  // 3 的幂必须是正整数
  if (n <= 0) return false

  // 使用换底公式：log3(n) = log10(n) / log10(3)
  // 如果结果是整数，则 n 是 3 的幂
  const logResult = Math.log10(n) / Math.log10(3)
  return Number.isInteger(logResult)
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

Discussions