【leetcode】剑指 Offer 16. 数值的整数次方（shu-zhi-de-zheng-shu-ci-fang-lcof）（快速幂）[中等]

链接

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

耗时

解题：6 min
题解：6 min

题意

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

提示：

• -100.0 < x < 100.0
• − 2 31 < = n < = 2 31 − 1 -2^{31} <= n <= 2^{31}-1 −231<=n<=231−1
• − 1 0 4 < = x n < = 1 0 4 -10^4 <= xn <= 10^4 −104<=xn<=104

思路

幂次可以为负的快速幂，特判一下就好了。

时间复杂度： O ( l o g n ) O(logn) O(logn)

AC代码

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 1 || n == 0) return 1;
        long long lln = n;
        bool isdiv = false;
        if(lln < 0) {
            isdiv = true;
            lln = -lln;
        }
        double ans = 1;
        while(lln) {
            if(lln&1) ans *= x;
            x *= x;
            lln >>= 1;
        }
        return isdiv ? 1/ans : ans;
    }
};