8-50.Pow(x,n)

• 2021 年 4 月 21 日
• 筆記
• leetcode, 二分查找

题目描述：

解题思路：

第一想法是递归，结果f(x,n) = x * f(x,n-1);这种方法的空间复杂度太高了，太想当然。

看了下题解：采取分治的方法：f(x,n) = f(x,n/2) * f(x,n/2)；这里只需要注意一下n的奇偶性就可以，如果是偶数，就是这个式子，如果是奇数，需要额外多乘一个x；这样空间复杂度就从O(N)转成了O(logN)；

主要是分治和递归

代码：

class Solution {
    public double myPow(double x, int n) {
        long N = n;//当n是-intMIN的时候，转换成正数会溢出、常用的办法是转成long类型的数据
        //处理一些特殊情形
        if(x == 0){
            return 0;
        }
        if(N == 0){
            return 1;
        }
        if(N > 0){
            return powHelper(x,N);
        }else{
            return 1.0/powHelper(x,-N);
        }
    }
    public double powHelper(double x,long N){
        if(N == 1){//定义该函数出口
            return x;
        }
        //分解成奇数和偶数两个子问题，然后进行递归
        if(N % 2 == 0){//当n为偶数
            double half = powHelper(x,N/2);
            return half * half;
        }else{//n为奇数
            double half = powHelper(x,N/2);
            return half * half * x;
        }
    }
}