首页 > 代码库 > leetcode第一刷_Sqrt(x)
leetcode第一刷_Sqrt(x)
这道题乍看下来非常简单,实际上要注意的问题非常多。
注意看给出来的函数的接口,返回的是int值,也就是计算结果是个近似值。怎样求呢?难道是从2开始往上算?直到某个值正好接近x?当然不行,肯定超时了。再仔细想一下,对了,有二分法,从最大的开始,每次计算一下平方,如果结果比x大,那么缩短上界,否则提高下界。
思想很正确,下面的问题是最大的那个值是多少?你会毫不犹豫的说出是x啊,x的平方根肯定比x小吧。好,那如果x是INT_MAX呢,你想用什么类型来存储这个平方的结果?而且这样每次减半,也得好一会儿才能收敛,毕竟INT_MAX太大了。再仔细想一下,其实最大值并不是x啊,而应该是x的平方根,对吧,因为我们求的就是平方根啊。
剩下还有两个问题,第一个,怎样判定这个值和x够近了呢?看看它的平方跟x之间的差小于某个阈值?相信这个阈值不应该是个定值,而是变化的,毕竟如果本来数小的话,小的差值也说明差别很大。那么有没有更简洁一些的方法?当然有,因为返回的是int嘛,只要算一下a的平方比x小,而(a+1)的平方比x大就可以了嘛,而且求(a+1)的平方时可以直接用a的平方的结果。那么好,第二个问题,用什么类型来存储a和(a+1)的平方呢?用int?肯定溢出啦,因为a的最大值是sqrt(INT_MAX),(a+1)的平方肯定溢出int了,应该用long long啊亲。
代码还是很简单的:
class Solution { public: int sqrt(int x) { if(x == 1) return 1; int MAX = 46340; int middle, start = 0, end = x; while(start<=end){ middle = min(MAX, start+(end-start)/2); long long tp1 = middle*middle; long long tp2 = tp1+2*middle+1; if(tp1<=x&&tp2>x) return middle; if(tp1>x) end = middle-1; else start = middle+1; } return 0; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。