326. 3 的幂(简单)
方法一:试除法
思路
- 我们可以先进行特殊点判断,
n <= 0
的数都不可能是 3 的幂次方。 - 接着,当
n > 0
且n 能被 3 整除
时,我们对其整除 3 ,直到该条件不满足,我们就判断此时的 n, 如果n == 1
,即 30 ,说明原本的 n 是 3的幂次方。
代码
class Solution {
public:bool isPowerOfThree(int n) {if(n < 0) return false;while(n > 0 && n%3 == 0){// 能被3整除n /= 3;}return n == 1;}
};
方法二:倍数 & 约数
题目要求不能使用循环和递归,而传参 n 的数据类型为 int,这引导我们首先分析出 int 范围内的最大 3 次幂是多少,约为 319=11622614673 。
如果 n 为 3 的幂的话,那么必然满足 n∗3k=1162261467,即 n 与 1162261467 存在倍数关系。
因此,我们只需要判断 n 是否为 1162261467 的约数即可。
class Solution {
public:bool isPowerOfThree(int n) {return n > 0 && 1162261467 % n == 0;}
};
收获
-
这道题理解起来很简单,但是一开始我陷入了一个误区,以为 -27 之类的数也是 3 的幂次方,导致算不出来。
-
此外,投机取巧的方法二也需要掌握。
参考资料
宫水三叶:一题三解