69. x 的平方根
简单题,但是考察的内容可以有很多
首先是纯暴力法,毫无特色。速度也很慢。
class Solution { public: int mySqrt(int x) { long long i=1; while(1) { if(i*i<=x) i++; else break; } return i-1; } };
其次是二分法,面试官最希望看到的解法。注释的是官方解法,不知为何同样是二分法速度也有很大的差距。
class Solution { public: int mySqrt(int x) { /*int l = 0, r = x, ans = -1; while (l <= r) { int mid = l + (r - l) / 2; if ((long long)mid * mid <= x) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans;*/ if(x==0) return 0; if(x<=3) return 1; int left=1,right=x-1,mid; while(left<=right) { mid=left+(right-left)/2; if(1LL*mid*mid>x) right=mid-1; else if(1LL*mid*mid<x) left=mid+1; else if(1LL*mid*mid==x) return mid; } return right; } };
最后是牛顿迭代法,闻所未闻的解法,这是官方题解里的。还是看看原理吧
class Solution { public: int mySqrt(int x) { if (x == 0) { return 0; } double C = x, x0 = x; while (true) { double xi = 0.5 * (x0 + C / x0); if (fabs(x0 - xi) < 1e-7) { break; } x0 = xi; } return int(x0); } };