Leetcode 50. Pow(x, n)

题目

Leetcode 50. Pow(x, n)

代码（9.19 首刷看解析）

快速幂

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0)
            return 1;
        if(n == 1)
            return x;
        if(n == INT_MIN) {  // 避免-n整形溢出
            return myPow(1/x, -(n+1))/x;
        }
        if(n < 0) {
            return myPow(1/x, -n);
        }
        if(n % 2) {
            return (x*myPow(x, n-1));
        } else {
            double sub = myPow(x, n/2);
            return (sub*sub);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

另一种解法

class Solution {
public:
    double myPow(double x, int n) {
        if(n == INT_MIN) {  // 避免-n整形溢出
            return myPow(1/x, -(n+1))/x;
        }
        if(n < 0) {
            return myPow(1/x, -n);
        }
        double ans = 1, tmp = x;
        while(n != 0) {
            if(n & 1 != 0) {
                ans = ans*tmp;
            }
            n>>=1;
            tmp = tmp*tmp;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20