剑指 Offer 16. 数值的整数次方

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
1
2

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
1
2

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
1
2
3

解法一：位运算 求解思路

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickPow(x,N) : 1 / quickPow(x,-N);
    }
    public double quickPow(double x,long N){
       double ans = 1.0;
       //需要的值：
       while( N > 0){
           //说明该数的二进制 有1
           if( N % 2 == 1){
               ans *= x;
           }
           x *= x;
           //该数右移动
           N /= 2;
       }
       return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

解法二：递归 分治思想

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickPow(x,N) : 1 / quickPow(x,-N);
    }
    public double quickPow(double x,long N){
      if(N == 0) return 1.0;
      double y = quickPow(x,N / 2);
      return N % 2 == 0 ? y*y : y*y *x;
    }
}
1
2
3
4
5
6
7
8
9
10
11