[LeetCode] 326. Power of Three* 解題思路 (Easy)

這題要算出是不是 3 的冪(次方)。

LeetCode 題目連結

 

https://leetcode.com/problems/power-of-three/

 

題目

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

Example 1:

Input: 27
Output: true

Example 2:

Input: 0
Output: false

Example 3:

Input: 9
Output: true

Example 4:

Input: 45
Output: false

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

Accept 作法

這題注意最後說不要迴圈或是遞迴，不過我還是迴圈了意外 Accept。時間複雜度為 O(log3n)。


Runtime: 11 ms
Memory: 39 MB

Java 程式碼

class Solution {
    public boolean isPowerOfThree(int n) {
       
        int lastNum = n;
        boolean isPower = true;
        
        if(n <= 0){
            return false;
        }
        
        for(int i = 0;i<n;i++){
            if(lastNum == 1){
                break;
            }
            int num = lastNum % 3;
            
            if(num != 0){
                isPower = false;
                break;
            }
            
            lastNum = lastNum / 3;
        }
        return isPower;
    }
}

然後再去看看答案共有三種解法，第一個是迴圈解，第二個是轉成二進制判斷，第三個是用數學來算。

第二種解法 - 三進制判斷

三進制的轉換會讓 3 轉成 10 、 9 轉成 100、27 轉成 1000， 45雖然是 3 的倍數，但不是次方，轉換成三進制會變成 1200 ，利用這個特性，去判斷三進制時只能存在開頭是 1 ，後面則有不限制出現次數的 0，除了這個以外則都不是 3 次方。
可以利用進制轉換計算機去查規律。

正規表示：^1代表開頭是 1 ， 0* 則表示有不限次數的 0，$ 就是除此之外的都是 false。

Java 程式碼

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

第三種解法 - 利用數學計算

搬出久違的 log ，直接反推回去，必須是整數。

Java 程式碼

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

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題