首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode: 69. Sqrt(x)

leetcode: 69. Sqrt(x)

作者头像
JNingWei
发布2018-09-27 16:59:09
4280
发布2018-09-27 16:59:09
举报
文章被收录于专栏:JNing的专栏JNing的专栏

Problem

# Implement int sqrt(int x).
#
# Compute and return the square root of x.
#
# x is guaranteed to be a non-negative integer.
#
# Example 1:
# Input: 4
# Output: 2
#
# Example 2:
# Input: 8
# Output: 2
#
# Explanation: The square root of 8 is 2.82842..., 
# and since we want to return an integer, the decimal part will be truncated.

Idea

二分法查找:start = 0, end = x, mid = (start+end)/2

(1) x/mid = mid:return mid
(2) x/mid < mid:end = mid-1
(3) x/mid > mid:start = mid+1

AC

class Solution():
    def mySqrt(self, x):
        if x < 2:
            return x
        left, right = 1, x // 2
        while left <= right:
            mid = left + (right - left) // 2
            if mid > x // mid:
                right = mid - 1
            else:
                left = mid + 1
        return left - 1


if __name__ == "__main__":
    assert Solution().mySqrt(10) == 3
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年11月19日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem
    • Idea
    • AC
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档