Table of contents
題目介紹
題目：檢查數字是否為 3 的冪的和
描述： 給定一個整數 n，判斷它是否可以表示為 3 的不同冪的和。如果可以，則返回 true；否則，返回 false。
換句話說，你需要檢查 n 是否可以寫成 3^0 + 3^1 + 3^2 + … + 3^k 的形式，其中每個 3 的冪最多使用一次。
例如：
-
輸入：n = 12
-
12 = 3^1 + 3^2 = 3 + 9
-
輸出：true
-
輸入：n = 91
-
91 = 3^0 + 3^3 + 3^4 = 1 + 27 + 81
-
輸出：true
-
輸入：n = 21
-
21 無法表示為 3 的不同冪的和
-
輸出：false
解題思路
-
理解 3 的冪
- 3 的冪指的是 3 的 0 次方、1 次方、2 次方等等：1, 3, 9, 27, 81, …
-
轉換為三進制
- 任何數字都可以轉換為不同的進制表示
- 如果 n 可以表示為 3 的冪的和，那麼它的三進制表示中，每一位只能是 0 或 1
- 例如：
- 12 = (110)_3 = 1 * 3^2 + 1 * 3^1 + 0 * 3^0 = 9 + 3 + 0
- 91 = (10101)_3 = 1 * 3^4 + 0 * 3^3 + 1 * 3^2 + 0 * 3^1 + 1 * 3^0 = 81 + 0 + 9 + 0 + 1
- 如果三進制表示中出現了 2，則表示該數字不能表示為 3 的不同冪的和
- 21 = (210)_3 = 2 * 3^2 + 1 * 3^1 + 0 * 3^0 = 18 + 3 + 0 // 有 2，所以不行
-
解題策略
- 將 n 轉換為三進制
- 檢查三進制表示中是否包含 2
- 如果包含 2，返回 false
- 否則，返回 true
-
舉例說明
-
n = 45
-
轉換為三進制：45 = (1200)_3
-
因為三進制表示中有 2，所以 45 不能表示為 3 的不同冪的和
-
n = 243
-
轉換為三進制：243 = (100000)_3
-
因為三進制表示中沒有 2，所以 243 可以表示為 3 的不同冪的和 (243 = 3^5)
-
代碼實現
class Solution:
def checkIfSumOfPowersOfThree(self, n: int) -> bool:
while n > 0:
if n % 3 == 2:
return False
n //= 3
return True複雜度分析
-
時間複雜度：O(log3(n))
- 迴圈的次數取決於 n 可以被 3 除多少次，這相當於以 3 為底的對數
- 因此時間複雜度為 O(log3(n))
-
空間複雜度：O(1)
- 我們只使用了常數級別的額外空間，不隨輸入 n 的大小變化
常見問題與解答
-
Q: 為什麼要轉換成三進制？ A: 因為如果一個數可以表示為 3 的冪的和，那麼它的三進制表示中，每一位只能是 0 或 1。如果出現了 2，就表示不能表示為相異 3 的冪的和。
-
Q: 為什麼時間複雜度是 O(log3(n))？ A: 因為每次迴圈我們都將 n 除以 3，所以迴圈的次數相當於以 3 為底的 n 的對數。
總結
這題「檢查數字是否為 3 的冪的和」展示了如何利用進制轉換的特性來解決問題。解題的關鍵在於：
- 理解 3 的冪的特性
- 將數字轉換為三進制
- 檢查三進制表示中是否包含 2
這種解題思路不僅高效，而且適用於許多類似的進制轉換問題，是算法競賽和面試中的重要技巧。下次遇到類似的題目，可以試著想想：我是不是可以利用進制轉換來簡化問題呢？