☆打卡算法☆LeetCode 50、Pow(x, n) 算法解析
☆打卡算法☆LeetCode 50、Pow(x, n) 算法解析
恬静的小魔龙
发布于 2022-08-07 10:03:12
发布于 2022-08-07 10:03:12
一、题目
1、算法题目
“实现函数，计算x的n次幂。”
题目链接：
来源：力扣（LeetCode）
链接：50. Pow(x, n) - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入： x = 2.00000, n = 10
输出： 1024.00000示例 2：
输入： x = 2.10000, n = 3
输出： 9.26100二、解题
1、思路分析
这道题可以使用快速幂+递归的方法解题。
快速幂算法，本质就是分治算法，将大问题分解成小问题，然后递归解决。
快速幂算法：
比如要计算x8，可以按照x → x2 → x4 → x8的顺序，从x开始，每次将上一次的结果进行平方，3次后就可以得到x8的结果，而不需要对x乘8次x。
如果幂是偶数，比如x9，可以按照x → x2 → x4 → x9的顺序，这些步骤中，还是按照将上一次结果平方，而在x4 → x9的步骤中，需要将上一个结果进行平方，还需要额外乘一个x。
综上所述，可以推到出规律，如果要计算xn，首先判断n的奇偶：
- n为偶数，那么xn=yn
- n为奇数，那么xn=yn * x
接着就可以递归地得到结果了。
2、代码实现
代码参考：
public class Solution {
//递归
public double MyPow(double x, int n) {
return (n >= 0) ? res(x, n) : 1 / res(x, n);
}
private double res(double x, int n)
{
if(n == 0)
return 1;
double y = res(x, n / 2);
return (n % 2 == 0) ? y * y :y * y * x;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(log n)
其中n为遍历的层数。
空间复杂度： O(log n)
其中n为遍历的层数。
三、总结
这道题还有更秀的一行解题法：
public class Solution {
public double MyPow(double x, int n) {
return Math.Pow(x,n);
}
}是不是秀的头皮发麻。。。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-11-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录