PS：《剑指offer》是很多同学找工作都会参考的一本面试指南，同时也是一本算法指南（为什么它这么受欢迎，主要应该是其提供了一个循序渐进的优化解法，这点我觉得十分友好）。现在很多互联网的算法面试题基本上可以在这里找到影子，为了以后方便参考与回顾，现将书中例题用Java实现（第二版），欢迎各位同学一起交流进步。
GitHub： https://github.com/Uplpw/SwordOffer。
完整题目链接： https://blog.csdn.net/qq_41866626/article/details/120415258
目录
1 题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。
leetcode链接： 数值的整数次方（以下代码已测试，提交通过）
2 测试用例
一般是考虑功能用例，特殊（边缘）用例或者是反例，无效测试用例这三种情况。甚至可以从测试用例寻找一些规律解决问题，同时也可以让我们的程序更加完整鲁棒。
（1）功能用例：正常的x，n值，如3，4。
（2）边缘用例：n = 0，1，负数。
（3）无效用例：底数是0。
3 思路
分析：
本题由于不考虑大数问题，所以工作量少了一些，但还是要注意细节，根据提前想好的测试用例考虑特殊情况。
注意：浮点数判断是否为0，并不是直接和0作比较，而是根据需要给出一个精度进行判断，即两种之差是否在该精度内。
下面是两种解决方法的具体过程：
解法1：循环迭代：
这种方法最简单直接，也是最容易想到的方法，不过要注意几种情况，数据没有意义注意处理方式（用函数返回值来提示错误；用一个全局变量来提示错误；抛出异常；）。
- 当底数为0时，（1）指数为负值，这时候就会出现分母为0，无意义，可以抛出异常；（2）其他值返回0。
- 当指数为正，迭代循环直接求解即可；
- 当指数为负时，一般流程是先利用相反数转为正指数求解，再求其倒数，有一种特殊情况需要注意，即指数 n = Integer.MIN_VALUE，此时其相反数还是它本身，因此这样求解会出现问题（特别是下面的递归求解直接导致栈溢出），针对这个问题，我们可以先计算一个底数，然后 n=-n-1 即可避免这种特殊情况（具体见代码）。
解法2：递归
- 求 x n x^n xn，我们可以将其转为 x n / 2 ∗ x n / 2 x^{n /2}*x^{n /2} xn/2∗xn/2 或者 x ∗ x n / 2 ∗ x n / 2 x*x^{n /2}*x^{n /2} x∗xn/2∗xn/2（n分奇偶），这样就可以使用递归求解，通过空间换时间，减少时间复杂度。
- 同样要注意解法1中的几种特殊情况，特别是当指数 n = Integer.MIN_VALUE时。这里不再重复。
4 代码
算法实现：
public class Power {
// 循环计算 注意特殊情况，可以抛出异常
public static double power(double x, int n) throws Exception {
if (equal(x, 0)) {
if (n == 0) {
return 1;
} else if (n < 0) {
throw new Exception("分母为0");
}
return 0;
}
if (n < 0) {
double pow = x;
int count = -n - 1;
for (int i = 1; i < count; i++) {
pow = pow * x;
}
return 1 / pow;
} else {
double pow = 1;
for (int i = 0; i < n; i++) {
pow = pow * x;
}
return pow;
}
}
// 递归计算，可以抛出异常
public static double powerRecursionly(double x, int n) throws Exception {
if (equal(x, 0)) {
if (n == 0) {
return 1;
} else if (n < 0) {
throw new Exception("分母为0");
}
return 0;
}
if (n < 0) {
return 1 / x * powerCoreRecursionly(1 / x, -n - 1);
} else {
return powerCoreRecursionly(x, n);
}
}
public static double powerCoreRecursionly(double x, int n) {
if (n == 0) {
return 1;
} else {
if ((n & 1) == 0) {
double temp = powerCoreRecursionly(x, n >> 1);
return temp * temp;
} else {
double temp = powerCoreRecursionly(x, n >> 1);
return x * temp * temp;
}
}
}
// 判断double类型是否相等，主要是判断两者之差是否在很小的区间内
public static boolean equal(double x, double y) {
return -0.000001 < (x - y) && (x - y) < 0.000001;
}
public static void main(String[] args) throws Exception {
System.out.println("2^3=" + powerRecursionly(2, 3));
System.out.println("2^-3=" + powerRecursionly(2, -3));
System.out.println("0^3=" + powerRecursionly(0, 3));
System.out.println("0^-3=" + powerRecursionly(0, -3));
}
}
参考
在解决本书例题时，参考了一些大佬的题解，比如leetcode上的官方、K神，以及其他的博客，在之后的每个例题详解后都会给出参考的思路或者代码链接，同学们都可以点进去看看！
本例题参考：
https://www.jianshu.com/p/83b5663a519b
本文如有什么不足或不对的地方，欢迎大家批评指正，最后希望能和大家一起交流进步、拿到心仪的 offer !!!