导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 循环
    2. 递归
    3. 不用循环和递归
      1. 方法一
      2. 方法二

LeetCode-326.Power of Three

题目

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

翻译

给出一个整数,编写函数确定它是否是3的幂。
追加:
你是否可以不用循环或递归?

循环

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

递归

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

不用循环和递归

方法一

取得3的最大幂,然后判断n是否是其因子:

1
2
3
4
5
6
7
public class Solution {
public boolean isPowerOfThree(int n) {
// 0x7fffffff为最大的long int的最大值
// (int)(Math.log(0x7fffffff) / Math.log(3))为3的最大幂
return n > 0 && Math.pow(3, (int)(Math.log(0x7fffffff) / Math.log(3))) % n == 0;
}
}

或:
由于输入是int,正数范围是0-2^31,在此范围中允许的最大的3的次方数为3^19=1162261467,那么我们只要看这个数能否被n整除即可

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

方法二

如果log10(n) / log10(3)返回整数,则n是3的幂。

1
2
3
4
5
6
public class Solution {
public boolean isPowerOfThree(int n) {
double res = Math.log(n) / Math.log(3);
return Math.abs(res - Math.round(res)) < epsilon;
}
}

参考:
http://www.cnblogs.com/EdwardLiu/p/5115390.html
http://blog.csdn.net/cwj649956781/article/details/8589981
http://98sky.com/info/52594.html
http://blog.csdn.net/u010025211/article/details/50484747