PowerOfThree [source code]

public class PowerOfThree {
static

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

    public static void main(String[] args) {
        PowerOfThree.Solution tester = new PowerOfThree.Solution();
    }
}

这个题目分别尝试了 bit(找不到什么方法), DP(无法避免使用 loop/recursion), pattern(找不到规律), 最后都没有想到用什么方法. 最后直接看的 editorial 的答案;

Approach #1 Loop Iteration [Accepted]  

public class Solution {  
    public boolean isPowerOfThree(int n) {  
        if (n < 1) {  
            return false;  
        }  

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

        return n == 1;  
    }  
}

这个还是很简单的

Approach #2 Base Conversion [Accepted]  

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

这个是从其他的比如10或者2的 base 的情形得到的类比:

All we need to do is convert the number to base 3 and check if it is written as a leading 1 followed by all 0.
We will use the regular expression above for checking if the string starts with 1 ^1, is followed by zero or more 0s 0* and contains nothing else $.

这个做法有点脏, 不过估计应该不是通用解, 毕竟这个依赖了一个 JAVA 的 API;

Approach #3 Mathematics [Accepted]  

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

这个算法按理应该是可以想到的, 其实就是 check whether log_3{n} is an integer. 转化成为 check 整除的问题;
注意这里 check 整数的做法, 用 mod1来做. double % 1就可以检查这个 double 是不是整数.

想法很好, 不过这个算法涉及到 double 的计算, 有陷阱:

Common pitfalls

This solution is problematic because we start using doubles, which means we are subject to precision errors. This means, we should never use == when comparing doubles. That is because the result of Math.log10(n) / Math.log10(3) could be 5.0000001 or 4.9999999. This effect can be observed by using the function Math.log() instead of Math.log10().

In order to fix that, we need to compare the result against an epsilon.

return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;

不太理解这里为什么要多给一个2;
另外, 这个是 discussion 里面一个类似的解:

public boolean isPowerOfThree(int n) {  
  double a = Math.log(n) / Math.log(3);  
  return Math.abs(a - Math.rint(a)) <= 0.00000000000001;  
}

这个解其实也是一样的问题, 这里自己 inline 了一个 epsilon, 但是实际上这个值还是可以被 break. break 的方法就是找很大的值作为 n, 比如这里的是3^999就 break 了; 至于为什么是这样我也不知道.

Approach #4 Integer Limitations [Accepted]  

public class Solution {  
    public boolean isPowerOfThree(int n) {  
        return n > 0 && 1162261467 % n == 0;  
    }  
}

这个方法我当时几乎都有点想到了, 因为我们这里计算的是一个指数, int 有大小限制, 所以在32位内的power of 3其实并没有那么多.
An important piece of information can be deduced from the function signature

public boolean isPowerOfThree(int n)

In particular, n is of type int. In Java, this means it is a 4 byte, signed integer.

事实上, 就算是穷举, 也不多, 32位里面能够达到的最大的(正的)power of 3就是3^19. 难怪这个问题被 downvote 这么多, 是有点蠢.
如果想要穷举的话, 比较好的办法是把这19个数作为一个 array 的 index. 虽然这样占用了大量空间, 但是速度比放到一个类似 set 的东西里面搜索要快很多. 而且原理上说, 这个 space 大归大, 也可以说成是 constant 的;

速度就不纠结了, 最后4的方法是最优解;

Problem Description

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?

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:40.01%
Contributor: LeetCode
Companies
google
Related Topics
math
Similar Questions
Power of Two Power of Four