题目

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

思路1

第一种是将整数n变成二进制的形式，再对x进行快速幂计算
代码

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         if(x == 0) return 0;
  4.         long b = n;
  5.         double res = 1.0;
  6.         if(b < 0) {
  7.             x = 1 / x;
  8.             b = -b;
  9.         }
  10.         while(b > 0) {
  11.             if((b & 1) == 1) res *= x;
  12.             x *= x;
  13.             b >>= 1;
  14.         }
  15.         return res;
  16.     }
  17. }

思路二

利用分治思想，直接递归计算

  1. public double myPow(double x, int n) {
  2.     if(n == 0) return 1;
  3.     if(n == 1) return x;
  4.     if(n == -1) return 1 / x;
  5.     double half = myPow(x, n / 2);
  6.     double mod = myPow(x, n % 2);
  7.     return half * half * mod;
  8. }