题目描述 Implement pow(x, n).
题意计算x的n次方，考虑复杂度和n的取值。
n有可能是正数或者负数，分开计算。
用递归的做法讲复杂度降到O（logn）。
【Pow(x, n) （计算x的n次方）】实现代码：
class Solution {
public:
double pow(double x, int n) {
if(n==0)return 1;
if(n==1)return x;
double temp=pow(x,abs(n/2));
if(n>0)
{
if(n&1) return temp*temp*x;
else return temp*temp;
}
else
{
if(n&1)return 1.0/(temp*temp*x);
else return 1.0/(temp*temp);
}
}
};
推荐阅读
- 分治|全排列算法整理
- 数论|hdu 5322 Hope（分治+NTT）
- codeforces|Codeforces Global Round 10 D. Omkar and Bed Wars(思维，分块)
- hdu|【hdu 5354】Bipartite Graph【分治 并查集】
- codeforce514 D. Nature Reserve 凸函数三分
- 模板|LOJ #2340. 「WC2018」州区划分(FMT子集卷积)
- 点分治|点分治时间复杂度
- LeetCode 973 TopK问题 分治算法