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)