本文主要是介绍基础数学-求平方根(easy),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、问题描述
二、实现思路
1.题目不能直接调用Math.sqrt(x)
2.这个题目可以使用二分法来缩小返回值范围
所以我们在left<right时
使 mid = (left+right)/2+1
当mid*mid>x时,说明right范围过大,right=right-1
当mid*mid<x时,说明left范围太小,left=mid
当left>=right时跳出循环,返回left
三、代码实现
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param x int整型 * @return int整型*/public int sqrt (int x) {if(x==0||x==1){return x;}else{//在函数图像中可以看出:当x>4时,√x < x/2//由于以上性质,可以使用二分法去缩小返回值范围int res=1;int left=1;int right=x;while(left<right){int mid=(left+right)/2+1;int tmpsqrt=x/mid;if(mid>tmpsqrt){//等价于mid*mid>xright=mid-1;}else{left=mid;}}return left;}}
}
四、刷题链接
求平方根_牛客题霸_牛客网
这篇关于基础数学-求平方根(easy)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!