【LeetCode】50. Pow(x, n)

问题描述

https://leetcode.com/problems/powx-n/#/description

Implement pow(x, n).

实现pow(x,n)，及实现幂运算。

算法分析

这个题目的难度是中等，所以如果用显而易见的那个O(n)算法，即直接循环n次，将n个x乘起来的话是肯定会超时的，所以，只能用递归分治算法，即一次只乘一半，设值为A，即当n为偶数时，结果是A*A；当n为奇数时，结果为A*A*x；当然，如果n为负数，则计算倒数即可。

例：

1. 计算pow(2, 4)

A = pow(2,2)
return A*A

2. 计算pow(2, 5)

A = pow(2, 5/2) = pow(2, 2)
return A * A *x

代码

public double myPow(double x, int n) {
    if(n==0) return 1;
    if(n==1) return x;
    if(n==-1) return 1.0/x;
    double tmp = myPow(x, n/2);
    if(n%2==0) {
    	return tmp*tmp;
    }
    if(n>0) {
    	return tmp*tmp*x;
    }
    return tmp*tmp/x;
}