LeetCode解题报告（358) -- 326. Power of Three

Problem

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

Example 2:

Input: n = 0
Output: false

Example 3:

Input: n = 9
Output: true

Example 4:

Input: n = 45
Output: false

Constraints:

• -231 <= n <= 231 - 1

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

---

Analysis

  题目给出一个数字n，要判断这个数是否3的x次方。最无脑的方法就是写个循环，不断除以3，最后如果剩下1的话就说明这个数是3的x次方。但这里我们要看看能否在不用递归或者循环的前提下，快速判断出结果。

  在数学中，解决次方很常见的做法是使用对数，因为对数有个换底公式$\log a^b=\frac{\log {10}^b}{\log {10}^a}$，这里我用了10作为底数（实际上换成什么底数都是成立的）。所以如果题目给出的n满足$n=3^x$，则会有$\log 3^n=\log 3^{3^x}=x$为整数，于是题目转化为判断$\log 3^n$是否为整数。

  使用换底公式，$log{3}^n=\frac{\log {10}^n}{\log {10}^3}$，运算出来之后，判断是否整数即可。注意这里使用10为底的原因是，C++存在精度问题，如果使用自然数或2为底，将得不到正确的答案。

---

Solution

  无

---

Code

class Solution {
public:
    bool isPowerOfThree(int n) {
        return (n > 0 && int(log10(n) / log10(3)) - (log10(n) / log10(3)) == 0);
    }
};

---

Summary

  这道题目更偏向于数学知识，主要是使用对数的性质处理次方问题。同时也涉及到了C++计算过程中，判断整数、精度等问题，非常值得总结。这道题目的分享到这里，感谢你的支持！