首页 > 代码库 > 【LeetCode】Pow(x, n) (2 solutions)
【LeetCode】Pow(x, n) (2 solutions)
Pow(x, n)
Implement pow(x, n).
按照定义做的O(n)肯定是TLE的。
利用这个信息：x2n = (xn)2
有个主意点，当n为负是，直接取反是不可行的。
由于int的表示范围是[2-31, 231-1]，当n为INT_MIN时，取反会溢出。
因此需要对n==INT_MIN单独考虑。
另外，除以2可以用右移1位来实现。
解法一：递归
class Solution {public: double pow(double x, int n) { if(n < 0) { if(n == INT_MIN) //-INT_MIN will cause overflow return pow(x, n+1)/x; else { x = 1/x; n = -n; } } return Helper(x, n); } double Helper(double x, int n) {//n > 0 if(n == 0) return 1; double partRes = Helper(x, n>>1); if(n%2 == 1) return partRes*partRes*x; else return partRes*partRes; }};
解法二：非递归
对于n的二进制表示，考虑每一位的0/1。
举例n==5，二进制表示为101
右数第一位为1，需要乘以x
右数第二位为0，不需要乘以x2
右数第三位为1，需要乘以x4
class Solution {public: double pow(double x, int n) { if(n < 0) { if(n == INT_MIN) //-INT_MIN will cause overflow return pow(x, n+1)/x; else { x = 1/x; n = -n; } } return Helper(x, n); } double Helper(double x, int n) {//n > 0 if(n == 0) return 1; double Res = 1; double cur = x; while(n) { if(n%2 == 1) Res *= cur; cur *= cur; n >>= 1; } return Res; }};
【LeetCode】Pow(x, n) (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。