内容简介:实现 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
- 戳这里看源码
- 各种数据结构及算法的Golang实现, LeetCode解题思路及答案
- 大厂面试题汇总及答案解析
参考资料
本文为原创文章,转载注明出处,欢迎扫码关注公众号 tomorrowwu
或者网站 https://lovecoding.club
,第一时间看后续精彩文章,觉得好的话,顺手分享到朋友圈吧,感谢支持。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- LeetCode 69. x 的平方根:二分查找法实现自定义的函数:x 的平方根
- LeetCode - 069 - x 的平方根(sqrtx)
- LeetCode 之 JavaScript 解答第69题 —— X 的平方根(Squrt(x))
- swoole之协程channel元素个数
- 用堆找出最小的 N 个数
- 统计两个IP地址之间的IP个数
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
The Cult of the Amateur
Andrew Keen / Crown Business / 2007-6-5 / USD 22.95
Amateur hour has arrived, and the audience is running the show In a hard-hitting and provocative polemic, Silicon Valley insider and pundit Andrew Keen exposes the grave consequences of today’s......一起来看看 《The Cult of the Amateur》 这本书的介绍吧!