[LeetCode] 69. Sqrt(x)

SQC 发布于2019-08-14 16:22 / 2148人阅读

Problem

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

Solution

start <= end / start < end / start + 1 < end

class Solution {
    public int sqrt(int x) {
        if (x < 1) return 0;
        int start = 1;
        int end = x;
        while (start < end) {
            int mid = start + (end-start)/2;
            if (mid <= x/mid && mid+1 > x/(mid+1)) {
                return mid;
            } // The key to success
            if (mid <= x/mid) start = mid;
            else end = mid;
        }
        return start;
    }
}

start+1 < end

 class Solution {
        public int sqrt(int x) {
            if (x < 1) return 0;
            int start = 1, end = x/2+1;
            while (start+1 < end) {
                int mid = start+(end-start)/2;
                if (mid <= x/mid) start = mid;
                else end = mid;
            }
            return start;
        }
    }

update 2018-11

class Solution {
    public int mySqrt(int x) {
        if (x < 0) return -1;
        int left = 1, right = x;
        while (left <= right) {
            int mid = left+(right-left)/2;
            if (mid <= x/mid) {
                if (mid+1 > x/(mid+1)) return mid;
                else left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return 0;
    }
}

云服务器 GPU云服务器 Sqrt LeetCode x69x64 php 69er

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66186.html

LeetCode69. Sqrt(x) -- 求一个数的开方

摘要：牛顿迭代法的原理很简单，其实是根据在附近的值和斜率，估计和轴的交点，因此牛顿迭代法的公式为其实就是求切线与轴的交点。代码利用牛顿法进行的更新，比直接从开始遍历所作的循环要少牛顿迭代法的基本原理，请参考牛顿迭代法求开平方描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...

ddongjian0000 2019-07-30 16:55 评论0 收藏0
leetcode-69. Sqrt(x)

摘要：题目思路牛顿迭代法，导数方程，任何函数，求解某个均可以转化为此后就可以用牛顿迭代法，不断逼近实际待求值。牛顿迭代共识应用迭代思想，类似于动态规划思想，，进行动态推断处理题目： Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-neg...

Yuqi 2019-07-30 17:22 评论0 收藏0
LeetCode 之 JavaScript 解答第69题 —— X 的平方根（Squrt(x)）

摘要：测试用例输入输入输入负数的输入平方根为正整数的输入平方根为小数的代码实现写二分查找代码需要注意的三点循环退出条件。使用二分查找之前，判断问题是否满足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿题目：sqrt(x) Implement int sqrt(int x). Compute and retu...

sf_wangchong 2019-08-23 17:00 评论0 收藏0
leetcode 二分查找 - easy

摘要：如果目标值不存在于数组中，返回它将会被按顺序插入的位置。也因为是排序的数组，所以可以考虑二分法。计算并返回的平方根，其中是非负整数。输入输出说明的平方根是由于返回类型是整数，小数部分将被舍去。是一个非负整数，并且在位有符号整型的范围内。有时候会抽时间看看题目，锻炼一下简单记录下二分查找吧，会持续更新的啊哈~~~仅供参考，路过看下就行，欢迎交流~ 第35题给定一个排序数组和一个目...

objc94 2019-07-30 17:44 评论0 收藏0