[LeetCode74]Pow(x,n)

本文主要是介绍[LeetCode74]Pow(x,n)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Implement pow(x, n).

幂运算 Calculates x raised to the power of y.

Analysis:

If we just use the normal way of calculation, when face 1 to the power of 10000, the computation complexity is too high.

Consider this way:
If we want to get 2^10,

2^10 = 2^4 * 2^4 *2^2
2^4 = 2^2*2^2
2^2 = 2*2

Let's see this in a bottom-up way, totally it needs to loop n/2 > 0 times, first we have 2^1=2, then we can have 2^2 = 2*2=4, and again we have 2^4 = 4*4, (key point:) and if n%2==1, we need one more previous value, which is 2^2 here, so we have 2^4*2^4*2^2 = 2^10.

We use binary divide method.

Java

public double pow(double x, int n) {if(n<0){return 1.0/power(x, -n);}else {return power(x, n);}}public double power(double x, int n){if(n==0)return 1;double v = power(x, n/2);if(n%2==0)return v*v;elsereturn v*v*x;}

c++

double power(double x, int n){if(n==0)return 1;double v = power(x,n/2);if(n%2 == 0)return v *v;elsereturn v* v* x;
}
double pow(double x, int n) {if(n<0)return 1.0 / power(x,-n);elsereturn power(x,n);
}

这篇关于[LeetCode74]Pow(x,n)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---