0326. Power of Three - kumaeki/LeetCode GitHub Wiki

326. Power of Three

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 == 3x.

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

解法1

就是循环的除以3 直到最后得到结果

class Solution {
    public boolean isPowerOfThree(int n) {

        if(n == 1)
            return true;
        
        if(n < 1)
            return false;

        while(n > 3){
            if(n % 3 != 0)
                return false;
            n = n / 3;
        }

        return n == 3;
    }
}

更优美的写法

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

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

        return n == 1;
    }
}

解法2

或者提前把int范围内的所有可能的值求出来,然后直接看是否相等

class Solution {
    
    static Set<Integer> set;
    
    static{
        set = new HashSet<Integer>();
        int n = 1;
        while(n > 0){
            set.add(n);
            n *= 3;
        }
    }
    
    public boolean isPowerOfThree(int n) {
        return set.contains(n);
    }
}

解法3

这个是leecode的答案的内容.绝了.

对于10进制来说, 10的幂的形式一定是前面一个1,后面跟若干个0. 比如10, 100, 1000.
对于2 进制来说, 2 的幂的形式一定是前面一个1,后面跟若干个0. 比如10(十进制的2), 100(十进制4), 1000(十进制的8).
其实对于任意进制来说都是这样.(我不知道怎么证明, 也不想知道数学意义上的证明过程)

所以,可以把数字转换为3进制,看是否满足前面一个1,后面若干个0的形式.

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