剑指Offer:数值的整数次方

题目

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

分析

这道题的题意很明显,实现C语言库函数中的pow函数
但是我们在考虑这道题的时候,不能因为太过简单而放松“警惕”,稍不留神就可能会“翻车”,当然作为老司机我们肯定是不会让这种事情发生的。
下面我们来分析一下这道题的易错点

  • 要考虑到指数可能会出现负数的情况,这时我们要先取绝对值,算出结果之后再取倒数。
  • 既然考虑到了取倒数的情况,就要特殊判断一下对0取倒的情况。方式程序崩溃。

考虑过特殊情况之后,我们再想想看能不能再优化一下代码,提升一下时间效率或者空间效率。
这道题的本质是求一个数的n次方,那么我们可以先求出这个数的n/2的次方,然后再把n/2的次方的结果平方一下即可。
11.jpg

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public double Power(double base, int exponent) {
if (base == 0.0 && exponent < 0)
return 0;
int absExponent = exponent;
if (exponent < 0)
absExponent = -exponent;

double ans = P(base, absExponent);
if (exponent < 0)
return 1/ans;
return ans;
}
public double P(double base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
double ans = P(base, exponent >> 1);
ans*=ans;
if ((exponent&1) == 1)
ans*=base;
return ans;
}
}
由于位运算的效率要比一般运算发的效率高,我们还可以利用位运算在进一步的优化代码。既然要优化,我们就要把优化做到极致。