剑指 Offer 16 数值的整数次方

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

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/