LeetCode 69 Sqrt(x)

简介: 题目描述: Implement int sqrt(int x). Compute and return the square root of x. 题目翻译:输入x,返回sqrt(x); C语言版: int mySqrt(int x) { int t...

题目描述:

Implement int sqrt(int x).

Compute and return the square root of x.


题目翻译:输入x,返回sqrt(x);


C语言版:

int mySqrt(int x) {
    int t, l, r, mid;
    l = 1;
    r = x>>1;
    if (x < 2) return x;
    while(l <= r){
        mid = (l + r) >> 1;
        if (mid == x/mid) return mid;
        else if(mid < x/mid){
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return r;
}
看似一个简单的二分查找,其实里面也有很多细节要注意

比如:l的初始化问题,以前习惯性初始化为0,在这里就不可以,比如X==2的时候,会出现除0错误

还有就是一些开平方的结果是小数的,在这里当然就要输出整数,那么,最后return哪一个值呢?

一开始我固执的以为应该是左边的指针较小,应该返回左边的指针l,错了才发现,跳出循环的时候

左边的指针已经大于右边的指针了,因此应该返回右边的指针r!

目录
相关文章
|
Python
LeetCode 69. Sqrt(x)
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
123 0
|
Java 测试技术 C++
LeetCode 69. Sqrt(x)--(数组)--二分法查找 --简单
Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
127 0
LeetCode 69. Sqrt(x)--(数组)--二分法查找 --简单
LeetCode 69. Sqrt(x)
实现int sqrt(int x). 计算并返回x的平方根,其中x保证为非负整数. 由于返回类型是整数,因此将截断十进制数字,并仅返回结果的整数部分.
90 0
LeetCode 69. Sqrt(x)
☆打卡算法☆LeetCode 69、Sqrt(x) 算法解析
“给定一个非负整数,计算并返回x的算术平方根。”
[LeetCode]--69. Sqrt(x)
Implement int sqrt(int x). Compute and return the square root of x. 我采用的是二分法。每次折中求平方,如果大了就把中值赋给大的,如果小了就把中值赋给小的。 public int mySqrt(int x) { long start = 1, end = x; while
855 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2