首页 > 代码库 > [LeetCode] Pow(x,n)
[LeetCode] Pow(x,n)
Implement pow(x, n).
思路：像string to integer一样。考虑的细节较多。
1.测试用例要考虑基数和指数都为正数、负数和零的情况。
2.注意0的0次方在数学上没有意义。
3.用位运算代替乘除和求余优化效率：移位代替除法（n>>1 == n /2);用位与代替求余判定奇偶（if (n& 0x1 == 1) == if(n % 2 == 1))
4.对于n取值INT_MIN = -2147483648时，-n依然是INT_MIN，并不是INT_MAX=2147483647，这时需要格外小心。
时间复杂度O(lgN),空间复杂度O(1)
1 class Solution { 2 public: 3 double pow(double x, int n) { 4 if (n == 0) 5 return 1; 6 if (n < 0) { 7 if (n == INT_MIN) { 8 return 1.0 / (pow(x, INT_MAX) * x); 9 } else {10 return 1.0 / pow(x, -n);11 }12 }13 14 double result = pow(x, n>>1);15 if (n & 0x1 == 1) {16 return result * result * x;17 } else {18 return result * result;19 }20 }21 };
这是一种STL的写法，来自http://blog.csdn.net/fengbingyang/article/details/12236121
class Solution { public: double pow(double x, int n) { // Start typing your C/C++ solution below // DO NOT write int main() function if(n<0) { if(n==INT_MIN) return 1.0 / (pow(x,INT_MAX)*x); else return 1.0 / pow(x,-n); } if(n==0) return 1.0; double ans = 1.0 ; for(;n>0; x *= x, n>>=1) { if(n&1>0) ans *= x; } return ans; } };
还有一位大牛的方法，来自http://blog.csdn.net/sunbaigui/article/details/8981241
class Solution { //divide-and-conquer //classic public: double pow(double x, int n) { if (n == 0) return 1.0; // Compute x^{n/2} and store the result into a temporary // variable to avoid unnecessary computing double half = pow(x, n / 2); if (n % 2 == 0) return half * half; else if (n > 0) return half * half * x; else return half * half / x; } };
[LeetCode] Pow(x,n)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。