LeetCode刷题记录3

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  

• 剑指offer上有很多种解法,但是解法几乎只能是快速幂
• double类型不能直接用等于号比较(但是书上和网上的题解都直接用的==)
• 虽然不用考虑大数问题,但是2.00000
  的-2147483648次幂不能先算正数次幂再取倒数,因为会溢出;算0.5的那么多次方,会超时.另外,这个数字没法在int里面变成正的,因为正数范围少了1,需要用long
• 判断奇数偶数只需要(n&1==1)

算法流程：

1 当 x = 0 时：直接返回 0 （避免后续 x = 1 / x操作报错）。

2 初始化 res = 1res=1 ；

3 当 n < 0 时：把问题转化至 n ≥0 的范围内，即执行 x = 1/x ，n = - n；

4 循环计算：当 n = 0 时跳出

当 n&1==1 时：将当前 x 乘入 res （即 res *= x ）；

执行 x = x^2,（即 x *= x ）；

执行 n 右移一位（即 n >>= 1）

5 返回 res。

作者：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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

错误的题解(没有使用快速幂):

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 myPow(double x, int n) {
        if(0==n)
            return 1;
        if(Math.abs(x)<0.00000001){
            return 0;
        }
        if(Math.abs(x-1)<0.00000001){
            return 1;
        }
        double res=x;
        if(n>=1){
            for(int i=1;i<n;i++){
                res*=x;
            }
        }else{
            long ln=-(long)n;
            res=1/x;
            for(long i=1;i<ln;i++){
                res*=(1/x);
            }
        }
        return res;
    }
}