题目

题解

这道题在leetcode上用挨个累乘的方法会超时因此需要用快速幂法
快速幂是指x**2n == x**n + x**n，利用这一性质，不断的一半的数进行运算。有递归法和迭代法两种，注意要区分n为奇偶和n为负数的情况。

1. 递归法

  • 时间复杂度$O(log{n})$
  • 空间复杂度$O(log{n})$
class Solution {//两个方法。1.递归
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        double half = myPow(x, n/2);//先把一半的幂算出来，防止反复调用mypow影响效率
        if(n%2 == 0) return half*half;//注意n是偶数的情况包括了为负数的情况，偶数两个负数相乘为正数
        else if(n>0) return half*half*x;//n为正奇数的情况
        else return half*half/x;//n为负奇数的情况
    }
};

2. 迭代法

  • 时间复杂度$O(log{n})$
  • 空间复杂度$O(1)$
class Solution {//两个方法。2. 迭代
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        double res = 1;//初始化res
        for(int i=n; i != 0; i /= 2){//每次取n的一半，用移位操作会报错
            if(i%2 != 0) res *= x;//若遇到奇数，res乘上x
            //注意此时的x不一定是起初的x
            //这里用x进行累乘，也可以定义一个新变量存累乘的值
            x *= x;
        }
        return n>0? res:1/res;//判断n的正负
    }
};