50. Pow(x, n)
50. Pow(x, n)
一、题目描述:
实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。 示例 1: 输入:x = 2.00000, n = 10 输出:1024.00000 示例 2: 输入:x = 2.10000, n = 3 输出:9.26100 示例 3: 输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25 提示: -100.0 < x < 100.0 -2^31 <= n <= 2^31-1 -10^4 <= xn <= 10^4 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/powx-n 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、思路分析:
这道题考察了什么思想?你的思路是什么?
说到求幂函数,我不得不说一下快速幂了,快速幂的递归版本还是比较好理解的,我们先来讲一下快速幂吧,快速幂的本质是分治算法,比如我们要计算x^8:
可以有: x -> x^2 -> x^4-> x^8
我们只需将上一次结果进行平方,进行3次即可得到x^8。
而如果我们想求x^19,可以有:
x -> x^2 -> x^4 -> x^9 -> x^19
因为我们需要从右到左进行推理,所以可以用到递归的思想。
当我们计算x^19时,先计算y = x[n/2],[a]表示向下取整。如果n为偶数,那么上一个数的平方为xn,如果n为奇数,那么上一个数的平方再乘x为x^n。
做题的时候是不是一次通过的,遇到了什么问题,需要注意什么细节?
不是一次通过的,边界条件没有处理好,也就是递归出口刚开始没有搞好。
有几种解法,哪种解法时间复杂度最低,哪种解法空间复杂度最低,最优解法是什么?其他人的题解是什么,谁的效率更好一些?用不同语言实现的话,哪个语言速度最快?
class Solution {
public double myPow(double x, int n) {
double res = 1.0;
for(int i = n; i != 0; i /= 2){
if(i % 2 != 0){
res *= x;
}
x *= x;
}
return n < 0 ? 1 / res : res;
}
}
三、AC 代码:
func myPow(x float64, n int) float64 {
if n >= 0 {
return Mul(x, n)
}
return 1.0 / Mul(x, -n)
}
func Mul(x float64, n int) (res float64) {
if n == 0 {
return 1
}
y := Mul(x, n/2)
if n%2 == 0 {
res = y * y
return
}
res = y * y * x
return
}
四、总结:
其实AC代码用到的快速幂方法还有非递归方法,即用迭代方法。那样空间复杂度也能减小到O(1)。
相关文章
- 数据孤岛是业务效率的无声杀手
- 2023展望:新的一年将给大数据分析领域带来什么?
- 阿里云ADB基于Hudi构建Lakehouse的实践
- 大数据在医疗保健领域的使用案例
- 微软增加说明:KB5021751 更新扫描已经 / 即将过时 Office 过程中不会触碰用户隐私
- 2022 Gartner全球云数据库管理系统魔力象限发布 腾讯云数据库入选
- 场景化、重实操,分享一个实时数仓实践案例
- Arctic的湖仓一体践行之路
- 分布式计算MapReduce究竟是怎么一回事?
- 淘系数据模型治理优秀实践
- 大数据分析对医疗保健的影响
- 当我们说大数据Hadoop,究竟在说什么?
- 2022年及以后大数据的五个发展趋势
- 网易严选离线数仓治理实践
- 2023 年数据治理趋势
- 一份“靠谱”的年度经营计划,你学会了吗?
- 漫谈对大数据的思考
- 测试一下,读懂数据的能力,你有吗?
- 用艺术的眼光探索数据之美
- 聊聊数据分析成果如何落地