leetcode 50. Pow(x, n) 谷歌面试题
本帖最后由 Seawolf 于 2019-8-17 14:47 编辑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
页:
[1]