首页 > 代码库 > 【Leetcode长征系列】Pow(x, n)
【Leetcode长征系列】Pow(x, n)
原题:
Implement pow(x, n).
思路:递归计算pow。
class Solution { public: double pow(double x, int n) { long long int mid = n/2; int d = n%2; if(n==0) return 1; if(n==1) return x; if(d==1) return pow(x, (n/2)+1) * pow(x, n/2); else return pow(x, n/2) * pow(x, n/2); } };
边界值处超时。
int -2147483648 ~ +2147483647 (4 Bytes)
class Solution { public: double pow(double x, int n) { long long num = n; if(num==0) return 1.0; if(num==1) return x; if(num<0) return 1.0/pow(x, -num); double half = pow(x,num>>1); if(num%2==0) return half*half; else return half*half*x; } };此时n若为负值,取负后即溢出。RE
class Solution { public: double pow(double x, int n) { if(n==0) return 1.0; if(n==1) return x; if(n<0 && n!=INT_MIN) return 1.0/pow(x, -n); if(n==INT_MIN) return 1.0/(pow(x, INT_MAX)*x); double half = pow(x,n>>1); if(n%2==0) return half*half; else return half*half*x; } };要考虑到最小的INT_MIN,即-2147483648取负会溢出,所以需要特殊处理。
AC
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。