LeetCode OJ: 326. Power of Three 三次方判斷

若您覺得文章寫得不錯，請點選網誌上的廣告，來支持小編，謝謝。

題目連結 https://leetcode.com/problems/power-of-three/。題目需要判斷一個整數是不是 3 的某次方，例如：
1 是 3 的 0 次方；
3 是 3 的 1 次方；
9 是 3 的 2 次方；
27 是 3 的 3 次方；
0 不是 3 的 某次方；
12 不是 3 的 某次方；
24 不是 3 的 某次方；

此題 LeetCode 提供了四種解法：Loop Iteration、Base Conversion、Mathematics、Integer Limitations。

方法一： Loop Iteration
一個整數是 3 的某次方時(3^x)，可以寫成如下表示方式：
n = 3 ^ x
n = 3 * 3 * 3 * 3 ... * 3
也就是將 n 除以 3 做 x 次後，會得到整數 1 。於是可以用迴圈一直除以 3，直到餘數不是零。最後在判斷有沒有得到整數 1。

C++ 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n < 1)   return false;
        
        while(n % 3 == 0)   n /= 3;
        
        return n == 1;
    }
};

方法二： Base Conversion
十進制時，10 ^ 0 = 1；10 ^ 1 = 10；10 ^ 2 = 100 ... etc。只要是 10 ^ x 次方時，一定會是以 1 開頭，接著連續 0 的形式出現： 1 ... 0 。

那二進制時呢？ 2 ^ 0 = 1； 2 ^ 1 = 10；2 ^ 2 = 100 ... etc。也是 1 ... 0 形式。所以可以將數字 n 轉換成 三進制 的字串，在檢查數字 1 是否只有出現一次。

C++ 程式碼：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    bool isPowerOfThree(int n) {
        string s = "";
        char c;

        // convert n into base 3 as string
        while(n / 3 > 0)
        {
            c = (n%3) + '0';
            s.append(string(1, c));
            n = n / 3;
        }

        // the last digit
        c = n + '0';
        s.append(string(1, c));
        
        // Check checking if the string contains only one 1.
        int cnt = 0;
        for(int i = s.length() - 1; i >= 0; i--)
        {
            if(s[i] == '2')
            {
                cnt += 2;
                break;
            }
            else if(s[i] == '1')
            {
                cnt++;
                if(cnt > 1)
                {
                    break;
                }
            }
        }

        return cnt == 1;
    }
};


方法三： Mathematics
若 n 為 3 的 x 次方，那麼以 3 為底，對 n 取對數會得到整數的結果。而C++ math 所提供的對數函數沒有以 3 為底。但可以使用換底公式(下圖取自Wikipedia)：
\log_\alpha\!x=\frac{\log_\beta\!x}{\log_\beta\!\alpha}
以十為底來計算。接著使用 floor() 函數來判斷計算結果是不是一個整數。

C++程式碼：
1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfThree(int n) {
        double r = (log10(n) / log10(3));
        int fr = floor(r);
        return fr == r;
    }
};

方法四： Integer Limitations
在程式語言中，整數會有最大值的限制，C++ 中可以使用 INT_MAX 來查詢到最大值為 2147483647。那麼找出小於 INT_MAX 的 3 ^ x 次方之數值，這個數值會是 3 ^ 19 = 1162261467。而其他的 3 ^ x 一定會是 3 ^ 19 的因數，所以就可以用求餘數的方式來判斷了。

C++ 程式碼：
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};


而針對這四種方法，LeetCode在解答部分有做了 Java 程式碼執行速度的比較：

Iterations10^610^710^810^9Maxint
Java Approach 1: (Naive)0.040.070.302.475.26
Java Approach 2: (Strings)0.684.0238.90409.16893.89
Java Approach 3: (Logarithms)0.090.504.5945.5397.50
Java Approach 4: (Fast)0.040.060.080.410.78


可以看出第四種方法是最快的。依上面的解法，讀者可以試著解這題：https://leetcode.com/problems/power-of-four/
Labels: , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)