50. Pow(x, n)/面试题16. 数值的整数次方（中等）

实现 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]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n

思路1：

这里思路用分治的思想，如果是n是偶数，计算x*x^(n/2)即可，如果是奇数，我们求n-1的，最后再求x 乘以n-1得到的值，这里使用递归写法会出一些问题，由于n为int，所以会出现下面的错误，所以要进行单独判断

最后执行的输入：1.00000 -2147483648

执行出错信息：Line 8: java.lang.StackOverflowError

代码一中注释部分为原代码，只能通过三百个示例，根据其他人的题解进行修改，代码二为非递归写法

回看记录200525

第二次看到时，递归思想很好理解，但是位运算的还不是很快能一次掌握，需要加强

回看记录200627

添加go代码，分治递归

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public double myPow(double x, int n) {
        //分治-递归
        // if(n==0)
        //     return 1;
        // if(n<0)
        //     return myPow(1/x,-n);
        // if(n%2==1)//奇数
        //     return x*myPow(x,n-1);
        // else
        //     return myPow(x*x,n/2);
        if (n == 0)
            return 1;
        if (n == 1) 
            return x;
        if (n == -1)
            return 1 / x;
        double half = myPow(x, n / 2);
        double rest = myPow(x, n % 2);
        return half * half * rest;
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//借助位运算，这里要好好理解
class Solution {
    public double myPow(double x, int n) {
        //非递归解法
        long n1 =n;
        if(n<0){
            x=1/x;
            // n=-n;
            n1 = -n1;
        }
        double pow = 1;
        while (n1 > 0) {
            if ((n1 & 1) == 1)//相当于if(n%2 ==1)，用来判断奇偶
                pow *= x;
            x *= x;  // 快速幂算法的核心在于不断对x做平方运算
            n1 >>= 1;//n1除以2
        }
        return pow;
    }
}

代码3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func myPow(x float64, n int) float64 {
    if n==0{
        return 1
    }
    if n<0{
        return myPow(1/x,-n)
    }
    if n%2==1{
        return x*myPow(x,n-1)
    }else{
        return myPow(x*x,n/2)
    }
}
如果java这么写有个样例过不去，会超时