日期 | 是否一次通过 | comment |
---|---|---|
2019-02-05 20:20 | N | 不会取巧 |
2019-02-06 09:20 | Y | 💪 |
2019-02-10 12:20 | N | 非递归一次通过,递归卡住了 |
题目:实现Math.pow(x, n)
思路:
-
>>1
相当于int型变量/2
;
- 尾递归和非递归终止条件的差异:
a. 尾递归终止条件是0:实际上1结束后,计算已经完成;如果终止条件是1,考虑幂次直接为0时,递归没有结束条件;
b. 非递归终止条件是1:实际上1结束后,计算已经完成;幂次为0的情况已经兜底;如果终止条件是0,无法跳出循环。
1. 尾递归
public class Solution {
public double Power(double base, int exponent) {
return helper(1.0, base, exponent);
}
private double helper(double result, double base, int exponent) {
if(exponent < 0) {
return helper(result, 1/base, -exponent);
}
if(exponent == 0) {
return result;
}
if((exponent & 1) == 1) {
return helper(result*base, base*base, exponent>>1);
} else {
return helper(result, base*base, exponent>>1);
}
}
}
2. 非递归
public class Solution {
public double Power(double base, int exponent) {
double result = 1.0;
if(exponent < 0) {
base = 1 / base;
exponent = -exponent;
}
while(exponent > 0) {
if((exponent & 1) == 1) {
result *= base;
}
base *= base;
exponent >>= 1;
}
return result;
}
}
网友评论