原题
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例1：
输入： 4
输出： 2
示例2：
输入： 8
输出： 2
说明： 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
解法
思想
二分法
代码
class Solution {
public int mySqrt(int x) {
//为了防止end * end 超过int范围，这里统一使用使用long
long longx = x;
long start = 0;
long end = x/2;
long mid;
while(start<=end){
mid = (end+start)/2;
if(mid*mid == longx) return (int)mid;
if(mid*mid < longx) {
start = mid + 1;
if(start*start>longx) return (int)mid;
}
else if(mid*mid > longx) {
end = mid - 1;
if(end*end<longx) return (int)end;
}
}
return (int)start;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode69-x%e7%9a%84%e5%b9%b3%e6%96%b9%e6%a0%b9/
相关推荐
-
leetcode102-二叉树的层次遍历
原题 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如:给定二叉树: [3,9,20,null,null,15,7],  ...
-
leetcode876-链表的中间结点
原题 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1: 输入： [1,2,3,4,5] 输出： 此列表中的结...
-
leetcode429-N叉树的层序遍历
原题 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。 例如，给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:...
-
leetcode374-猜数字大小
原题 我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接...
-
leetcode111-二叉树的最小深度
原题 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul...
-
leetcode974-和可被K整除的子数组
原题 给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。 示例: 输入： A = [4,5,0,-2,-3,1], K = 5 输出： 7 解释： ...
-
leetcode435-无重叠区间
原题 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没...
-
leetcode206-反转链表
原题 反转一个单链表。 示例： 输入： 1->2->3->4->5->NULL 输出： 5->4->3->2->1->NULL 进阶： 你可以迭代或递归地反转链表。你能否用两种方法...
-
leetcode912-排序数组
原题 给定一个整数数组 nums，将该数组升序排列。 示例 1: 输入： [5,2,3,1] 输出： [1,2,3,5] 示例 2: 输入： [5,1,1,2,0,0] 输出： [...
