題目

給你一個整數 n ，如果你可以將 n 表示成若干個不同的三的冪之和，請你返回 true ，否則請返回 false 。

對於一個整數 y ，如果存在整數 x 滿足 y == 3x ，我們稱這個整數 y 是三的冪。

示例 1：輸入：n = 12 輸出：true

解釋：12 = 31 + 32

示例 2：輸入：n = 91 輸出：true

解釋：91 = 30 + 32 + 34

示例 3：輸入：n = 21 輸出：false

提示：1 <= n <= 107

1、遍歷；時間複雜度O(1)，空間複雜度O(1)

func checkPowersOfThree(n int) bool {	arr := make([]int, 0)	arr = append(arr, 1)	sum := 1	for i := 0; i < 15; i++ {		sum = sum * 3		arr = append(arr, sum)	}	for i := len(arr) - 1; i >= 0; i-- {		if n > arr[i] {			n = n - arr[i]		} else if n == arr[i] {			return true		}	}	return false}

2、遍歷；時間複雜度O(1)，空間複雜度O(1)

func checkPowersOfThree(n int) bool {	for n > 0 {		if n%3 == 2 { // 轉換為3進位制，n*3^x，其中n為0或者1，不會為2			return false		}		n = n / 3	}	return true}

Medium題目，注意每一個3^n只使用1次，遍歷即可