LeetCode算法題-Power Of Three（Java實作-七種解法）

這是悅樂書的第204次更新，第215篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第71題（順位題号是326）。給定一個整數，寫一個函數來确定它是否為3的幂。例如：

輸入：27

輸出：true

輸入：0

輸出：false

輸入：9

輸入：45

跟進：你可以不使用任何循環/遞歸嗎？

本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。

02 第一種解法

建立一個變量，隻要其小于n，依次乘上3，最後比較兩數是否相等。當然，你也可以做除法。

public boolean isPowerOfThree(int n) {
    long m = 1;
    while (m < n) {
        m *= 3;
    }
    return  m == n;
}
           

03 第二種解法

使用遞歸的方法。當n等于0的時候，傳回false，當n等于1的時候，傳回true。當n大于1的時候，先判斷其對3取餘是否等于 0，如果等于0，則将n除以3再調用自己。最後傳回false。

public boolean isPowerOfThree2(int n) {
    if (n == 0) {
        return false;
    }
    if (n == 1) {
        return true;
    }
    if (n > 1) {
        return n%3 == 0 && isPowerOfThree2(n/3);
    }
    return false;
}
           

04 第三種解法

将第二種解法的遞歸換成疊代的方式也可以。

public boolean isPowerOfThree3(int n) {
    if (n == 0) {
        return false;
    }
    if (n == 1) {
        return true;
    }
    while (n%3 == 0) {
        n /= 3;
    }
    return n == 1;
}
           

05 第四種解法

利用取餘。一般的思路是對3取餘，但是這隻能判斷n是否是3的倍數，而不能保證是3的幂次方。但是我們可以反過來對n取餘，借助1162261467這個整數，因為它是3的19次方，是int類型範圍内3能夠取到的最大幂次方數。隻要n是3的幂次方，1162261467對n取餘都會傳回0。

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

06 第五種解法

利用數學中的對數算法。以下是推理步驟：

3^X == N

log (3^X) == log N

X log 3 == log N

X == (log N) / (log 3)

如果n是3的幂次方，那麼将兩數取對數後再做除法，得到的是一個以幂次方為整數位，以0位小數位的double類型數，那麼對其取整再和自身做減法，那麼它的絕對值肯定是無限接近于0的。

public boolean isPowerOfThree5(int n) {
    double lg = Math.log(n)/Math.log(3);
    return Math.abs(lg-Math.round(lg)) <= 0.00000000000001;
}
           

07 第六種解法

借助包裝類Integer的toString方法。

Integer.toString(int par1, int par2)，par1表示要轉成字元串的數字，par2表示要轉成的進制表示。我們可以将n轉成3進制的數，那麼隻要是3的幂次方，轉換成3進制字元串後，就是一個以1開頭尾随k個0的字元串。

public boolean isPowerOfThree6(int n) {
    if (n <= 1) {
        return n == 1;
    }
    return Integer.toString(n, 3).matches("10*");
}
           

08 第七種解法

将int類型範圍内所有3的幂次方整數放入一個HashSet中，然後判斷n是否在HashSet中。

public boolean isPowerOfThree7(int n) {
    HashSet<Integer> set = new HashSet<>(Arrays.asList(1, 3, 9, 27, 
            81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441,
            1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467));
    return set.contains(n);
}
           

09 小結

算法專題目前已連續日更超過兩個月，算法題文章71+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！