69-x的平方根

bergwhite 发布于2019-08-19 11:07 / 2036人阅读

摘要：前言今天心血来潮想做一下题目，就选了一道关于二分查找的题目的平方根实现函数。计算并返回的平方根，其中是非负整数。示例输入输出示例输入输出说明的平方根是由于返回类型是整数，小数部分将被舍去。

前言

今天心血来潮想做一下题目，就选了一道关于二分查找的题目x的平方根：

实现int sqrt(int x)函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

解题思路

一开始我是直接用二分查找的做法来进行解题，但是其中一个测试用例为2147395599,进行平方的时候溢出导致结果错误。后面在网上找到一个关于平方的特性：
对于一个非负数n，它的平方根m不会大于（n/2+1），即m<=(m^2)/2+1
利用这个特性缩小了二分查找的范围最终完成解题。

实现代码

    public int mySqrt(int x) {
        //为了防止溢出，选择用长整型
        long left=0;
        //对于一个非负数n，它的平方根不会大于 n/2+1
        long right=x/2+1;
        while(left<=right){//二分查找
            long middle = (left + right)/2;
            long middleSqrt=middle*middle;
            if(middleSqrt>x){
                right=middle-1;
            }else if(middleSqrt

云服务器 GPU云服务器负数的平方 c语言平方根平方根java javascript平方根

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77017.html

6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
【Leetcode】71. 简化路径

摘要：题目给定一个文档的完全路径，请进行路径简化。例如，边界情况你是否考虑了路径的情况在这种情况下，你需返回。此外，路径中也可能包含多个斜杠，如。文化和社会被恐惧所塑造，在将来这无疑也不会消失。题目给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 边界情况:...

liuchengxu 2019-08-19 11:11 评论0 收藏0
【Leetcode】71. 简化路径

摘要：题目给定一个文档的完全路径，请进行路径简化。例如，边界情况你是否考虑了路径的情况在这种情况下，你需返回。此外，路径中也可能包含多个斜杠，如。文化和社会被恐惧所塑造，在将来这无疑也不会消失。题目给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 边界情况:...

afishhhhh 2019-07-30 17:50 评论0 收藏0
Zurmo - - 商标及修改

摘要：简介关于的商标和，官方源码中是这样说的在行中文的意思是不要删除标志或版权声明。根据第节的通用公共许可证版本，这些适当的法律声明必须保留显示的标志和版权声明。上面的这段进制字符串用相应的方法转换成正常的字符串就可以看到了。 1：简介关于Zurmo的商标和Logo，官方源码中是这样说的：在 zurmo/app/protected/modules/zurmo/views/FooterVie...

CntChen 2019-07-24 10:41 评论0 收藏0