Leetcode326. 3 的幂

Every day a leetcode

题目来源：326. 3 的幂

相似题目：342. 4的幂

解法1：递归

代码：

/** @lc app=leetcode.cn id=326 lang=cpp** [326] 3 的幂*/// @lc code=start
class Solution
{
public:bool isPowerOfThree(int n){if (n <= 0)return false;if (n == 1)return true;if (n % 3 == 0)return isPowerOfThree(n / 3);elsereturn false;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(logn)，当n是3的幂时，需要除以3的次数为log₃n=O(logn)；当n 不是3的幂时，需要除以3的次数小于该值。

空间复杂度：O(logn)，取决于递归栈的具体实现。

解法2：暴力

在题目给定的32位有符号整数的范围内，最小的3的幂为3⁰=1，最大的3的幂为3¹⁹=1162261467。

我们使用数组记录3⁰到3¹⁹，再在这个数组里查找即可。

代码：

/** @lc app=leetcode.cn id=326 lang=cpp** [326] 3 的幂*/// @lc code=start
// class Solution
// {
// public:
//     bool isPowerOfThree(int n)
//     {
//         if (n <= 0)
//             return false;
//         if (n == 1)
//             return true;
//         if (n % 3 == 0)
//             return isPowerOfThree(n / 3);
//         else
//             return false;
//     }
// };class Solution
{
public:bool isPowerOfThree(int n){vector<int> nums;for (int i = 0; i <= 19; i++)nums.push_back(pow(3, i));return count(nums.begin(), nums.end(), n);}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(1)。

空间复杂度：O(1)。