目录
刷题日期：18:5215 星期三2021年3月24日
个人刷题记录，代码收集，来源皆为leetcode
经过多方讨论和请教，现在打算往Java方向发力
主要答题语言为Java
题目：
剑指 Offer 16. 数值的整数次方
难度中等137
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1-104 <= xn <= 104
题目分析
这道题开始进入书本的第三章，高质量的代码，自己平时写题也要注意代码规范等等。
提示限定了题目的数值范围。
最简单的乘法肯定是不行的，最后也会有其他不为常人所知的公式可以解题，只要能掌握中等的解法就可。
初始解答：
最简单的解法
class Solution {
public double myPow(double x, int n) {
double res = 1;
for (int i = 0; i < n; i++) {
res *= x;
}
return res;
}
}
但是没有考虑n为负的情况，还得加上判断，以及x为0的情况。
不断增加边界输入的结果。
class Solution {
public double myPow(double x, int n) {
if (x == 0) return 1; //这里应该是不对的，return 0
if (x == 1) return 1;
double res = 1;
if (n > 0) {
for (int i = 0; i < n; i++) res *= x;
}
if (n < 0) {
double y = 1 / x;
for (int i = 0; i < (0-n); i++) res *= y;
}
return res;
}
}
还是存在问题，这里没有理解为什么能错，x已经求过倒数，乘这么多遍，还能输出1。执行结果： 解答错误
显示详情
输入：
2.00000 -2147483648
输出：
1.00000
预期结果：
0.0
Summer1121 （编辑过）2020-03-01
-2147483648这个指数也很有意思呢，如果为了用移位取代除法来加速，负数是用补码表示的，补码的除法逻辑又不能用移位来解决…就需要取n的绝对值…因为int的取值范围是-2147483648到2147483647…所以java的Math.abs(n)在这个时候返回的还是-2147483648…leetcode的用例还是秀，这种边界…
Java 代码中 int32 变量 n \in [-2147483648, 2147483647]n∈[−2147483648,2147483647] ，因此当 n = -2147483648n=−2147483648 时执行 n = -nn=−n 会因越界而赋值出错。解决方法是先将 nn存入 long 变量 b ，后面用 bb 操作即可。
作者：jyd
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/
来源：力扣（LeetCode）
看来不是我自己一个人卡在这里，按照官方精选的方法二改正了一番，还是卡在这里，也没有看到有循环解出来的，还是放弃了。这里参考方法一，用了书里的公式，递归实现
class Solution {
public double myPow(double x, int n) {
if(n == 0) return 1; //特殊情况
if(n == 1) return x; //特殊情况
if(n == -1) return 1/x;
double half = myPow(x,n / 2); //为偶数的话直接先求一半的
double mod = myPow(x, n % 2); //为奇数的话这一项就为x，否则为1
return half * half * mod; //不论奇偶都能直接通过
}
}
执行结果：
通过
显示详情
执行用时：1 ms, 在所有 Java 提交中击败了98.50%的用户
内存消耗：37.9 MB, 在所有 Java 提交中击败了20.28%的用户
然后学习了官方精选的迭代解法，就不再敲一遍了。
学习他人：
方法一
递归