leetcode.69.求一个数的平方根

栏目: 编程工具 · 发布时间: 6年前

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

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例1:

输入: 4
输出: 2

示例2:

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

暴力版本

// 暴力解法
func mySqrt(x int) int {
    for i := 0; i <= x; i++ {
        res := i * i
        if res == x {
            return i
        } else if res > x {
            return i - 1
        }
    }
    return -1
}

二分查找

//在有序数组中,找到最后一个小于等于给定值的数
func mySqrt2(x int) int {
    low, high := 0, x
    for low <= high {
        //防止大数相加溢出
        //位运算更高效
        mid := low + (high-low)>>1
        product := mid * mid
        if product > x {
            high = mid - 1
        } else {
            if (mid == x) || (mid+1)*(mid+1) > x {
                //遍历最后一个数 || 下一个数大于目标值
                return mid
            }
            //下一个数小于等于目标值,所以mid不是最后一个数
            low = mid + 1
        }
    }
    return -1
}

二分查找思路

  • 相当于从0-x中找到最后一个平方<=x的整数
  • 我们求解的是最后一个小于等于给定值的元素,所以当 product<=x时,需要确认 mid+1 的平方>x
  • 如果 mid+1 的平方 <= x ,说明mid肯定不是最后一个,更新low

GitHub

参考资料

leetcode 69. x 的平方根

极客时间 数据结构与算法之美

本文为原创文章,转载注明出处,欢迎扫码关注公众号 tomorrowwu 或者网站 https://lovecoding.club ,第一时间看后续精彩文章,觉得好的话,顺手分享到朋友圈吧,感谢支持。

leetcode.69.求一个数的平方根


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

码出高效:Java开发手册

码出高效:Java开发手册

杨冠宝、高海慧 / 电子工业出版社 / 2018-10 / 99.00元

《码出高效:Java 开发手册》源于影响了全球250万名开发工程师的《阿里巴巴Java开发手册》,作者静心沉淀,对Java规约的来龙去脉进行了全面而彻底的内容梳理。《码出高效:Java 开发手册》以实战为中心,以新颖的角度全面阐述面向对象理论,逐步深入地探索怎样成为一位优秀开发工程师。比如:如何驾轻就熟地使用各类集合框架;如何得心应手地处理高并发多线程问题;如何顺其自然地写出可读性强、可维护性好的......一起来看看 《码出高效:Java开发手册》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具