Leetcode-50.Pow(x,n)

发表于 分类于 阅读次数：

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：快速幂（递归）

借鉴：leetcode官方

假设我们已经得到了$x^n$,我们如何得 $x^{2n}$呢？很明显我们不需要再将x再乘n次，我们直接使用$(x^n)^2=x^{2n}$,通过一次计算，我们就得到了结果值

同样对于$x^n$我们可以通过求$x^{n/2}$（A）来得到$x^n$我们可以根据n的奇偶性来分别讨论$x^n$的值。如果n为偶，那么$(x^n)^2=x^{2n}$来得到$x^n$=A*A如果n为奇数那么$x^n$= A * A *x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double fastPow(double x, long long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
};

解法2：快速幂（循环）

使用公式$x^{a+b}=x^a+x^b$我们可以将n看做一系列正整数之和，即n=$b_1+b_2+b_3+……+b_n$那么到底将n分成那些数的和呢，我们可以以x的10次方为例，10的二进制为1010，然后把它展成2的幂次的和。

$x^{10}=x^{(1010)_2}=x^{12^3+02^2+12^1+02^0}$即$x^{10}=x^{2^3}*x^{2^1}$

同时10的二进制数 在 3 1 位置为1 也就是说我们把1位置对应的项累乘就能得到结果，

那么累成的项，我们可以发现前一项是后一项的自乘，即$x^8=x^4*x^4$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    double myPow(double x, int n) {
        long long N=n;
        if(N<0)
        {
            N=-N;
            x=1/x;
        }
        double res=1;
        while(N)
        {
            if(N&1)
                res*=x;
            x*=x;
            N>>=1;
        }
        return res;
    }
};