50. Pow(x, n)

https://leetcode.com/problems/powx-n/description/

solution

• 快速幂: recursive

  • n为奇数，x^n = x(x^2)^(n//2)

  • n为偶数，x^n = (x^2)^(n//2)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:  # 退出递归的关键返回
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2 == 1:
            return x * self.myPow(x, n - 1)
        return self.myPow(x * x, n // 2)  # 注意是 (x ** 2 ^ n//2) 而不是 (x ^ n//2 ^ 2)

时间复杂度：O(log(n)) 空间复杂度：O(1)

• 非递归: iterative

# https://algo.monster/liteproblems/50

follow up

372. Super Pow

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        mode = 1337
        ans = 1

        for i in b:
            ans = pow(ans, 10, mode) * pow(a, i, mode)
        return ans % mode

时间复杂度：O(n) 空间复杂度：O(1)