LeetCode 50 Pow(x, n)

Ciel Yang 收录于类别练习 OJ解题报告

2020-05-11 2023-04-21 约 1031 字预计阅读 3 分钟

本题是经典的快速幂问题，要熟悉解题算法的思想，方便以之位原型和模板处理更复杂的问题。

题目描述

原题链接如下： LeetCode 50 Pow(x, n)

题目大意

用尽量快的办法求出浮点数的整数幂，指数可以位负数。

输入与输出

示例输入：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Input 1:
x = 2.0
n = 10

Input 2:
x = 2.1
n = 3

Input 3:
x = 2.0
n = -2

示例输出：

1
2
3
4
5
6
7
8
Output 1:
1024.0

Output 2:
9.261

Output 3:
0.25

解题思路

本题的递归解法很好想，但是，如果要用迭代方式解答此问题就要格外注意算法的设计。当然，不论递归还是迭代实际都暗含了分治法的思想，只不过迭代法是自底向上的分治法，不太直观罢了。

解法一：递归

可以根据乘方运算的数学性质不断把指数除以 2 得到子问题，然后把子问题的解平方即可得到原题的解。只需要注意一些边界情况：

指数是负数时，把指数转化为它的绝对值，最后结果取倒数即可
指数时奇数时，先提前一个底数 x，即 $x^n = x \times x^{n-1}$
指数或底数为 0 或 1 时，可以剪枝

解法二：迭代

如果机械地把递归法翻译位迭代法，算法可能会难以理解，不如深究分治法的原理，进行逆向思维。

迭代法的核心思想就是把整数指数转化为二进制形式，然后把二进制数字拆解为多项式形式，即:

$$n = \sum_{i=0}^{k} {a_i \cdot 2^i},\quad {a_i \in {\lbrace 0,\ 1 \rbrace}}$$

那么原来的幂函数求解就能转化为如下形式：

$$x^n = \prod_{i=0}^{k} {(x^{2^i})^{a_i}}$$

表面上看，我们把问题复杂化了，其实不然：

$x^{2^i}$ 其实很容易求解，只要不断自乘即可
而 $a_i$ 则就是指数的二进制串的各位上的内容，只可能为 0 或 1

那么，迭代方法的正整数指数快速幂运算如下：

指数转化为二进制串
求解数列 $x^{2^i}$ 的各项值，数列项数就是 1 中得到的二进制串的长度
2 中的数列由低到高对应 1 中二进制串，如果某个位是 1 代表结果包含这个数列项，是 0 则代表不包含
把所有 3 中包含的数列项相乘即可得到原题答案

最后，我们从头总览迭代法也不难发现：步骤 2 中求解数列的各项值的过程其实就是递归法求子问题的逆向过程。

实际编程过程中，我们无需把进制转换过程和数列求解过程分开，更无需进行进制转换，只需要不断使用右移运算即可得到二进制串各个位的内容。而且右移运算是从低到高得到各位的内容，正好匹配数列的各项数值，可以使得数列从 x 开始自乘，方便计算。

代码

解法一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    fun myPow(x: Double, n: Int): Double {
        if (x == 0.0) return 0.0
        if (x == 1.0) return 1.0
        return if (n > 0) helper(x, n) else helper(1.0 / x, -n)
    }

    private fun helper(x: Double, n: Int): Double {
        if (n == 0) return 1.0
        if (n == 1) return x
        val tmp = helper(x, n / 2)
        return if (n and 1 == 1) tmp * tmp * x else tmp * tmp
    }
}

解法二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import kotlin.math.abs

class Solution {
    fun myPow(x: Double, n: Int): Double {
        var tn = abs(n.toLong())
        var tx = if (n < 0) 1.0 / x else x
        var re = 1.0
        while (tn != 0L) {
            if (tn and 1 == 1L) re *= tx
            tx *= tx
            tn = tn ushr 1
        }
        return re
    }
}

目录