給定一個整數(shù)，寫一個函數(shù)來判斷它是否是 3 的冪次方。

示例 1:

輸入: 27
輸出: true
示例 2:

輸入: 0
輸出: false
示例 3:

輸入: 9
輸出: true
示例 4:

輸入: 45
輸出: false

方法一：

用最常規(guī)的方法，直接用除余來判斷

• 如果余數(shù)為零就直接除3，一直循環(huán)到n為3為止
• n == 1是因為一開始傳過來的n就是1，3的0次方等于1，所以1也是對的

復雜度

• 時間復雜度：O(log3n)，除數(shù)是用對數(shù)表示的。
• 空間復雜度：O(1)，沒有使用額外的空間。

func isPowerOfThree(n int) bool {
 if n == 0 {return false}
    for {
        if n==1 || n==3 {
            return true
        }
        if n % 3 == 0 {
            n = n / 3
        } else {
            return false
        }
        
    }


        // return n > 0 && 1162261467 % n == 0;

        if n < 1 {
        return false
    }
    s := strconv.FormatInt(int64(n), 3)
    return s[0:1] == "1" && strings.Count(s, "0") == len(s)-1

   
}

進階：
你能不使用循環(huán)或者遞歸來完成本題嗎？

方法二：

利用3進制來判斷

• 將n轉(zhuǎn)化為3進制數(shù)的字符串，只要只有第一個數(shù)字為1，其他都為0，說明這個數(shù)是3的冪次方

復雜度

• 時間復雜度：O(log3n)。
  假設：
  strconv.FormatInt() - 轉(zhuǎn)換為3進制數(shù)，和方法一類似，都是求余。復雜性應該類似于方法一：O(log3n)的復雜性。
  regexp.MatchString - 方法迭代整個字符串。n 以 3 為基數(shù)表示的位數(shù)是O(log3n)。
• 空間復雜度：O(log3n)。我們使用兩個附加變量。
  以 3 為基數(shù)表示數(shù)字的字符串（大小為log3n） 正則表達式的字符串（常量大?。?/li>

func isPowerOfThree(n int) bool {
    if n < 1 {
        return false
    }
    s := strconv.FormatInt(int64(n), 3)
    //正則表達式,檢查字符串是否以1 ^1 開頭，后跟 0 或 多個 0* 并且不包含任何其他值 $。
    a,_ := regexp.MatchString("^10*$",s)
    return a
}

執(zhí)行用時：108 ms, 在所有 Go 提交中擊敗了8.55%的用戶
內(nèi)存消耗：6.9 MB, 在所有 Go 提交中擊敗了11.48%的用戶

能看到其實上面的效率會有點慢，我們可以優(yōu)化一下

func isPowerOfThree(n int) bool {
    if n < 1 {
        return false
    }
    s := strconv.FormatInt(int64(n), 3)
    //直接用字符串來判斷，開頭為一，其他都為0
    return s[0:1] == "1" && strings.Count(s, "0") == len(s)-1
}

執(zhí)行用時：28 ms, 在所有 Go 提交中擊敗了75.09%的用戶
內(nèi)存消耗：6 MB, 在所有 Go 提交中擊敗了100.00%的用戶

還有一種適用于該題的數(shù)學解法，在int范圍內(nèi)的3的冪只有19個，分別是

1, 3, 9, 45, 99, 111, 153, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721,
129140163, 387420489, 1162261467

最大的第19個為1162261467
因為 3 是質(zhì)數(shù)，所以 3^19 的除數(shù)只有 3^3,31, …3 ^19，因此我們只需要將 3^19 除以 n。若余數(shù)為 0 意味著 n 是 3^19的除數(shù)，因此是 3 的冪。

復雜度

• 時間復雜度：O(1)。
• 空間復雜度：O(1)。

func isPowerOfThree(n int) bool {
  return n > 0 && 1162261467 % n == 0;
}

執(zhí)行用時：24 ms, 在所有 Go 提交中擊敗了84.39%的用戶
內(nèi)存消耗：6.1 MB, 在所有 Go 提交中擊敗了29.51%的用戶