首页 > 代码库 > 50. Pow(x, n)

50. Pow(x, n)

一、描述

  1、题目

     技术分享

  2、题意

      实现 X 的 n 次方。

 

二、解答

  1、思路:

    将 n 除以2, 用X*X 代替X,保持值不变。需要注意的是,n 可以取负数,此时 将 n 变为正数进行计算,X 变为 1/X 。另外,当 n 取 为 Integer.Min_VALUE 时,即为-2147483648时, n 取 -n时溢出,需要单独处理。

  

public static double myPow(double x, int n) {
        
        if(n == 0) return 1;
        if(x == 1) return 1;
        
        if(n > 0) {
            if(n % 2 == 0)
                return myPow(x*x, n/2);
            else 
                return x * myPow(x*x, n/2);
        }
        else {
            if(n == -2147483648)
                return 1/x * myPow(1/x, -(n+1));
            else
                return myPow(1/x, -n);
        }
    }

 

2、优化:

    上述代码看起来比较复杂,观察后可以发现,可以统一调用,提高简易度。

  

public static double myPow2(double x, int n) {
        
        if(n == 0) return 1;
        if(x == 1) return 1;
        
        if(n < 0) {
            if(n == -2147483648)
                return 1/x * myPow2(1/x, -(n+1));
            else {
                n = -n;
                x = 1/x;
            }
        }
        return (n%2 == 0 ? myPow2(x*x, n/2) : x * myPow2(x*x, n/2));
        
    }

 

三、总结

    处理数值时,忽视边界情况,如整形最小值(-2147483648)取反后,值会溢出。整形最大值为 -2147483647。即不论什么类型,最小值取反总会溢出,得不到目标结果。

50. Pow(x, n)