50. Pow(x, n)

快速冪算法的目的，就是快速計算 x 的 n 次方。基本思路是把 n 視作二進制數，則 n 可以被分解為多個 2 的冪次方之和，如 12 對應 1100 等于 $0?2^0+0?2^1+1?2^2+1?2^3$，即二進制數中每一位的0或1對應的正是系數。因此，$x^{12}=x^{0?2^0}+x^{0?2^1}+x^{1?2^2}+x^{1?2^3}$。從 n 的二進制形式可以得到系數，而對應的 x 的二次冪可以通過 x 自乘得到（$x=x^{2^0},x?x=x^{2^1},x^2?x^2=x^{2^2}......$）。實現上可以使用遞歸或者迭代，迭代的空間復雜度更優：

遞歸法：

class Solution:def myPow(self, x: float, n: int) -> float:def quickMul(N: int):if N == 0:return 1.0y = quickMul(N // 2)return y * y if N % 2 == 0 else y * y * xreturn quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

迭代法：

class Solution:def myPow(self, x: float, n: int) -> float:if x == 0.0: return 0.0ans = 1if n < 0: x = 1 / xn = -nwhile n:if n & 1: ans *= xx *= xn >>= 1return ans

372. 超級次方

做這題需要知道的公式是：$$(a?b)\%MOD=((a\%MOD)?(b\%MOD))\%MOD$$

class Solution:# 快速冪算法def quick_mul(self, x: int, n: int) -> int:MOD = 1337ans = 1while n:if n & 1:ans = ans * x % MODx = x * x % MODn >>= 1return ansdef superPow(self, a: int, b: List[int]) -> int:MOD = 1337ans = 1x = a % MODfor y in b[::-1]:ans = ans * self.quick_mul(x, y) % MODx = self.quick_mul(x, 10)return ans

關鍵是兩點：一是根據公式，增加了多次取模操作（MOD）；二是由于指數存儲在了數組中，從右到左遍歷是低位到高位，兩種方法，一是用一個變量記錄當前是第幾位，則從數組取出來的數與 10 的多少次方相乘，二是每次將底數 x 乘以 10 次方，這樣也相當于指數乘以 10，例如 $x^{123}=(x^1{)}^3+(x^{10}{)}^2+(x^{100}{)}^1$。

總結

以上是生活随笔為你收集整理的快速幂算法相关题目（Leetcode题解-Python语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。