Description:

Implement pow(x, n)

 

大意：

实现pow(x, n)，即通常所说的x的n次方。

 

分析：

真是一道很考验人的题目，看似简单，其实有非常多的细节要注意：

1）由于x及返回值都是浮点数(double)，那么许多自定义的变量、返回值都尽量使用#.0f的方式定义与实现，显得正式和规范；

2）为了加快计算速度，在计算之前，需要把一些诸如x/n = 0.0/1.0的情况列出来；

3）使用divide and conquer加快计算速度；

4）注意符号的使用，x和n都可能为负数，结果的符号会变化；

5）注意边界条件，考虑到其中的test case会有n等于INT_MAX和INT_MIN的情况。

 

C++代码： 

1 class Solution { 2 public: 3  4     double calculate( double x, int n ) 5     { 6         if( n == 1 ) { 7             return x; 8         } 9         10         double divided = calculate( x, n / 2 );11         double result = 0.0f;12         if( n % 2 == 0 ) result = divided * divided;13         else result = divided * divided * x;14         15         return result;16     }17 18     double pow(double x, int n)19     {20         bool flag = false;21         if( n < 0 ) {22             flag = true;23             n = -n;24         }25         26         double result = 0.0f;27         28         if( n == 0 ) {29             return 1.0;30         }31         32         if( x == 0.0 ) {33             return 0.0;34         }35         36         if( x == 1.0 ) {37             return 1.0;38         } else if( x == -1.0 && n % 2 == 0 ) {39             return 1.0;40         } else if( x == -1.0 && n % 2 != 0 ) {41             return -1.0;42         } else {43             result = calculate( x, n );44             if( flag ) result = 1 / result;45             return result;46         }47     }48 };