LeetCode 69. x 的平方根:二分查找法实现自定义的函数:x 的平方根

栏目: IT技术 · 发布时间: 4年前

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

LeetCode 69. x 的平方根:二分查找法实现自定义的函数:x 的平方根

题目描述

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4

输出: 2

示例 2:

输入: 8

输出: 2

说明: 8 的平方根是 2.82842...,

由于返回类型是整数,小数部分将被舍去。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/sqrtx

解题思路

1.取右区间,保证left <= right 条件可以终结

2.Int类型计算sqare,上界的时候会溢出,需要转成Long来计算,但是Long的时候呢?

3.因为返回类型是整数,结果只保留整数的部分,小数部分将被舍去。所以,这里当 sqare <= x 的条件满足的时候,ans = mid,一直收敛到 left<=right 条件边界.

代码

class Solution {
    fun mySqrt(x: Int): Int {
        var left = 0
        var right = x
        var ans = -1

        while(left<=right){
            // 取右区间,保证left <= right 条件可以终结
            val mid = left + (right - left)/2

            // Int类型计算sqare,上界的时候会溢出,需要转成Long来计算,但是Long的时候呢?
             val sqare: Long = mid.toLong() * mid.toLong()

            // 因为返回类型是整数,结果只保留整数的部分,小数部分将被舍去。所以,这里当 sqare <= x 的条件满足的时候,ans = mid,一直收敛到 left<=right 条件边界.
            if(sqare<=x){
                ans = mid
                left = mid + 1
            }else{
                right = mid - 1
            }
        }

        return ans

    }
}

Kotlin开发者社区

LeetCode 69. x 的平方根:二分查找法实现自定义的函数:x 的平方根

专注分享 Java 、 Kotlin、Spring/Spring Boot、 MySQLredis 、neo4j、NoSQL、Android、JavaScript、React、Node、函数式编程、编程思想、"高可用,高性能,高实时"大型分布式系统架构设计主题。


以上所述就是小编给大家介绍的《LeetCode 69. x 的平方根:二分查找法实现自定义的函数:x 的平方根》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

推荐系统

推荐系统

[奥地利] Dietmar Jannach、Markus Zanker、Alexander Felfernig、Gerhard Friedrich / 蒋 凡 / 人民邮电出版社 / 2013-6-25 / 59.00元

编辑推荐: 通过对本书的学习,读者不仅可以全面系统地了解该领域的基础原理,还能试验如何搭建一套真正的推荐系统。 —— 百度主任架构师、百度技术委员会主席 廖若雪 本书比较全面地介绍了推荐系统涉及的相关知识点,很适合对于推荐系统感兴趣的相关人员作为入门教程,目前能够系统全面介绍相关技术的中文书籍还显得匮乏,相信这本译著对于缓解这种情况大有裨益。 ——新浪微博数据挖掘技术专家 ......一起来看看 《推荐系统》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换