内容简介:实现 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开发者社区
专注分享 Java 、 Kotlin、Spring/Spring Boot、 MySQL 、 redis 、neo4j、NoSQL、Android、JavaScript、React、Node、函数式编程、编程思想、"高可用,高性能,高实时"大型分布式系统架构设计主题。
以上所述就是小编给大家介绍的《LeetCode 69. x 的平方根:二分查找法实现自定义的函数:x 的平方根》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- leetcode.69.求一个数的平方根
- LeetCode - 069 - x 的平方根(sqrtx)
- LeetCode 之 JavaScript 解答第69题 —— X 的平方根(Squrt(x))
- LeetCode 81,在不满足二分的数组内使用二分法 II
- 二分查找
- 谈谈二分搜索及其变体
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
算法艺术与信息学竞赛
刘汝佳 / 清华大学出版社 / 2004-1 / 45.00元
《算法艺术与信息学竞赛》较为系统和全面地介绍了算法学最基本的知识。这些知识和技巧既是高等院校“算法与数据结构”课程的主要内容,也是国际青少年信息学奥林匹克(IOI)竞赛和ACM/ICPC国际大学生程序设计竞赛中所需要的。书中分析了相当数量的问题。 本书共3章。第1章介绍算法与数据结构;第2章介绍数学知识和方法;第3章介绍计算机几何。全书内容丰富,分析透彻,启发性强,既适合读者自学,也适合于课......一起来看看 《算法艺术与信息学竞赛》 这本书的介绍吧!
RGB转16进制工具
RGB HEX 互转工具
XML、JSON 在线转换
在线XML、JSON转换工具