LeetCode50. Pow(x, n)_leetcode 50. pow(x, n)

题目

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

思路

分治快速幂
当n == 0，返回1。
当n <0，取相反数，递归，结果用1除。
n > 0，递归计算出mid=pow(x,n/2)，由于n/2向下取整，当n为奇数，需要在返回时多乘一个x，否则直接返回mid*mid

class Solution {
	/**这里修改了本来为int的参数，因为对于INT_MIN取相反数还是其本身
	（int类型取反加一求得相反数，对于INT_MIN结算结果还是其本身）*/
    public double myPow(double x, long n) {
        if(n==0){
            return 1;
        }
        if(n<0){
            return 1/myPow(x,-n);
        }
        double mid=myPow(x,n/2);
        return n%2==0?mid*mid:mid*mid*x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14