50. Pow(x, n)

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 -2^31 <= n <= 2^31-1 -10^4 <= xn <= 10^4 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/powx-n 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

这道题考察了什么思想？你的思路是什么？

说到求幂函数，我不得不说一下快速幂了，快速幂的递归版本还是比较好理解的，我们先来讲一下快速幂吧，快速幂的本质是分治算法，比如我们要计算x^8：

可以有： x -> x^2 -> x^4-> x^8

我们只需将上一次结果进行平方，进行3次即可得到x^8。

而如果我们想求x^19，可以有：

x -> x^2 -> x^4 -> x^9 -> x^19

因为我们需要从右到左进行推理，所以可以用到递归的思想。

当我们计算x^19时，先计算y = x[n/2]，[a]表示向下取整。如果n为偶数，那么上一个数的平方为xn，如果n为奇数，那么上一个数的平方再乘x为x^n。

做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？

不是一次通过的，边界条件没有处理好，也就是递归出口刚开始没有搞好。

有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？

image-20221208231042122

class Solution {
    public double myPow(double x, int n) {
        double res = 1.0;
        for(int i = n; i != 0; i /= 2){
            if(i % 2 != 0){
                res *= x;
            }
            x *= x;
        }
        return  n < 0 ? 1 / res : res;
    }
} 

三、AC 代码：

func myPow(x float64, n int) float64 {
 if n >= 0 {
     return Mul(x, n)
 }
 return 1.0 / Mul(x, -n)
}

func Mul(x float64, n int) (res float64) {
 if n == 0 {
     return 1
 }
 y := Mul(x, n/2)
 if n%2 == 0 {
      res = y * y
      return
 }
 res =  y * y * x
 return 
}

四、总结：

其实AC代码用到的快速幂方法还有非递归方法，即用迭代方法。那样空间复杂度也能减小到O(1)。