[数据结构与算法]50. Pow(x n)、Leetcode的Go实现

博客主页：🏆看看是李XX还是李歘歘?🏆

🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺

💗点关注不迷路，总有一些📖知识点📖是你想要的💗

??今天的内容是Leetcode?342. 4的幂??💻💻💻

50. 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

内置函数：

func myPow(x float64, n int) float64 {
    return math.Pow(x,float64(n))
}

「快速幂算法」的本质是分治算法：

每次递归都会使得指数减少一半，因此递归的层数为O(logn)

迭代：需要使用快速幂解决超时问题，减少时间复制度

func myPow(x float64, n int) float64 {
    //迭代
    res := 1.0
    if n<0 {
        n=-n
        x=1/x
    }
    for n > 0 {
        if n%2==1 {
            res=res*x
        }
        x=x*x
        n=n/2
    }
    return res
}

递归：需要使用快速幂解决超时问题，减少时间复制度

func myPow(x float64, n int) float64 {
    if n==0 {
        return 1
    }
    if n < 0 {
        return 1/myPow(x,-n)
    }
    if n%2==1 {
        return x*myPow(x,n-1)
    }
    return myPow(x*x,n/2)
}