# **Leetcode筆記(Pow(x, n))**

:::info
:information_source: 題目 : Pow(x, n), 類型 : math , 等級 : medium
日期 : 2023/06/15，2023/08/13，2024/03/27
:::

### 嘗試
2023/08/13
如果想要時間複雜度為log(n)下去解，那就是用樹狀圖法，只遞迴一邊
遇到奇數時再多乘一個base就可以了

class Solution:
    def myPow(self, x: float, n: int) -> float:
        
        def helper(base, power):
            if power == 1:
                return base
            if power == 0:
                return 1

            # res = helper(base, power // 2) * helper(base, power // 2)
            res = helper(base, power // 2)
            res *= res

            if power % 2: # 代表奇數
                res *= base
            
            return res

        return helper(1 / x, - n) if n < 0 else helper(x, n)

binary解法

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = - n
        
        pow2 = 1 # 二的零次方
        res = 1
        while n:
            res *= x ** ((n % 2) * pow2)
            pow2 *= 2
            n = n >> 1
        
        return res

2024/03/27

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1/x
            n = -n

        def cal(x, n):
            if n == 0:
                return 1
            if n == 1:
                return x
            
            half = cal(x, n // 2)
            temp_res = half * half

            if n % 2:
                temp_res *= x
            
            return temp_res
        
        return cal(x, n)

---
### **優化**
一直把次方數分解下去
例如2^ 10，就分成2^ 5和2^ 5下去算，
2^ 5分成2^ 2和2^ 2和2下去算，
2^ 2分成2^ 1和2^ 1下去算，
2^ 1分成2^ 0和2^ 0和2下去算

時間複雜度：這段程式碼的時間複雜度為 O(log n)。遞歸函式 `helper` 的遞迴深度為 log n
空間複雜度：這段程式碼的空間複雜度為 O(log n)。遞迴函式 `helper` 的遞迴深度為 log n，每層遞迴需要 O(1) 的空間，因此整個遞歸過程的空間複雜度為 O(log n)。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        
        def helper(base, power):
            if power == 0:
                return 1
            res = helper(base, power // 2)
            res *= res # 例如2^10 = 2 ^ 5 * 2 ^ 5
            if power % 2: # power是奇數 補乘一次
                res *= base
            return res
        
        # 負數要絕對值(最後直接回傳倒數)
        return helper(x, abs(n)) if n > 0 else 1 / helper(x, abs(n))

也可以用binary的方法思考
x ^ 10 = x ^ 1010 = x ^ 8 * x ^ 2 =
x * (2 ^ 3) * x * (2 ^ 2) * x * (2 ^ 1) * x * (2 ^ 0)
但有點不能理解while那個部分

把整數n取n % 2，就是把interger換成binary的一個過程

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            n = -n
            x = 1 / x
        
        res = 1
        while n: # 當 1010 完全沒有時
            if n % 2: # 換成binary
                res = res * x # 一開始為x * 2 ^ 0次方
            n = n >> 1 # 101
            x = x * x # x * 2 ^ 1次方

        return res

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://blog.csdn.net/fuxuemingzhu/article/details/82960833
https://www.youtube.com/watch?v=g9YQyYi4IQQ
Provided by. 负雪明烛 & Neetcode

###### tags: `math` `medium` `leetcode`