Pow(x, n)

Implement pow(x,?n).

?

按照定義做的O(n)肯定是TLE的。

利用這個信息：x²ⁿ = (xⁿ)²

有個注意點，當n為負是，直接取反是不可行的。

由于int的表示范圍是[2^-31, 2³¹-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 overflowreturn pow(x, n+1)/x;else{x = 1/x;n = -n;}}return Helper(x, n);}double Helper(double x, int n){//n > 0if(n == 0)return 1;double partRes = Helper(x, n>>1);if(n%2 == 1)return partRes*partRes*x;elsereturn partRes*partRes;} };

?

解法二：非遞歸

對于n的二進制表示，考慮每一位的0/1。

舉例n==5，二進制表示為101

右數第一位為1，需要乘以x

右數第二位為0，不需要乘以x²

右數第三位為1，需要乘以x⁴

class Solution { public:double pow(double x, int n) {if(n == 0)return 1;int sign = 1; if(n == INT_MIN)return pow(x, n+1) / x;else if(n < 0){sign *= -1;n *= -1;}double ret = 1;double mul = x;while(n){if(n & 1)ret *= mul;n >>= 1;mul *= mul;}if(sign == 1)return ret;elsereturn 1 / ret;} };

?

解法三：just a joke

class Solution { public:double pow(double x, int n) {return std::pow(x,n);} };

轉載于:https://www.cnblogs.com/ganganloveu/p/4161167.html

總結

以上是生活随笔為你收集整理的【LeetCode】50. Pow(x, n) (3 solutions)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。