云智网站建设公司,前端开发线下培训班,90后做网站,IT男为女朋友做的求婚网站给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数#xff0c;结果只保留 整数部分 #xff0c;小数部分将被 舍去 。 注意#xff1a;不允许使用任何内置指数函数和算符#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 这道题虽然是简单题… 给你一个非负整数 x 计算并返回 x 的 算术平方根 。 由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 这道题虽然是简单题可它表现的也不是那么简单刚看到题的时候我也想的是用内置函数可是正当我写的时候看到了题目的要求(可我还是用)
return (int)Math.pow(x,0.5); 我又拿了其他方式写了几次现在给大家分享一下我的做题思路
第一种方式找区间
我们可以假设为该区间是由红绿颜色组成的红色代表的是小于等于目标值绿色代表大于目标值这样 通过不断的移动指针终会从红色变为绿色我们求的目标值就是红色区域的最后一个元素 //利用二分查找进行求解public int mySqrt(int x) {if(x0||x1){return x;}int rfind(x,0,x);return r-1;}public boolean isGree(int val,int x){return (long)val*valx;}public int find(int x,int left,int right){if(leftright){return 0;}//找到最右侧的第一个红色while(leftright){int midleft(right-left)/2;if(isGree(mid,x)){rightmid;}else{leftmid1;}}return left;} 方法二普通的二分搜索 public int mySqrt(int x) {if(x0||x1){return x;}int left0;int rightx;while(leftright){int midleft(right-left)/2;if(midx/mid){return mid;}else if(midx/mid){leftmid1;}else{rightmid-1;}}return right;}
方法三最右侧的二分搜索 这种方法我觉的你学会了你才是对二分搜索有了一定的理解它的取值范围还是它的边界初始值因为这种靠左侧靠右侧的方法训话条件都是leftright,而不是left等于right,因为题目中给定的参数根号x是可以取到的所以我们为了凑写个条件写成rightx1这样就可以套我们的模板了具体模板看一起学算法二分搜索篇 public int mySqrt(int x) {if(x0||x1){return x;}int left0;int rightx1;while(leftright){int midleft(right-left)/2;if(midx/mid){leftmid1;}else{rightmid;}}return left-1;}
模板就套好了当我提交的时候错了 最后几个居然过不去遇到这种情况过不去千万别回头检查代码的问题过了90%多的代码一般不会出现什么大的问题我建议的方法是直接打表 if(x2147483647){return 46340;}
然后过了这种直接打表的方式还是很好用的效率也嘎嘎高
