实现函数 double Power(double base, int exponent)，求base的exponent次方。
注意：
1.保证base和exponent不同时为0。
2.不得使用库函数，同时不需要考虑大数问题
3.有特殊判题，不用考虑小数点后面0的位数。
数据范围： 
， 
,保证最终结果一定满足 
进阶：空间复杂度%5C)
，时间复杂度 %5C)
进阶：空间复杂度
[编程题]数值的整数次方
public static double Power(double base, int exponent) {
//3个递归边界条件
if (exponent == 0) {
return 1;//如果次方是0，返回1, 0的0次方也是1
}
if (exponent == 1) {
return base;//如果次方是1，返回base
}
//这里要特别注意，对于次方为负数，exponent / 2的结果为 -1
if (exponent == -1) {
return 1 / base;
}
//递归
if (exponent % 2 == 0) {
//如果次方是偶数，比如2的4次方，直接算2的2次方 再算2的2次方乘2的2次方
double power = Power(base, exponent / 2);
return power * power;
} else {
//如果次方是奇数，比如2的5次方，先算2的3次方，再算2的2次方，最后乘起来
double power1 = Power(base, exponent / 2);
double power2 = Power(base, exponent - exponent / 2 );
return power1 * power2;
}
}
这段代码的时间复杂度是多少？有点人说O(logN),有的说O(n)，有大佬帮分析一下吗？
编辑于 2024-01-05 17:47:12
回复(0)
两种办法，一种分指数类型为正数，负数，和0直接计算，另一种利用分治法进行迭代，每次将计算分为两部分，一部分算完另一部分就不用计算，但是如果指数为奇数时是需要都计算的
import java.util.*;
public class Solution {
public double Power1(double base, int exponent) {
double num = base;
if (exponent > 0) {
for (int i = 0; i < exponent - 1; i++) {
base *= num;
}
} else if (exponent == 0) {
base = 1l;
} else {
for (int i = 0; i > exponent - 1; i--) {
base *= 1l / num;
}
}
return base;
}
public double Power(double base, int exponent) {
if (exponent == 0) {
return 1l;
}
if (exponent == 1) {
return base;
}
if (exponent == -1) {
return 1 / base;
}
if (exponent % 2 == 0) {
double power = Power(base, exponent / 2);
return power * power;
} else {
double power1 = Power(base, exponent / 2);
int addNum = 1;
if (exponent < 0) {
addNum = -1;
}
double power2 = Power(base, exponent / 2 + addNum);
return power1 * power2;
}
}
}
发表于 2023-09-03 14:47:16
回复(0)
public class Solution {
public double get(double base, int exponent) {
if(exponent==0)
return 1.0;
if(exponent==1)
return base;
//每一次向下取整
double ret=get(base,exponent/2);
if(exponent%2==0){
return ret*ret;
}else
return ret*ret*base;
}
public double Power(double base, int exponent) {
if(exponent<0)
return 1.0/get(base,exponent);
return get(base,exponent);
}
}
发表于 2022-11-20 14:10:52
回复(0)
public class Solution {
public double Power(double base, int exponent) {
if(exponent==0)return base*0+1;
if(base==0)return base*0;
if(exponent==1)return base;
if(exponent==-1)return 1/base;
if(exponent>0){
double temp=base;
while(exponent>1){
exponent--;
base*=temp;
}
return base;
}else{
double temp=1/base;
while(exponent<-1){
exponent++;
temp*=(1/base);
}
return temp;
}
}
}
发表于 2022-11-03 16:00:25
回复(0)
import java.util.*;
public class Solution {
public double Power(double base, int exponent) {
if(exponent == 0){
return (double)1;
}else if(exponent > 0){
return Math.pow(base,exponent);
}else{
base = 1.0 / base;
exponent = -exponent;
return base * Power(base,exponent - 1);
}
}
}
发表于 2022-08-25 12:01:12
回复(0)
import java.util.*;
public class Solution {
public double Power(double base, int exponent) {
if(exponent==0){
return 1.0;
}
if(base==0){
return 0;
}
int log=exponent;
exponent=Math.abs(exponent);
double result=1;
while(exponent>0){
if(exponent%2==1){
result*=base;
}
if(exponent%2==1){
exponent=(exponent-1)/2;
}else{
exponent/=2;
}
base*=base;
}
if(log<0){
return 1/result;
}
return result;
}
}
发表于 2022-08-02 19:04:16
回复(0)
关于快速幂，找到一篇讲解比较详细的博文：https://blog.csdn.net/qq_19782019/article/details/85621386，基础不太好的友友们可以看一下
发表于 2022-06-05 12:17:58
回复(0)
public class Solution {
public double Power(double a, int b) {
double ret = a;
if(b<0) {
a = 1/a;
b = -b;
while(b - 1!=0) {
a = a*(1/ret);
b--;
}
} else if(b > 0) {
while(b - 1!=0) {
a = a * ret;
b--;
}
}else {
return 1;
}
return a;
}
}
发表于 2022-05-31 18:04:29
回复(0)
为啥你们写那么多？这道题有什么的吗
public class Solution {
public double Power(double base, int exponent) {
if(exponent==0)return (double)1;
else if(exponent>0)return base * Power(base, exponent-1);
else {
base = 1/base;
exponent = -exponent;
return base * Power(base, exponent-1);
}
}
}
发表于 2022-04-01 16:30:53
回复(0)
public class Solution {
public double Power(double base, int exponent) {
if (exponent == 0)
return 1.0;
double res = 1.0;
if (exponent < 0) {
res = 1 / res;
base = 1 / base;
exponent = -exponent;
}
double b = base;
//把指数转化为二进制
while (exponent > 0) {
//看其二进制哪位上有1
if ((exponent & 1) != 0)
res *= b;
//看当前遍历到2的几次方了
b *= b;
//算过了就淘汰掉
exponent >>= 1;
}
return res;
}
}
发表于 2022-01-09 22:15:24
回复(0)
public double Power(double base, int exponent) {
if(base == 0){
return 0;
}
if(exponent == 0){
return 1;
}
double v = 1;
int count = Math.abs(exponent);
if(exponent>0){
while(count > 0){
count--;
v *= base;
}
}else{
while(count>0){
count--;
v /= base;
}
}
return v;
}
if(base == 0){
return 0;
}
if(exponent == 0){
return 1;
}
double v = 1;
int count = Math.abs(exponent);
if(exponent>0){
while(count > 0){
count--;
v *= base;
}
}else{
while(count>0){
count--;
v /= base;
}
}
return v;
}
发表于 2021-12-13 08:07:00
回复(0)
public class Solution {
public double Power(double base, int exponent) {
// if (base==0&&exponent==0)return 0d;
if (exponent==0||base==1)return 1.0d;
if (base==0)return 0d;
if (exponent==1)return base;
double ret = 1d;
while (exponent>0){
if((exponent&1)==1)ret*=base;
base*=base;
exponent>>=1;
}
while (exponent<0){
if((-exponent&1)==1)ret*=1/base;
base*=base;
exponent=-((-exponent)>>1);
}
return ret;
}
}
public double Power(double base, int exponent) {
// if (base==0&&exponent==0)return 0d;
if (exponent==0||base==1)return 1.0d;
if (base==0)return 0d;
if (exponent==1)return base;
double ret = 1d;
while (exponent>0){
if((exponent&1)==1)ret*=base;
base*=base;
exponent>>=1;
}
while (exponent<0){
if((-exponent&1)==1)ret*=1/base;
base*=base;
exponent=-((-exponent)>>1);
}
return ret;
}
}
发表于 2021-11-14 16:10:01
回复(0)
不能使用库函数的话。
使用循环计算指数幂，设置一个flag表示幂的正负。幂正返回结果，幂负返回结果的倒数。
public class Solution {
public double Power(double base, int exponent) {
if(base==(double)0)return 0;
double res=1;
int flag=0;
if(exponent<0){
flag =1;
exponent = -exponent;
}
for(int i=0;i<exponent;++i){
res = base*res;
}
if(flag==0)
return res;
else return 1/res;
}
}
发表于 2021-09-21 11:16:47
回复(0)
自己写的，看了一下，超过了96的用户，所以发一下。思路比较简单，看代码应该可以看懂吧 ，就不解释了，希望对你有帮助，谢谢
public class Solution {
public double Power(double base, int exponent) {if(exponent>=0){
if(exponent==9){
return 0;
}
if(exponent==1){
return base;
}
if(exponent==2){
return base*base;
}
return Power(base,exponent-1)*base;
}else{
if(exponent==-1){
return 1.0/base;
}
if(exponent==-2){
return 1.0/(base*base);
}
return Power(base,-1) * Power(base,exponent+1);
}
}
}
发表于 2021-09-11 16:20:38
回复(0)
public class Solution {
public double Power(double base, int exponent) {
if(base==0){
return 0;
}
if(exponent==0){
return 1;
}
return getResult(base,exponent);
}
private double getResult(double base,int power){
double result = 0d;
if(power>0){
result = base;
for(int i =1;i<power;++i){
result *=base;
}
}else{
result = 1;
for(int i =0;i<-power;++i){
result = result/base;
}
}
return result;
}
}
public double Power(double base, int exponent) {
if(base==0){
return 0;
}
if(exponent==0){
return 1;
}
return getResult(base,exponent);
}
private double getResult(double base,int power){
double result = 0d;
if(power>0){
result = base;
for(int i =1;i<power;++i){
result *=base;
}
}else{
result = 1;
for(int i =0;i<-power;++i){
result = result/base;
}
}
return result;
}
}
发表于 2021-09-07 22:06:06
回复(0)
//老递归家了
public class Solution {
public double Power(double base, int exponent) {if(exponent==0){
return 1;
}
int realex = Math.abs(exponent);
double[] dp = new double[realex+1];
dp[0]=1;
if(exponent>0){
dp[1]=base;
}else{
dp[1]=1.0/base;
}
dfs(dp[1],realex,dp);
return dp[realex];
}
public void dfs(double base,int exponent,double[] dp ){
if(exponent<=1){
return ;
}
int mid = exponent>>1;
dfs(base,mid,dp);
if(exponent%2==0){
dp[exponent] = dp[mid]*dp[mid];
}else{
dp[exponent] = dp[mid]*dp[mid]*base;
}
}
}
发表于 2021-08-24 14:39:45
回复(0)
直接相乘，但是需要注意 exponent 的正负
如果为正，没事
如果为正，没事
如果为负，可以考虑把 base 变成 1/base (把负号拿下来)
此时注意 base 不能为0
判断 double 是否为 0:
不使用 api 判断，这里可以根据一个概念入手：
两数相等概念：如果两个数相差小于 0.000001 则认为两数相等
public class Solution {
public double Power(double base, int exponent) {
if(base-0.0<0.000001 && base-0.0>-0.000001){
return 0;
}
double ans = 1;
if(exponent<0) {
base = 1/base;
exponent = -1*exponent;
}
while (exponent > 0) {
ans = ans * base;
exponent--;
}
return ans;
}
}
发表于 2021-08-23 17:06:29
回复(0)
想知道为哈不直接算呢？
public class Solution {
public double Power(double base, int exponent) {
if(exponent==0)
return 1;
if(exponent<0){
base = 1/base;
exponent = -1*exponent;
}
double temp = base;
for(int i = 1;i<exponent;i++){
base = base*temp;
}
return base;
}
}
发表于 2021-08-22 22:54:13
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
/** * 1.全面考察指数的正负、底数是否为零等情况。 * 2.写出指数的二进制表达，例如13表达为二进制1101。 * 3.举例:10^1101 = 10^0001*10^0100*10^1000。 * 4.通过&1和>>1来逐位读取1101，为1时将该位代表的乘数累乘到最终结果。 */ public double Power(double base, int n) { double res = 1,curr = base; int exponent; if(n>0){ exponent = n; }else if(n<0){ if(base==0) throw new RuntimeException("分母不能为0"); exponent = -n; }else{// n==0 return 1;// 0的0次方 } while(exponent!=0){ if((exponent&1)==1) res*=curr; curr*=curr;// 翻倍 exponent>>=1;// 右移一位 } return n>=0?res:(1/res); }