【leetcode刷题】T187-x 的平方根
木又连续日更第37天（37/100）
木又的第187篇leetcode解题报告
数学类型第3篇解题报告
leetcode第69题：x 的平方根
https://leetcode-cn.com/problems/sqrtx
【题目】
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
【思路】
可以暴力解决，从0遍历到x，遇到第一个数num*num > x，则返回num-1。
另一种想法，参考二分查找—寻找最后一个小于x的数。
while l <= r:
if mid * mid <= x:
l = mid + 1
else:
r = mid -1
# 最后结果：r*r <= x < l
return l - 1
【代码】
python版本
暴力
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
num = 0
while num * num <= x:
num += 1
return num - 1
二分查找
class Solution(object):
def mySqrt(self, x):
l, r = 0, x
while l <= r:
mid = (l + r) / 2
val = mid * mid
if val <= x:
l = mid + 1
else:
r = mid - 1
return l - 1
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读