[Leetcode] powx n x的n次方

Implement pow(x, n).

题意：计算x的次方

思路：这题的思路和sqrt的类似，向二分靠近。例如求4^5，我们可以这样求：res=4、4*4^4。就是将每次在res的基础上乘以x本身，换成，每次以x*=x的方式前行，这样时间复杂度为O(logn)，代码如下：

 class Solution {

 public:

     double pow(double x, int n)

     {

         double res=1.0;

         for(int i=n;i !=;i/=)

         {

             if(i% !=)

                 res*=x;

             x*=x;

         }

         return n<?/res:res;

     }

 };

把x的n次方划分成两个x的n/2次方相乘，然后递归求解子问题，结束条件是n为0返回1。代码：

 class Solution {

 public:

     double pow(double x, int n)

     {

         if(n==)    return ;

         double half=pow(x,n/);

         if(n%==)

             return half*half;

         else if(n>)

             return half*half*x;

         else

             return half*half/x;

     }

 };