用于收集一些常用数学运算的程序以备不时之需。
1. myPow(x,n) 幂运算
public class Solution {
private double pow(double x, int n){
if(n == 0) return 1;
double v = pow(x,n/2);
if(n%2 == 0)
return v*v;
else
return v*v*x;
}
public double myPow(double x, int n) {
return n < 0 ? 1/pow(x,-n) : pow(x,n);
}
}
2. greatest common divisor 最大公约数
public double GCD(double m, double n){
//所谓辗转相除法，不明白的可以举例看看。
while(m%n != 0){
double temp = n;
n = m%n;
m=temp;
}
return n;
}
3. least common multiple 最小公倍数
public double LCM(double m,double n){
return m*n/GCD(m,n);
}
4. Square root 整型近似整数平方根
public class Solution {
public int mySqrt(int x) {
if(x == 0) return 0;
long left = 1, right = Integer.MAX_VALUE;
while(true){
long mid = left + (right-left)/2;
//巧妙利用除法进行判断避免溢出。
if(mid > x/mid)
right=mid-1;
else{
if(mid+1>x/(mid+1))
return (int)mid;
left=mid+1;
}
}
}
}