LeetCode50天刷题计划（Day 27— Pow(x, n)（18.30-19.20）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

新人登场~
快速幂算法，早有耳闻，今日一见
果然名不虚传（bushi 最近电视剧看多了）

一、题目

Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104

二、思路

一上去直接暴力解了（还想这题也配中等？）然后时间超限，
然后用二分法递归（时间复杂度由n变logn）
最后才想起来快速幂（空间复杂度由logn变1）
推导过程如下：

二进制函数bin（）将一个数转为二进制字符串，使用for循环就将字符串中的01直接取出。循环中的重点是这两步的顺序：

注意每次是对每轮积攒的x整体取平方，而不是只乘上底数

三、代码

1.python O(n)【超时】

class Solution:
    def myPow(self, x: float, n: int) -> float:
        n_abs=abs(n) #指数的绝对值
        x_abs=abs(x) #底数的绝对值
        if(x<0 and n_abs%2==1): #计算最终的符号（只有底数为负且指数为奇数才为负）
            result=-1
        else:
            result=1
        for i in range(n_abs): #线性
            result*=x_abs
        if(n<0): #如果n是负的,要用1除一下result
            return 1/result
        else: #否则返回result即可
            return result



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.python O（logn）【过】

class Solution:
    def myPow(self, x: float, n: int) -> float:
        n_abs=abs(n) #指数的绝对值
        x_abs=abs(x) #底数的绝对值
        if(n==0): #任何数的0次方都等于1
            return 1
        if(x<0 and n_abs%2==1): #计算最终的符号（只有底数为负且指数为奇数才为负）
            result=-1
        else:
            result=1

        def dg(x_abs,n): #o(logn)
            if(n==1): #x的1次方还是x
                return x_abs
            if(n%2==0): #n是偶数
                temp=dg(x_abs,n/2)
                return temp*temp
            else: #n是奇数
                temp=dg(x_abs,n//2)
                return temp*temp*x_abs
        result*=dg(x_abs,n_abs)
       
        if(n<0): #如果n是负的,要用1除一下result
            return 1/result
        else: #否则返回result即可
            return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.快速幂（python）

class Solution:
    def myPow(self, x: float, n: int) -> float:
        n_abs=abs(n) #指数的绝对值
        x_abs=abs(x) #底数的绝对值
        if(n==0): #任何数的0次方都等于1
            return 1
        if(x<0 and n_abs%2==1): #计算最终的符号（只有底数为负且指数为奇数才为负）
            result=-1
        else:
            result=1
        #快速幂函数
        def ksm(x_abs,n,result): #o(logn)+o(1)
            n=bin(n)
            x=x_abs
            for i in range(1,len(n)+1):
                if(n[-i]=='1'):
                    result*=x
                x*=x
            return result
        #调用
        result=ksm(x_abs,n_abs,result)
        #返回
        if(n<0): #如果n是负的,要用1除一下result
            return 1/result
        else: #否则返回result即可
            return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26