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

Seawolf

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100
Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

class Solution {
    public double myPow(double x, int n) {
        
            double result = 1.0;
            
            while(n != 0) {
        
        if(n > 0){
            
            result = x * result;
            
            n = n-1;
        }
        
        else{
            
                double a = Math.abs(x); 
                
            result =  (1/x) * result;
            
            n = n + 1;
        }
        
            }
            
            return result;
        
    }
}

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

class Solution {
    public double myPow(double x, int n) {
        //1.边界条件 x ^ 0 = 1
        if(n == 0)
            return 1;
        
        //2.折半拆分为子任务，子任务黑盒递归：2边子任务一样，只要算一边
        //当n = Integer.MIN_VALUE的时候要特殊处理
        //因为整形范围是-2^31到2^31 -1，所以或者我们使用long来存转换的数，或者特殊判断一下
        double halfPow;
        if(n < 0){
            if (n == Integer.MIN_VALUE) {
                // return 1.0 / (myPow(x,-(Integer.MIN_VALUE+1)) * x);
                return 1.0 / (myPow(x, Integer.MAX_VALUE) * x);
            }
            return 1.0 / myPow(x, -n);
        }
        halfPow = myPow(x, n / 2);

        
        //3.返回值任务：把halfPow拼成fullPow
        //要先偶后奇，不然报错
        //偶
        double res;
        if(n % 2 == 0){
            res = halfPow * halfPow ;
        //奇
        }else{
            res = halfPow * halfPow * x;
        }
        
        //4.返回
        return res;
    }
}

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

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