Implement int sqrt(int x)
.
Compute and return the square root of x.
不用翻译。 关键是注意到两个类型,参数 int ,返回也是 int 。另外,x是不能为负数的。
1 很不好意思的说,我第一反应是先用 java 的库。
return (int) Math.sqrt(x)
成功编译过。。。
2 目的是练级,所以停止傻笑,继续思考。根据上面的测试,知道是截取整数部分,ok,暴力破解。i从1 开始一个一个试,只要 i * i 超过了 x ,那么答案就是 i -1 。其中i<=46340是偷鸡了,它为(int) sqrt(2^31),如果i超过了这个,i*i 会溢出。
if(n==0){ return 0; } int i=1; while(i*i<=n&&i<=46340){ i++; } if(i*i==n){ return i; } else{ return i-1; }
public class Solution { public int sqrt(int x) { if(x==0){ return 0; } long i =1; long j=x/2+1; while(i<=j){ long mid=i+(j-i)/2; long temp = mid*mid; if(temp==x){ return (int)mid; } else if(temp<x){ i=mid+1; } else { j=mid-1; } } return (int)j; } }
4 但是这个做法,只适用于int ,如果参数double ,返回double,怎么办?
double sqrt(double x) { 2 if (x == 0) return 0; 3 double last = 0.0; 4 double res = 1.0; 5 while (res != last) 6 { 7 last = res; 8 res = (res + x / res) / 2; 9 } 10 return res; 11 }