Pow [source code]
public class Pow {
static
/******************************************************************************/
class Solution {
public double myPow(double x, int _n) {
int n = _n;
if (n < 0) {
x = 1 / x;
n = -n;
}
double A = 1.0;
char[] bits = Integer.toBinaryString (n).toCharArray ();
for (int i = 0; i < bits.length; i++) {
A *= A;
if (bits[i] == '1')
A *= x;
}
return A;
}
}
/******************************************************************************/
public static void main(String[] args) {
Pow.Solution tester = new Pow.Solution();
double[] inputs = {
2.00000, 10.0, 1024.0,
2.1, 3.0, 9.26100,
};
for (int i = 0; i < inputs.length / 3; i++) {
double x = inputs[3 * i], ans = inputs[3 * i + 2];
int n = (int) inputs[3 * i + 1];
System.out.println (Printer.separator ());
double output = tester.myPow (x, n);
System.out.printf ("%f and %d -> %s, expected: %f\n",
x, n, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
大量的downvote, 估计是只接受数学解法, 大概看看, 不浪费时间了, 能写个搜索就写一个搜索解法; 另外, 之前有做过一题用/2来实现一般的除法, 这里不知道有没有类似的操作;
HAC上面看到的一个算法, 好像比较好记, 实现一下看看:
后来想了一下好像不行, 这个算法是只能解决integer的指数运算, 没有说double怎么做?
想不通, 不想了;
原来上面这个算法是可以的, 速度是24ms (10%). 注意处理一下负指数就行了;
不过写完了还是有一个小问题, 下面那个从右到左的方法, 实际上还是挺好理解的, 可以看一下editorial的文章, 讲的实际上很清楚, 就是一个利用了2的操作, 然后循环本身的一个优化; 但是这里这个从左到右的例子, 到底是什么原理? 怎么declarative的解释? 想了半天, 唯一的说法就是, 反正最后被square的次数是固定的, 从左到右从右到左都是无所谓的, 只要在有1的bit的位置, 记得多乘一个g就行了;
感觉这个解释实际上不是特别合理;
editorial
Approach #1 Brute Force [Time Limit Exceeded]
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
for (long i = 0; i < N; i++)
ans = ans * x;
return ans;
}
};
Approach #2 Fast Power Algorithm Recursive [Accepted]
class Solution {
private double fastPow(double x, long n) {
if (n == 0) {
return 1.0;
}
double half = fastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return fastPow(x, N);
}
};
难怪讨骂好吧. 这个就是HAC上面的算法;
事实上, 这个就是我上面HAC上面看来的这个算法, 一模一样的; 我当时以为不能handle double, 不过这里看来, 实际上是可以的;
Approach #3 Fast Power Algorithm Iterative [Accepted]
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
double current_product = x;
for (long i = N; i > 0; i /= 2) {
if ((i % 2) == 1) {
ans = ans * current_product;
}
current_product = current_product * current_product;
}
return ans;
}
};
不对, 实际上他这里实现的是这个:
不过其实这两个好像都是差不多的算法; 另外, 不要被这里的这个伪代码给骗到了, 实际上这个很好记忆, 循环里面的实际上直接就是A = S, S = S两个而已;
另外第三行的那个if e != 0其实可以看出来, 不是必须的, 反正下一个iteration也自动就terminate了;
这个算法也算是记下来了, 那我就实现我上面看到的从左到右的写法;
@pei-heng said in Short and easy to understand solution:
public class Solution {
public double pow(double x, int n) {
if(n == 0)
return 1;
if(n<0){
n = -n;
x = 1/x;
}
return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
}
}
@ChrisHuang said in Short and easy to understand solution:
If n is Integer.MIN_VALUE, the code will have overflow runtime error.
@4acreg said in Short and easy to understand solution:
you need one additional if statement
if( n < 0 ) { if( n == Integer.MIN_VALUE ) { ++n; n = -n; x = 1/x; return x * x * pow( x * x, n / 2 ); } n = -n; x = 1 / x; }
@mingjun said in 5 different choices when talk with interviewers:
After reading some good sharing solutions, I'd like to show them together. You can see different ideas in the code.
1. nest myPow
double myPow(double x, int n) { if(n<0) return 1/x * myPow(1/x, -(n+1)); if(n==0) return 1; if(n==2) return x*x; if(n%2==0) return myPow( myPow(x, n/2), 2); else return x*myPow( myPow(x, n/2), 2); }2. double myPow
double myPow(double x, int n) { if(n==0) return 1; double t = myPow(x,n/2); if(n%2) return n<0 ? 1/x*t*t : x*t*t; else return t*t; }3. double x
double myPow(double x, int n) { if(n==0) return 1; if(n<0){ n = -n; x = 1/x; } return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2); }4. iterative one
double myPow(double x, int n) { if(n==0) return 1; if(n<0) { n = -n; x = 1/x; } double ans = 1; while(n>0){ if(n&1) ans *= x; x *= x; n >>= 1; } return ans; }5. bit operation
see this [solution][1]
If you have other ideas, please leave it below. Thanks.
[1]: https://leetcode.com/discuss/12004/my-answer-using-bit-operation-c-implementation
懒得看了;
另外一个处理因为flip导致的overflow的方法:
@aesi123 said in 5 different choices when talk with interviewers:
@shu.zhang As pointed earlier, it suffers from overflow.
You can convert n to -2147483646 before flipping the sign. (Convert it to -2147483647 will give you incorrect result if the base number is negative.)
不过到我现在提交为止, 好像这个bug其实都没有修复; 这里, 也看出来为什么在editorial里面, 都是先把n给cast到long了; 天天在这种corner case上面纠结, 确实是有点搞自己;
下面有一个也很好玩的解法:
@dingty said in 5 different choices when talk with interviewers:
Another iterative one like 4, may not be the fastest. The idea is to multiply x by n times, but with some speed up giving you an average O(log n) runtime.
class Solution {
public:
double myPow(double x, int n) {
if (!n) return 1.0;
if (n < 0) {
n = -(++n);
x = 1 / x;
} else
n--;
double result = x;
while (n) {
double y = x;
for (int i = 1; i > 0 && i <= n; i *= 2) {
result *= y;
y *= y;
n -= i;
}
}
return result;
}
};
刚开始没有看懂, 那就画trace:
这里这个写法就能看出来这个问题跟除法那一题的相似性了, 两道题目都依赖于一个关键的信息, every integer is the sum of powers of 2. 当然, division那一题当时实际上是更难一点的, 但是这里上面这个人的解法, 其实就是利用了类似的观察;
但是感觉他这个最后实际上的算法跟division那题还是有点区别的, 因为如果按照sum of powers of 2的思路, 9不是应该是8 + 1这样分解就行了吗, 但是他这里的分解你可以看到, 实际上是1 + 1 + 2 + 4 + 1; 不理解背后是什么思路;
不过其实有所谓吗? 这题的核心点, 就是利用square和2之间的对应性; 反正最后只要拆分成power of 2, 哪怕你跟他这里这样, 拆的太细了, 也无所谓, 都可以使用类似的square来加速;
另外, 他这个拆分的具体的操作不知道是不是什么已知的套路;
@mathsam said in My answer using bit operation (C++ implementation):
class Solution {
public:
double pow(double x, int n) {
if(n<0){
x = 1.0/x;
n = -n;
}
int unsigned m = n;
double tbl[32] = {0};
double result = 1;
tbl[0] = x;
for(int i=1;i<32;i++){
tbl[i] = tbl[i-1]*tbl[i-1];
}
for(int i=0;i<32;i++){
if( m & (0x1<<i) )
result *= tbl[i];
}
return result;
}
};
In bit format and for a unsigned number, the number is represented as
k0*2^0 + k1*2^1 + ... +k31*2^31. Therefore, once we know the pow(x,2^0), pow(x,2^1), ..., pow(x,2^31), we can get pow(x,n). And pow(x,2^m) can be constructed easily as pow(x,2^m) = pow(x,2^(m-1)*pow(x,2^(m-1).
这个就是把之前从右到左的算法给更加直白的描述了一点, 所有的base全都存下来, 虽然是没有必要的;
submission最优解: 19(75):
class Solution {
public double myPow(double x, int n) {
boolean isNegPow = false;
if (n < 0) {
x = 1 / x;
isNegPow = true;
n = -(n + 1); // Avoid overflow when pow == MIN_VALUE
}
double ans = 1, tmp = x;
while (n != 0) {
if (n % 2 == 1) {
ans *= tmp;
}
tmp *= tmp;
n /= 2;
}
if (isNegPow) {
ans *= x;
}
return ans;
}
}
就是从右到左的写法, 看来比从左到右快一点; HAC书上说的那个从左到右更快, 看来也是未必;
Problem Description
Implement pow(x, n).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Difficulty:Medium
Total Accepted:195.9K
Total Submissions:752.1K
Contributor:LeetCode
Companies
googlefacebookbloomberglinkedin
Related Topics
mathbinary search
Similar Questions
Sqrt(x)