326. 3的幂

Posted on | In
Words count in article: 413 | Reading time ≈ 1

题目

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

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

示例1：

1
2
输入: 27
输出: true

示例2：

1
2
输入: 0
输出: false

示例3：

1
2
输入: 9
输出: true

示例4：

1
2
输入: 45
输出: false

提示：

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

进阶

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

解法

解法一：

递归

Java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isPowerOfThree(int n) {
        if (n == 0) {
        	return false;
        } else if (n == 1) {
        	return true;
        } else if (n % 3 == 0) {
        	return isPowerOfThree(n / 3);
        }
        return false;
    }
}

解法二：

循环

Java

1
2
3
4
5
6
7
8
9
10
public boolean isPowerOfThree(int n) {
		if (n < 1) {
            return false;
        }

        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
	}

解法三：

数学方法

数学公式

Java

1
2
3
public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }

解法四：

使用库函数，转换成3进制的数的字符串，然后判断字符串是否只包含一个1.

Java

1
2
3
public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }

解法五：

整数限制

我们现在可以推断出 n 的最大值，也就是 3 的幂，是 1162261467。因此，我们应该返回 true 的 n 的可能值是 3，9…3 的19次方。因为 3 是质数，所以 3的19次方 的除数只有 3，9，27，3的19次方，因此我们只需要将 3的19次方 除以 n。若余数为 0 意味着 n 是 3的19次方 的除数，因此是 3 的幂。

Java

1
2
3
4
5
public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}
0%