第 16 题：数值的整数次方（快速幂）
传送门：AcWing：数值的整数次方，牛客网 online judge 地址。
实现函数double Power(double base, int exponent)，求base的 exponent次方。
不得使用库函数，同时不需要考虑大数问题。
注意：
- 不会出现底数和指数同为 0 的情况
样例1：
输入：10 ，2
输出：100
样例2：
输入：10 ，-2
输出：0.01
分析：数值的整数次方，要处理一些细节问题，加法变成乘法。考虑底数为 的时候，指数不能为负数。
思路1：使用递归
Python 代码：
class Solution(object):
def Power(self, base, exponent):
"""
:type base: float
:type exponent: int
:rtype: float
"""
if exponent == 0:
return 1
if exponent < 0:
return 1 / self.Power(base, -exponent)
# 如果是奇数
if exponent & 1:
return base * self.Power(base, exponent - 1)
return self.Power(base * base, exponent >> 1)
思路2：非递归的写法，把 exponent 想象成二进制。
Python 代码：在理解的基础上记住这个写法
class Solution(object):
def Power(self, base, exponent):
"""
:type base: float
:type exponent: int
:rtype: float
"""
if exponent < 0:
base = 1 / base
# 负数变成正数
exponent = -exponent
res = 1
while exponent:
if exponent & 1:
res *= base
base *= base
exponent >>= 1
return res
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent 。求 base 的 exponent 次方。
求解思路与关键
-
注意分类讨论与与递归函数的设计。
-
关键：将循环变成递归操作，每次折半求值，避免死板做循环，这种感觉像加法变乘法。
-
注意细节：底数为 0 的时候，指数为负数是没有意义的
-
精确计算，转成浮点数 0.125：
System.out.println((double) 1 / 8);
- 右移 1 位运算等价于“除以 2”：
// exponent 指数，exponent >> 1 表示将指数除以 2
System.out.println(exponent >> 1);
- 使用位运算的 与 运算符代替了求余数运算，来判断一个数是奇数还是偶数：
if ((exponent & 1) == 0) {
Java 代码：
public class Solution {
public double Power(double base, int exponent) {
// 先把极端情况考虑到
// 不能用 == 比较两个浮点数是否相等，因为有误差
if (equals(base, 0) && exponent < 0) {
throw new IllegalArgumentException("当底数为 0 的时候，指数为负数没有意义");
}
if (exponent == 0) {
return 1.0;
}
// 下面将指数的两种情况合并成一种情况考虑
if (exponent > 0) {
return power(base, exponent);
} else {
return power(1 / base, -exponent);
}
}
public double power(double base, int exponent) {
if (exponent == 0) {
return 1.0;
}
if (exponent % 2 == 0) {
double square = power(base, exponent / 2);
return square * square;
} else {
double square = power(base, (exponent - 1) / 2);
return square * square * base;
}
}
private boolean equals(double num1, double num2) {
return num1 - num2 < 0.000001 && num1 - num2 > -0.000001;
}
}
Java 代码：
public class Solution {
public double Power(double base, int exponent) {
if (exponent == 0) {
return 1;
}
if (exponent < 0) {
return 1 / Power(base, -exponent);
}
// 使用位运算的 与 运算符代替了求余数运算，来判断一个数是奇数还是偶数
if ((exponent & 1) == 0) {
double square = Power(base, exponent >> 1);
return square * square;
} else {
double square = Power(base, (exponent - 1) >> 1);
return square * square * base;
}
}
public static void main(String[] args) {
int base = 3;
int exponent = -3;
Solution solution = new Solution();
double result1 = solution.Power(base, exponent);
System.out.println(result1);
exponent = 6;
double result2 = solution.Power(base, exponent);
System.out.println(result2);
// exponent 指数，exponent >> 1 表示将指数除以 2
System.out.println(exponent >> 1);
}
}
LeetCode 第 50 题：)
传送门：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] 。
思路1：使用循环，把指数 想成二进制
Python 代码：
class Solution:
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
x = 1 / x
n = - n
res = 1
while n:
if n & 1 == 1:
res *= x
# 注意：这里不要写成 res *= res
x *= x
n >>= 1
return res
思路2：将循环变成递归操作，每次折半求值，避免死板做循环，这种感觉像加法变乘法。（脑子里回忆公式）。注意细节：底数为 的时候，指数为负数是没有意义的。
Python 代码：递归写法：注意边界条件
class Solution:
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
# 对 x = 0 ， n < 0 还要做特判
if n == 0:
return 1
if n < 0:
return 1 / self.myPow(x, -n)
if n & 1:
return x * self.myPow(x, n - 1)
return self.myPow(x * x, n // 2)
基本的写法：
https://blog.csdn.net/happyaaaaaaaaaaa/article/details/76552127
《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂）-1
模板写法1：
《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂）-2
模板写法2：
《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂）-3
网友评论