实现阶乘__牛客网

Kanarien

/**
* 求x的n次幂
*
* 思路：
* 题目当然不会是一个简单的循环就能AC的，
* 首先要注意符号的问题，负数n次幂要取倒数，
* 其次是时间复杂度的问题，
* 可通过设置一个中间变量tmp记录平方值，来折半计算，
* 将O(n)降为O(logn)
* 当指数为偶数时，直接 tmp *= tmp 即可，
* 当指数为奇数时，除了tmp *= tmp 外， 结果还要乘上自己一次
*
* 下面的实现使用迭代，不使用递归
**/
public class Solution {
    public double pow(double x, int n) {
        double res = 1.0;
        double tmp = x;
        for (int i = n; i != 0; i /= 2) {
            if (i % 2 != 0) {
                res *= tmp;
            }
            tmp *= tmp;
        }
        return n > 0 ? res : 1 / res;
    }
}

发表于 2018-11-05 22:03:52 回复(0)

丶沉梦昂志

public class Solution {
    public double pow(double x, int n) {
        long ln = n;//使用int会溢出
        if (ln < 0)
            ln = -ln;
        double temp = x;
        long index = 1;//使用int会溢出
        while (index < ln) {
            x *= x;
            index *= 2;
        }
        while (index > ln) {
            x /= temp;
            index--;
        }
        while (index < ln) {
            x *= temp;
            index++;
        }
        if (n < 0)
            return 1 / x;
        else
            return x;
    }
}

发表于 2017-11-21 22:05:36 回复(1)

JacobGo！

public class Solution {
    public double pow(double x, int n) {
		if(x==0)
			return 0;
		if(n<0)
			return 1/power(x,-n);
		else
			return power(x,n);
	}
	
	private double power(double x, int n) {
		if(n==0)
			return 1;
		double half=power(x,n/2);
		if(n%2==0)
			return half*half;
		else
			return half*half*x;
	}
}

发表于 2017-07-30 11:03:10 回复(0)

Terence_Ge

AC:
class Solution {
public:
    double pow(double x, int n) {
        if(x == 0 && n == 0) return 1;
        if(x == 0) return 0;
        if(n == 0) return 1;
        if(n < 0){
            return 1/x * pow(1/x, -(n+1));
        }
        // n < 32 直接求解，要不然会递归太深，真是醉了。。。
        if(n < 32){
            double tmp = 1;
            for(int i = 0; i < n; i++){
                tmp = tmp * x;                
            }
            return tmp;
        }
        double tmp = pow(x, n/2);
        if(n % 2 == 1) return tmp * tmp *x;
        return tmp * tmp;
        
    }
};

发表于 2016-04-29 19:26:27 回复(3)

Java

詆調壹點

public class Solution {
    public static double pow(double x, int n) {
		if(n == 0) return 1;
		if(n < 0) return 1 / x * pow(1 / x, - (n + 1));
		if(n % 2 == 0) return pow(x * x, n / 2);
		else return pow(x * x, n / 2) * x;
	}
}

发表于 2017-03-25 22:28:31 回复(5)

可乐猪

class Solution {
public:
    double pow(double x, int n) {
        //求 x^n = x^(n/2) + x^(n/2) + x^(n%2)
        if (n < 0) return 1.0 / power(x, -n);
        else return power(x, n);
    }
private:
    double power(double x, int n) {
        if (n == 0) return 1;
        double tmp = power(x, n / 2);
        if (n % 2 == 0) return tmp * tmp;
        else return tmp * tmp * x;
    }
};

发表于 2016-09-08 10:14:58 回复(2)

C/C++

童珉

// 非递归代码
class Solution {
public:
    double pow(double x, int n) {
        bool neg;
        if(n<0) {neg=true; n=-n;}
        else {neg = false;}
        
        double res = 1;
        double tmp_pow=x; long bit_flg = 1;
        
        while(bit_flg<=n){
            if(n&bit_flg) res*=tmp_pow;
            tmp_pow=tmp_pow*tmp_pow; bit_flg = bit_flg<<1;
        }
        
        if(neg) return 1/res;
        return res;
    }
};

发表于 2018-05-12 21:56:23 回复(0)

Aileon

class Solution:
    def pow(self , x , n ):
        # write code here
        s = abs(int(n))
        res = 1
        temp = x
        while s | 0: # 一直向右移动到为0
            if s & 1:
                res *= temp
            temp *= temp 
            s = s >> 1 # 向右移动
        return res if n > 0 else 1/res

发表于 2020-08-29 21:57:09 回复(0)

惠鸿飞

import java.util.*;


public class Solution {
    /**
     * 
     * @param x double浮点型 
     * @param n double浮点型 
     * @return double浮点型
     */
    public double pow (double x, double n) {
        if(x == 1.0){
            return x;
        }
        if(n == 0.0){
            return 1.0;
        }
        double result = 1.0;
        double temp = x;
        for(int i = (int)n; i != 0; i /= 2){
            if(i % 2 != 0){
                result *= temp;
            }
            temp *= temp;
        }
        return n > 0 ? result : 1/result;
    }
}

发表于 2020-06-13 17:00:10 回复(0)

然后就

这题怎么变成这样了？？？？ n是浮点型？？我看题解都是int啊

import java.util.*;

public class Solution {
/**
*
* @param x double浮点型
* @param n double浮点型
* @return double浮点型
*/
public double pow (double x, double n) {
// write code here
}
}

发表于 2020-05-23 01:22:54 回复(4)

llch__

    public double pow(double x, int n) {
       if(n >= 0) return pows(x, n);
       else return 1 / pows(x, -n);
    }
    private double pows(double x, int n){
        if(n == 0) return 1;
        if(n == 1) return x;
        double divpow = pows(x, n / 2);
        return divpow * divpow * (n % 2 == 1? x : 1);
    }

编辑于 2018-07-28 16:15:13 回复(0)

依然·范特西


public class Solution {
    public double pow(double x, int n) {  

  if (n < 0)  

  return 1 / solve(x, -n);  

  else  

 return solve(x, n);
    }
    
    public double solve(double x, int n){
        if (n == 0)
            return 1;
        else if (n % 2 == 1)
            return x * solve(x, n-1);
        else
            return solve(x * x, n /2);
    }
}

编辑于 2017-12-06 00:50:18 回复(0)

C/C++

nbgao

class Solution {
public:
    double pow(double x, int n) {
    	if(x == 0) 
    		return 0;
    	if(n == 0)
    		return 1;
    	double result = 1;
    	int sign = 0;
    	if(n < 0)
    	{
    		sign = 1;
    		n = -(n+1);
    		result *= x;
		}
        while(n)
		{
			if(n&1)
				result *= x;
			x *= x;
			n>>=1;	
		} 
		return sign?(1/result):result;
	}
};

发表于 2017-09-03 01:07:37 回复(0)

元气の悟空

public class Solution {
    public double pow(double x, int n) {
        return Math.pow(x,n);
    }
}

发表于 2016-08-16 18:27:07 回复(5)

C++

牛客208405915号

#include <iostream>
using namespace std;
constexpr auto ZERO = 0;
constexpr auto ONE = 1;

double calculation(double x, int n) {
double ret = 1;
while (n > 0) {
ret *= x;
n--;
};
//cout << "---ret:"<< ret <<endl;
return ret;
}

double myPow(double x, int n)
{
const char* Perror = "math error:there is no point of 0^(minus value or 0)";
double ret = 0;

if (x == ZERO)
{
if (n <= ZERO) {
printf("%s!", Perror);
}
else {
return ZERO;
}
}
else {
if (n == ZERO) {
return ONE;
}
else if (n < ZERO) {
ret = calculation(1 / x, -n);//2,-3-->(1/2)^3
}
else {
ret = calculation(x, n);//2,3-->2^3
}
}

return ret;
}

int main()
{
double ans = 0;
double x = 0;
int n = 1;
cout << "please input 2 number:";
scanf_s("%lf %d", &x, &n);
//myPow(2,3);
ans = myPow(x, n);
cout << "ans is :" << ans << endl;
return 0;
}

发表于 2022-01-25 23:12:11 回复(0)

C/C++

codewind

class Solution {
public:
    /**
     * 
     * @param x double浮点型 
     * @param n double浮点型 
     * @return double浮点型
     */
    double pow(double x, double n) {
        if(x==0) return 0;
        if(n<0) return 1/qmi(x,-n);
        else return qmi(x,n);
    } 
    inline double qmi(double x,int n) {
        if(n==0) return 1;
        if(n==1) return x;
        double res = qmi(x,n/2);
        if(n&1) return res*res*x;
        return res*res;
    }
};

发表于 2021-04-11 17:53:39 回复(0)

Java

liangshang

快速幂的思路是这样的，比如我们要求 3 ^ 5，其中5的二进制表示为0101，因此3 ^ 5可以分解成 3 ^ (2 ^ 0) * 3 ^ (2 ^ 2) = 3 ^ 1 * 3 ^ 4 = 3 ^ 5

public class Solution {
    public double pow (double x, double n) {
        // write code here
        long num = (long) n;
        if (num < 0) {
            x = 1/ x;
            num = -num;
        }
        double res = 1;
        while (num != 0) {
            if ((num & 1) != 0)
               res *= x;
            x = x * x;
            num = num >> 1;
        }
        return res;
    }
}

发表于 2020-10-18 14:24:29 回复(0)

Python

黄沙遮天

#
#
# @param x double浮点型
# @param n double浮点型
# @return double浮点型
#
class Solution:
    def pow(self , x , n ):
        # write code here
        if n==0:
            return 1
        if n==1:
            return x**n
        if n%2==0:
            if n<0:
                return 1/self.pow(x*x,-n/2)
            return self.pow(x*x,n/2)
        else:
            if n<0:
                return 1/(x*self.pow(x*x,-n//2))
            return x*self.pow(x*x,n//2)

非直接方法，采用的递归

发表于 2020-09-18 21:26:15 回复(0)

C/C++

华科不平凡

求x的n次方，我们需要考虑以下特性：

0的n次方为0
x的负数次方等于x的正数次方的倒数

考虑全面后就可以开始编码：

//
// Created by jt on 2020/9/3.
//
class Solution {
public:
    /**
     *
     * @param x double浮点型
     * @param n double浮点型
     * @return double浮点型
     */
    double pow(double x, double n) {
        // write code here
        if (x == 0) return 0;
        if (n >= 0)
            return divideAndConquer(x, n);
        else
            return 1 / divideAndConquer(x, -n);
    }

private:
    double divideAndConquer(double x, int n) {
        if (n == 0) return 1;
        double part = divideAndConquer(x, n/2);
        if (n % 2 == 0)
            return part * part;
        else
            return x * part * part;
    }
};

发表于 2020-09-03 11:35:54 回复(0)

Java

日常不想上班的码农

import java.util.*;


public class Solution {
    public double pow(double x, double n) {
        boolean bigZero = n > 0;
        int mi = Math.abs((int)n);
        double res = myPowHelper(x, mi);
        if (bigZero) {
            return res;
        }
        return 1 / res;
    }
    // 递归版本
    public double myPowHelper(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double res = 1;
        if ((n & 1) == 0) {
            double temp = myPowHelper(x, n / 2);
            res = temp * temp;
        } else {
            double temp = myPowHelper(x, n / 2);
            res = temp * temp * x;
        }
        return res;
    }
        // 迭代版本
    public double myPowHelperTwo(double x, int n) {
        if(n == 0) {
            return 1;
        }
        double res = 1;
        if((n & 1) == 0) {
            for(int i = 0; i < n / 2; i++) {
                res *= x;
            }
            res *= res;
        } else{
            for(int i = 0; i < n / 2; i++) {
                res *= x;
            }
 
            res = res * res * x;
        }
        return res;
    }
}

编辑于 2020-08-01 19:33:29 回复(0)

实现阶乘

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题