剑指 Offer 16 数值的整数次方

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-23 10:06:46
    编辑于：2022-02-23 10:19:45
    浏览量：948

概述

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

https://leetcode.com/problems/powx-n/

注意为负数的情况哦。

二分法快速求幂（递归法）

要注意，输入范围为整型的范围：-2^31 <= n <= 2^31-1

所以当输入为 -2^31 时，对其取反将导致 int 溢出。

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        bool isNegative = n < 0;
        long n2 = n;
        if (isNegative) n2 *= -1;
        double ans = helper(x, n2);
        if (isNegative) ans = 1 / ans;
        return ans;
    }
    
    double helper(double x, long n) {
        if (n == 1) return x;
        int rem = n % 2;
        n /= 2;
        double ans = helper(x, n);
        ans *= ans;
        if (rem) ans *= x;
        return ans;
    }
};

Links: sword-offer-16