C++刷leetcode（面试题16. 数值的整数次方）【快速幂】

糖逗

题目描述：

1. 
   
2. 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
   
3. 
   
4. 
   
5. 
   
6. 示例 1:
   
7. 
   
8. 输入: 2.00000, 10
   
9. 输出: 1024.00000
   
10. 示例 2:
    
11. 
    
12. 输入: 2.10000, 3
    
13. 输出: 9.26100
    
14. 示例 3:
    
15. 
    
16. 输入: 2.00000, -2
    
17. 输出: 0.25000
    
18. 解释: 2-2 = 1/22 = 1/4 = 0.25
    
19. 
    
20. 
    
21. 说明:
    
22. 
    
23. -100.0 < x < 100.0
    
24. n 是 32 位有符号整数，其数值范围是 [&#8722;231, 231 &#8722; 1] 。

复制代码

1. double quick_pow(double x, int n){
   
2.         if(n == 0) return 1;
   
3.         if(n % 2 == 1) return x * quick_pow(x, n-1);
   
4.         else{
   
5.             double temp = quick_pow(x, n/2);
   
6.             return temp*temp;
   
7.         }
   
8.     }
   
9.     double myPow(double x, int n) {
   
10.         if(n == 0) return 1;
    
11.         if(x == 1.0) return x;
    
12.         if(x == -1.0)return n %2 == 0 ? -x : x;
    
13.         int input = abs(n);
    
14.         double res = quick_pow(x, input);
    
15.         if(n < 0 && n!= INT_MIN) return 1/res;
    
16.         if(n > 0 && n!=INT_MAX)return res;
    
17.         return 0;
    
18. 
    
19.     }

复制代码

注意事项：题目中明确指出“不需要考虑大数问题”，所以添加了INT_MIN和INT_MAX判断。