leetcode 69 x的平方根

给你一个非负整数 x ，计算并返回 x 的 平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：
输入：x = 4
输出：2

示例 2：
输入：x = 8
输出：2
解释：8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

文章目录

• leetcode 69 x的平方根
• 二分法

二分法

public int mySqrt(int x) {if(x<=1)return x;int left=1;int right=x;//为什么这边循环条件要写<=，而不是<,因为如果写成小于，那么循环退出条件就是left==right,那么返回的就是left或者right,因为left和right相等，所以mid=left或者right,但是我们并没有计算left*left是否等于x,所以必须将此left==right包含进去。while(left<=right){int mid=(left+right)>>1;if(mid<x/mid){ //相当于mid*mid<x//这边是最重要的一个点，为什么left=mid+1而不是left=mid;假设left=mid,因为到最后几次循环，left设为x,那么right=x+1,mid=x;因为mid*mid<x,left=mid=x;那么就会陷入死循环的状态。所以这边left必须为mid+1。left=mid+1;}else if(mid>x/mid){ //相当于mid*mid>x//如果mid*mid>x,right肯定等于mid-1。right=mid-1;}else{return mid;}}//因为循环结束条件是left=right+1,即right=left-1;因为上面的left赋值可能错过答案多加了1，所以最后返回的结果要减去1。比如x=8，//第一次 left=1,right=8,mid=4,mid*mid>8,right=mid-1=3//第二次 left=1,right=3,mid=2,mid*mid<8,left=mid+1=3,left错过答案//第三次 left=3,right=3,mid=3,mid*mid>8,right=mid-1=2//第四次不满足条件但是left=3,right=2,所以返回的是rightreturn right;//这边必须返回right}

总结

以上是生活随笔为你收集整理的4、leetcode69 x的平方根**的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。