50. Pow(x, n) 快速幂【每日一题】

快速幂【每日一题】"/>

50. Pow(x, n) 快速幂【每日一题】

50. Pow(x, n)

思路

          快速幂的实现，思路很简单，类比了二进制数转十进制的法子，比如 1001 = 1 * 2³+0 * 2²+0 * 2¹+1 * 2⁰。那么xⁿ，你假设 n=5 ，n = 101是吧，

x^5 = *x^(4*1) * x^(2*0) * x^(1*1)

那不就是把 n 对应 1 的位置相乘嘛，因为任何数的0次方都是1，所以0的位置可以不用管，而且，基数是从

x^1--------->x^2-------------->x^4------------>x^8-------->

每次翻倍

代码

class Solution:def myPow(self, x: float, n: int) -> float:flag = n<0n = abs(n)  # 这个都是为了判断负数次方  res = 1while n:    # 这才是快速幂的过程 if n&1: # n 的二进制当前位是 1， 是0就乘0次方，乘1 就当没乘 所以省略了res *= x    # 那就乘当前的基x *= x          # 每次基都翻倍n >>= 1         # 右移一位，其实就是判断前一位if flag:return 1.0/resreturn res

有时候题目要求说要模 10⁹+7

class Solution:def myPow(self, x: float, n: int) -> float:mod = 10**9+7flag = n<0n = abs(n)  # 这个都是为了判断负数次方  res = 1while n:    # 这才是快速幂的过程 if n&1: # n 的二进制当前位是 1， 是0就乘0次方，乘1 就当没乘 所以省略了res *= res * x % mod   # 那就乘当前的基x = x * x % mod            # 每次基都翻倍n >>= 1                    # 右移一位，其实就是判断前一位if flag:return 1.0/resreturn res