leetcode 50. Pow(x, n) 谷歌面试题

Seawolf

1. Implement pow(x, n), which calculates x raised to the power n (xn).
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: 2.00000, 10
   
6. Output: 1024.00000
   
7. Example 2:
   
8. 
   
9. Input: 2.10000, 3
   
10. Output: 9.26100
    
11. Example 3:
    
12. 
    
13. Input: 2.00000, -2
    
14. Output: 0.25000
    
15. Explanation: 2-2 = 1/22 = 1/4 = 0.25
    
16. Note:
    
17. 
    
18. -100.0 < x < 100.0
    
19. n is a 32-bit signed integer, within the range [&#8722;231, 231 &#8722; 1]

复制代码

1. class Solution {
   
2.     public double myPow(double x, int n) {
   
3.         
   
4.             double result = 1.0;
   
5.            
   
6.             while(n != 0) {
   
7.         
   
8.         if(n > 0){
   
9.             
   
10.             result = x * result;
    
11.             
    
12.             n = n-1;
    
13.         }
    
14.         
    
15.         else{
    
16.             
    
17.                 double a = Math.abs(x);
    
18.                
    
19.             result =  (1/x) * result;
    
20.             
    
21.             n = n + 1;
    
22.         }
    
23.         
    
24.             }
    
25.            
    
26.             return result;
    
27.         
    
28.     }
    
29. }

复制代码

这个code的问题是当n 很大的时候(十亿)， 系统会 run out of time, 要解决这个问题就要引入 divide and conquer.

1. class Solution {
   
2.     public double myPow(double x, int n) {
   
3.         //1.边界条件 x ^ 0 = 1
   
4.         if(n == 0)
   
5.             return 1;
   
6.         
   
7.         //2.折半拆分为子任务，子任务黑盒递归：2边子任务一样，只要算一边
   
8.         //当n = Integer.MIN_VALUE的时候要特殊处理
   
9.         //因为整形范围是-2^31到2^31 -1，所以或者我们使用long来存转换的数，或者特殊判断一下
   
10.         double halfPow;
    
11.         if(n < 0){
    
12.             if (n == Integer.MIN_VALUE) {
    
13.                 // return 1.0 / (myPow(x,-(Integer.MIN_VALUE+1)) * x);
    
14.                 return 1.0 / (myPow(x, Integer.MAX_VALUE) * x);
    
15.             }
    
16.             return 1.0 / myPow(x, -n);
    
17.         }
    
18.         halfPow = myPow(x, n / 2);
    
19. 
    
20.         
    
21.         //3.返回值任务：把halfPow拼成fullPow
    
22.         //要先偶后奇，不然报错
    
23.         //偶
    
24.         double res;
    
25.         if(n % 2 == 0){
    
26.             res = halfPow * halfPow ;
    
27.         //奇
    
28.         }else{
    
29.             res = halfPow * halfPow * x;
    
30.         }
    
31.         
    
32.         //4.返回
    
33.         return res;
    
34.     }
    
35. }

复制代码

什么是Integer.MAX_VALUE 和 Integer.MIN_VALUE呢？

1. Integer的MIN_VALUE
   
2. 在JDK中，整型类型是有范围的  -2147483648～2147483647  （ -2^31 --- 2^31-1）
   
3. 最大值为Integer.MAX_VALUE，即2147483647，最小值为Integer.MIN_VALUE -2147483648。
   
4. 对整形最大值加1，2147483648（越界了），那么此时值为多少呢？结果是-2147483648，即是Integer.MIN_VALUE。
   
5. 类似的，对Integer.MIN_VALUE取反或者取绝对值呢？仍为Integer.MIN_VALUE，因为值为-2147483648，绝对值2147483648超过Integer.MAX_VALUE 2147483647。
   
6. 所以就有以下结果
   
7. Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
   
8. //返回 Integer 值的绝对值。
   
9. Math.abs(Integer.MIN_VALUE) =  Integer.MIN_VALUE
   
10. Long，short，byte的结论是相同的。
    
11. 这个语句的输出结果：
    
12. System.out.println(1<<31== Integer.MIN_VALUE);//true

复制代码