106.Pow(x, n)
题目
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数。
示例 1：
- 输入：x = 2.00000, n = 10
- 输出：1024.00000
示例 2：
- 输入：x = 2.10000, n = 3
- 输出：9.26100
示例 3：
- 输入：x = 2.00000, n = -2
- 输出：0.25000
思路
阶乘就是要拿n个x来连乘。
但我们不一个一个的乘，而是把他们成倍成倍的叠起来。
比如算 3^13。
如果硬算，就是：
3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3
太慢了。
我们换个办法：
- 3^1 = 3
- 3^2 = 3 × 3 = 9
- 3^4 = 9 × 9 = 81
- 3^8 = 81 × 81 = 6561
你看出来了吧，每次都把前面的结果自己乘自己，指数就翻倍了。
所以：
- 1 变 2
- 2 变 4
- 4 变 8
- 8 变 16
然后看 13 需要哪几块：
13 = 8 + 4 + 1
所以：
3^13 = 3^8 × 3^4 × 3^1
也就是说，不是每一层都要用，只把需要的那几层拿出来乘。
为什么要 while (n > 0)
因为我们要一直把 n 拆下去，直到拆没了。
每次都做这三件事：
- 如果 n 是奇数，说明当前这一层要用，先乘进答案
- 把底数自己乘自己，下一层就翻倍了
- 把 n 除以 2，继续看下一层
等 n = 0 了，就说明没有层可以拆了，结束。
为什么奇数要乘进答案 因为奇数说明这一层“多出来一份”。 比如： - 13 可以拆成 8 + 4 + 1 - 最后那个 1 就表示当前这一层要拿一次 所以只要看到 n 是奇数，就把当前 base 乘进结果。
class Solution {
fun myPow(x: Double, n: Int): Double {
// 用 Long 存指数，避免 n = Int.MIN_VALUE 时取反溢出
var exp = n.toLong()
// 当前要不断“翻倍”的底数
var base = x
// 最终答案，先设成 1，因为 1 乘任何数都不影响结果
var result = 1.0
// 如果指数是负数，先把问题变成正数指数
// 例如 x^-2 = (1 / x)^2
if (exp < 0) {
base = 1.0 / base
exp = -exp
}
// 只要指数还没变成 0，就继续拆
while (exp > 0) {
// 如果当前指数是奇数，
// 说明这一层的 base 要算进结果里
if (exp % 2L == 1L) {
result *= base
}
// 底数自己乘自己，进入下一层
// 3 -> 9 -> 81 -> 6561 ...
base *= base
// 指数减半
exp /= 2
}
return result
}
}
复杂度
- 时间复杂度: n 每次砍半，所以是 O(log n)
- 空间复杂度: 只用几个变量，所以是 O(1)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!