LeetCode050——Pow(x, n)

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/powx-n/description/

题目描述：

知识点：二分法

思路：采用递归用二分法的思路计算幂函数

递归终止条件：

如果n为0，直接返回结果1。

递归过程：

（1）如果n大于0，设立临时变量temp，计算pow(x, n / 2)的值。如果n能被2整除，则返回temp * temp。如果n不能被2整除，则返回temp * temp * x。

（2）如果n大于0，设立临时变量temp，计算pow(x, n / 2)的值。如果n能被2整除，则返回temp * temp。如果n不能被2整除，则返回temp * temp / x。

时间复杂度是O(logn)级别的，空间复杂度即递归深度，也是O(logn)级别的。

JAVA代码：

public class Solution {

	public double myPow(double x, int n) {
        double result = 1;
        if(n == 0) {
        	return result;
        }else if(n > 0) {
        	double temp = myPow(x, n / 2);
        	if(n % 2 == 0) {
        		return temp * temp;
        	}else {
        		return temp * temp * x;
        	}
        }else {
        	double temp = myPow(x, n / 2);
        	if(n % 2 == 0) {
        		return temp * temp;
        	}else {
        		return temp * temp / x;
        	}
        }
    }
}

LeetCode解题报告：