Leetcode-50. Pow(x, n)

实现 pow(x, n) ,即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

解法:快速幂,利用分治的思想,将N次方转换成更小的问题,分成奇数偶数进行讨论,这样的时间复杂度能够降低到O(logN)。需要注意N同时可能是负数。空间复杂度为O(logN),储存logN的元素half值

  • Java
    注意防止stackoverflow error,深递归导致栈被耗尽,例如1.00000的-2147483648次方,不知道为什么python不会出现这个问题
    函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,相当于一次push压栈操作,每当函数返回,相当于一次pop出栈操作。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。
    解决方案:
    1.把递归调用函数改用while或者for循环来实现。
    2.通过尾递归优化。尾递归是指在函数返回调用自身本身,并且return语句不能包含表达式(既return 函数名(参数))。这种情况下,编译器或者解释器,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。
class Solution {
   
    public double myPow(double x, int n) {
   
        if(n<0){
   
            x = 1/x;
            n = -n;
        }
        return this.helper(x,n);
    }
    private double helper(double x ,int n){
   
        if(n==0) return 1d;
        double half = this.helper(x,n/2);
        if(n%2==0){
   
            return half*half; // 不写成return this.helper(x*x,n/2),会导致栈溢出
        }else{
   
            return x*half*half;
        }
    }
}
  • Python

使用递归

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if not n: return 1
        if n<0: return 1/self.myPow(x,-n)
        if n%2:
            return x*self.myPow(x,n-1)
        return self.myPow(x*x,n/2)