|
50. Pow(x, n)
题目：实现幂函数
思路：递归——注意超出最大值的判断
public class Solution {
public double myPow(double x, int n) {
if(n < 0){
x = 1/x;
n = ~n+1;
}
if(n == 0) return 1;
if(n == 1) return x;
if(x*x > Double.MAX_VALUE){
return 0.0;
}
if(n%2 == 0){
return myPow(x*x, n/2);
}
else{
return myPow(x*x, n/2)*x;
}
}
}
69. Sqrt(x) 题目：实现开方函数
思路：二分——注意使用乘法，不要用除法，这样不会溢出。并且要求返回下取整。
public class Solution {
public int mySqrt(int x) {
if(x == 0) return 0;
if(x == 1) return 1;
int start = 0, end = x;
while(start <= end){
int mid = start+(end-start)/2;
if(mid == x/mid) return mid;
else if(mid < x/mid){
start = mid+1;
}
else{
end = mid-1;
}
}
return end;
}
}
367. Valid Perfect Square 题目：判断一个整数是不是完全平方数
思路：二分法——注意要强制转换为浮点型
public class Solution {
public boolean isPerfectSquare(int num) {
int start = 0, end = num;
while(start <= end){
int mid = start + (end - start)/2;
if((double)mid == (double)num/mid) return true;
else if((double)mid > (double)num/mid){
end = mid - 1;
}
else{
start = mid + 1;
}
}
return false;
}
}
还有一种牛顿方法 public boolean isPerfectSquare(int num) {
long x = num;
while (x * x > num) {
x = (x + num / x) >> 1;
}
return x * x == num;
}
| 
转播
