l**h
发帖数: 893 | 1 比如下面这个log(n)的, 很容易实现，为什么喜欢考这个题？
public double pow(double x, int n) {
if (n == 0) return 1;
if (x == 0) return 0;
boolean positive = true;
if (n < 0) {
positive = false;
n = -n;
}
double tmp = pow(x, n/2);
double ret;
if (n%2 == 0) {
ret = tmp*tmp;
}
else {
ret = x*tmp*tmp;
}
return positive ? ret : 1.0/ret;
} |
t*********h
发帖数: 941 | 2 pow(1,12323243243)?
【在 l**h 的大作中提到】
: 比如下面这个log(n)的, 很容易实现，为什么喜欢考这个题？
: public double pow(double x, int n) {
: if (n == 0) return 1;
: if (x == 0) return 0;
: boolean positive = true;
: if (n < 0) {
: positive = false;
: n = -n;
: }
:
|
b*********h
发帖数: 103 | 3 就算容易实现 也不是都可以实现的好 从实现上也能看出功底 比如说这个递归可以更
简洁 甚至不用递归 |
j***n
发帖数: 301 | 4 agreed. theres definitely room for improvement, not necessarily in terms of
complexity but implementation.
【在 b*********h 的大作中提到】
: 就算容易实现 也不是都可以实现的好 从实现上也能看出功底 比如说这个递归可以更
: 简洁 甚至不用递归
|
l**h
发帖数: 893 | 5 找到一个号称constant time解决的，还没看懂，最后一种解法：
http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%
【在 l**h 的大作中提到】
: 比如下面这个log(n)的, 很容易实现，为什么喜欢考这个题？
: public double pow(double x, int n) {
: if (n == 0) return 1;
: if (x == 0) return 0;
: boolean positive = true;
: if (n < 0) {
: positive = false;
: n = -n;
: }
:
|
c********t
发帖数: 5706 | 6 最后一种解法貌似也是lgn的。按n的binary走的，本质与n/2应该一样
pow(double, double)应该怎么做？
【在 l**h 的大作中提到】
: 找到一个号称constant time解决的，还没看懂，最后一种解法：
: http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%
|
r*****e
发帖数: 146 | 7 为啥叫constant time? 那个实现就是logN (based on 2)的解法啊。
【在 l**h 的大作中提到】
: 找到一个号称constant time解决的，还没看懂，最后一种解法：
: http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%
|
w***o
发帖数: 109 | 8
好像不是Constant time。任然是O（lgn）。而且还可以简化：
public class Solution {
public double pow(double x, int n) {
boolean isNeg = n < 0;
if(n < 0)
n = -n;
double ret = 1.0;
while(n>0) {
if((n&1) >0)
ret *= x;
x *= x;
n >>= 1;
}
return isNeg? 1.0/ret : ret;
}
}
【在 l**h 的大作中提到】
: 找到一个号称constant time解决的，还没看懂，最后一种解法：
: http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%
|
f*******n
发帖数: 12623 | 9 return exp(n * log(x)) 不就行了吗？ |
