请实现函数 pow(x, n).
/** * 求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; } }
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; } }
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; } }
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; } };
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; } };
// 非递归代码 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; } };
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; } }
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); } }
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; } };
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; } }
# # # @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)非直接方法,采用的递归
求x的n次方
,我们需要考虑以下特性:
考虑全面后就可以开始编码:
// // 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; } };
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; } }