【【LeetCode-Java实现】50. Pow(x, n)求x的n次幂】
50. Pow(x, n）求x的n次幂
- 题目描述
- 思路
- 实现
题目描述 Implement pow(x, n), which calculates x raised to the power n (xn).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [?231, 231 ? 1]
实现求x的n次幂的函数
思路
- 暴力循环法，但是超时
x的n次幂即n个x相乘
（前提是n为正数，所以对于负数n，需要稍加改造，将n的负号放到x上） - 分治法
把n次幂分成两份：即xn=xn/2 *xn/2
比如：28.=24. 24
需要注意的是解决n的奇偶问题和正负问题
定义个临时变量temp用来存储n次幂的一半:temp=myPow(x,n/2)
如果n为偶数：直接返回 temp * temp
如果n为奇数：需要在temptemp基础上再来一个x，此时多出来的这个次方的正负需要单独讨论：
（1）若n是正数，直接乘上一个x即可
（2）若n是负数，把负号移到x上，即除以一个x
- 暴力循环（超时，没通过）
public double myPow(double x, int n) {
//直接暴力求解，x的n次幂即n个x相乘（前提是n为正数，所以对于负数n，需要稍加改造）
if(n<0){ //若n未负数，把负号放到x里，即x变成1/x
x=1/x;
n=-n;
}double res=1;
//x的n次幂的结果
for(int i=0;
i- 分治法
public double myPow(double x, int n) {
//分治法，把次幂分为两半//边界情况
if(n==0) return 1;
double temp=x;
temp=myPow(x,n/2);
//temp为次幂的一半
//解决n的奇偶问题
//n若是偶数，直接两份temp相乘即可
if(n%2==0){
return temp*temp;
}
//n若是奇数，两份temp相乘之后，还差一个x
else{
//解决n正负问题
if(n>0){
return temp*temp*x;
}
else{
return temp*temp/x;
}
}
}
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)