50. Pow(x, n)

50. Pow(x, n)

实现 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

思路：快速幂(分治) ，即把幂次拆分成一半计算后相乘
时间复杂度: O(longn)
非递归空间复杂度: O(1)
递归空间复杂度: O(logn)

分治 + 递归
class Solution {
    //分治 + 递归
    public double myPow(double x, int n) {
      
      //0.边界处理
      if(n==0) return 1;
      if(n==-1) return 1/x;//-1比较特殊 不论怎么右移一位 其结果不变都是 -1
 
      //1.定义需要的数据结构
      boolean odd = (n&1)==1;//是否是奇数幂 最后一位是1就是奇数
      
      //2. 拆分一半递归
      double half = myPow(x,n>>1);
      half *= half;

      //3.返回结果
      /** 
      奇数 如果n为负数 n右移两位得到的值是不同的,是向上取整后再加上负号  
      比如 -5除以2等于2.5 向上取整为3 加上负号 得到的值是-3  
      n < 0时：3^-21 = 3^-11 * 3^-11 *3
      n > 0时：3^21  = 3^10 * 3^10 *3
      n为正数本来就是乘以x 
       所以N为奇数不论N正负都一样 ，直接乘以 x即可
      */
      return odd?(half*x):half;
      

    }

}

分治+递归 执行结果.png

分治 + 非递归

举例： 求3的21次方
21 的二进制就是 10101
21 = (12^4) + (02^3) +(12^2) + (02^1) + (12^0)
3^21 = 3^(12^4).... 3^(12^0);
然而： 3⁽²1) = 3⁽²0) * 3⁽²0) , 如果此时我们设3⁽²0)为X ，那么忽略次幂的1 、0 单独处理 2^4、23、2^2、21、2^0
3^21 = X * X^2 * X^4 * X^8 * X^16

所以就有了以下算法

class Solution {

    //非递归
    public double myPow(double x, int n) {
      
      //1. 判断是否是负数
      boolean neg = n < 0;
      
      //2. 负数次幂先转成正数，因n的取值范围最小值得绝对值已经超出int的范围[int类型的最大值是 2^31 - 1] 所以需要转成长整型long
      long y = neg? - ((long)n):n;

      //3. 循环 终止条件y>0
      double result = 1.0;//结果
      while(y>0) {

         //有效次幂
         if((y&1)==1){
            result *= x;
         }

         //计算每轮循环的值: 单次两个x相乘，x可以是 x^0 .... x^z
         x *= x;
         //y的二进制位不断的右移，这样就能得到所有次幂
         y = y>>1;
      }

      return neg?(1/result):result;
    
    }

}

快速幂公式补充

假设有这样一道题：请设计一个算法求x的y次幂 模上z的结果：x^y%z

题意分析: 如果x y 都很大那x的y次幂就会是个非常大的值，可能会造成溢出的情况这是需要解决的，而且一般模运算的左右两边都需要是整数 这点需要注意 ; 边界条件 y > 0 && z != 0 ，x 是整数就行

计算公式：(a*b) %p = ( (a%p) * (b%p) )%p

非递归

    public long powMod(int x, int y, int z) {

      if( y < 0 || z == 0) return 0;

      long result = 1%z;//结果
      x = x%z;
      while(y>0) {
         //有效次幂
         if((y & 1)==1){
             //如果最后一位二进制位是1 就累乘以 x
            result = (result * x)%z;
         }
         x = (x * x)%z;
         //y的二进制位不断的右移，这样就能得到所有次幂
         y = y>>1;
      }
      return result;
    }
        

递归

    public long powMod(int x, int y, int z) {
      if(y < 0 || z == 0) return 0;
      if(y == 0) return 1%z;
      long half = powMod(x,y>>1,z);
      half *= half;
      if((y&1)==0){//偶数
          return half % z;
      }else {//奇数
          return (half * (x%z)) % z;
      }
    }