LeetCode

question

Implement pow(x,n), which calculates x raised to the power n (i.e. xn).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

题解

递归

x→x2→x4→x9→x18→x37

  • 计算x^n^时,可以递归算出x[n/2](其中[n/2]表示对n/2进行向下取整)
  • 令y=x^[n/2]^,如果n为偶数,那么x = yy;如果n为奇数,那么x=y y *x
  • 当n=0时,x0 = 1
class Solution {
   public double quickCalculate(double x,int N) {
        if(N==0)
            return 1.0;
        double y = quickCalculate(x,N/2);
        return N%2==0?y*y:y*y*x;
   }
   public double myPow(double x, int n) {
       int N = n;
       return N>=0?quickCalculate(x,N):1.0/quickCalculate(x,-N);
   }
}

迭代

x→x2→x4→x9→x18→x37 →x75

x→x2→x4→x8x→x16x2→x32x4x →x64x8x2*x

  • x4→x9中额外乘的x在后面的运算中平方了3次(23),在x75中贡献了x8
  • x37→x75中额外乘以的x在x75中贡献了x(20)
  • x18→x37中额外乘的x在后面中的运算中平方了1次(21),在x75贡献了x2

这些数的之和刚好对应的75的二进制表示:75=64+8+2+1=(1001011)2

Amazing!

现在我们只需要将指数表示成二进制数,然后如果n的第k个(从右往左,从 0 开始计数)二进制位为 1,那么我们就将对应的贡献x的2k次幂计入答案

x→x2→x4→x9→x18→x37

  • 计算xn时,可以递归算出x[n/2](其中[n/2]表示对n/2进行向下取整)
  • 令y=x[n/2],如果n为偶数,那么x = yy;如果n为奇数,那么x=y y *x
  • 当n=0时,x0 = 1
cclass Solution {
   public double quickMul(double x, long N) {
        double contribution = x;
        double multiply = 1.0;
       // 对N进行二进制拆分
       while (N>0) {
            if(N%2 == 1) {
                //如果N二进制表示的最低位为 1,那么需要计入贡献
                multiply *= contribution;
            }
           //每拆分一次,贡献就平方一次
            contribution *= contribution;
           //舍弃N二进制表示的最低位
            N /= 2;
        }
        return  multiply;
   }
   public double myPow(double x, int n) {
       long N = n;
       return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
   }
}
Pay by WeChat

Pay by WeChat

Comment

This is just a placeholder img.