`

Leetcode - sqrt(x)

 
阅读更多
[分析]
这是一道数值计算的题目,Code Ganker中指出数值计算类型题目通常就是二分法或者以2为基进行位处理。此题使用二分法,实现套路就是最经典的二分算法。数值计算题需要特别注意的就是数值越界处理。此题一开始没写对就是处理大数据时溢出,Method 1就是溢出版本,mid 为 int 类型,如果没有强转类型,则 mid * mid的结果仍然是int类型,赋给long类型的midSquare是不能防止数值溢出的。正如算平均数时使用减号避免加和溢出一样,可以使用除法来避免乘法溢出。
leetcode中其他数值计算题:pow(x,n),Divide Two Integers

[ref]
http://blog.csdn.net/linhuanmars/article/details/20089131



public class Solution {
    // Method 2
    public int mySqrt(int x) {
        if (x <= 0)
            return 0;
        int left = 1, right = x / 2 + 1;
        int mid = 0;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (mid <= x / mid && (x / (mid + 1)) < mid + 1) {
                return mid;
            } else if (mid > x / mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return 0;
    }
    // Method 1: fail @2147395599
    public int mySqrt1(int x) {
        if (x <= 0)
            return 0;
        int left = 1, right = x / 2 + 1;
        int mid = 0;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            long midSquare = mid * mid;
            if (midSquare <= x && x < (mid + 1) * (mid + 1))
                return mid;
            else if (midSquare > x)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return right;
    }
}
分享到:
评论

相关推荐

    leetcode怎么销号-LeetCode-Solutions:我自己的LeetCode解决方案

    leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 ...Sqrt(x) Easy 二分、牛顿迭代 0070 Climbing Stairs Easy 动态规划 0075 Sort Colors M

    leetcode-js:算法和数据结构是一个程序员的灵魂,LeetCode JavaScript TypeScript 题解

    69.x 的平方根 (Sqrt(x)) 70.爬楼梯 (Climbing Stairs) 83.删除排序链表中的重复元素 (Remove Duplicates from Sorted List) 88.合并两个有序数组 (Merge Sorted Array) 100.相同的树 (Same Tree) 104.二叉树的最大...

    Leetcode-Algorithm-Exercise

    Leetcode算法练习 Leetcode算法练习 ...MaximumSubarray 58_LengthOfLastWord 66_PlusOne 67_AddBinary 69_Sqrt(x) 70_ClimbStairs 83_RemoveDuplicatesFromSortedList 88_MergeSortedArray 100_SameT

    判断链表是否为回文链表leetcode-Leetcode:力码

    sqrt(int x)。 计算并返回 x 的平方根。 x 保证为非负整数。 1 位数 编写一个函数,该函数接受一个无符号整数并返回它具有的“1”位数(也称为汉明权重)。 例如,32 位整数“11”的二进制表示为 ...

    leetcode答案-LeetCode69:力扣69

    leetcode 答案 LeetCode 69 题 1.题目要求 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例...

    leetcode卡-Datawhale-DatasSructure-Sorting-binarySearch:Day3-DataWhale-D

    leetcode卡 Datawhale-DatasSructure-Sorting-binarySearch 第三个任务(2天) 排序 1.实现归并排序、快速排序、插入排序、冒泡...Sqrt(x) (x 的平方根) :OK_hand: 最近在准备星期六的考试,先打卡,剩下的之后补上。

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    leetcode343-LeetCode:LeetCodeJava解题

    第 343 章LeetCode解题笔记 代码请于src目录笔记见笔记目录下文档README 不更新了,直接提交。。。...69.Sqrt(x) 48.旋转图像 2017.10.30 46.排列 2017.10.29 40.组合和II 39.组合和112.路径和 201

    leetcode530-LeetcodeSolution:Leetcode的解决方案

    69.Sqrt(x); 300.LongestIncreasingSubsequence。 338. 计数位数419. 棋盘中的战舰461. 汉明距离476.数字补码500.键盘排93.恢复IP地址344.反向字符串463.岛屿周长485.最大连续数513. 查找左下树值406.按高度重构队列...

    leetcode切割分组-leetcode:leetcode

    069_sqrt.py # 实现开根号 136_single_number.py # 位操作:异或(xor)操作 x ^ 0 = x; x ^ x = 0 sum 001_two_sum.py # 求list中能加和成指定值的两个位置 015_3_sum**.py # 求list中能加和成0的三个值 数列 004_...

    leetcode题库-algorithm:acwing,leetcode,kickstart,算法模板,PAT等等

    x 10^8次汁算,如果题目给出的时间限制カ1s,那么你选择的算法执行的计算次数最多应该在10^8量级オ有可能解决这个题目。一般O(n)的算法能解决的数据范围在n &lt; 10^8。 O(n*logn)的算法能解决的数据范围在n &lt;= 10...

    leetcode : 69. x 的平方根

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

    leetcode曼哈顿距离-computational-geometry:计算几何

    leetcode 天线距离两点之间的距离 曼哈顿距离 定义为 Math.abs(x2-x1) + Math.abs(y2-y1)。 切比雪夫距离 众所周知,给定点 (x, y) 并且您需要计算它们之间的曼哈顿距离 而不是使用 |x1-x2|+|y1-y2| 您可以先将所有...

    leetcode双人赛-Leetcode:这个repo在我的java和python解决方案和描述中记录了Leetcode

    Sqrt(x) int mid long prod = mid * mid仍會overflow 要改成 long mid宣告才行 联合查找中的路径压缩 private int find(int x) { if (parent[x] == x) { return parent[x]; } parent[x] = find(parent[x]); // path ...

    leetcode 69: x的平方根

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2...

    leetcode2sumc-Leetcode_questions:Leetcode_questions

    69.Sqrt(x) (c++:二元除法) 70.Climbing Stairs(c++:Dynamic Programming) 83.从排序列表中删除重复项(c++) 88.Merge Sorted Array(c++) 00 94.Binary Tree Inorder Traversal(c++:tree traversal inorder) 100.Same...

    leetcode第321题-LeetCode:LeetCode问题的个人代码

    sqrt(int x)。 计算并返回 x 的平方根。 **单号** 说明:单号 给定一个整数数组,每个元素出现两次,除了一个。 找到那一个。 注意您的算法应该具有线性运行时复杂度。 你能在不使用额外内存的情况下实现它吗? **...

    LeetCode解题总结

    11.2 Sqrt(x) 12. 贪心算法 12.1 跳台阶游戏 12.2 买卖股票的最佳时机 12.2.1 最多允许交易一次 12.2.2 可以交易任意多次 12.2.3 最多可以交易两次 12.2.4 可以交易任意多次 12.2.5 交易后需要停止一段时间 12.3 ...

    leetcode中文版-myCP:我对CP问题的回答

    leetcode中文版到 CP 的路线图 第一组基本资料 1.图案印刷问题 2.时间复杂度分析 3. 线性搜索和循环数组表示 4. 基本数问题的回文和其他数(完美,阿姆斯特朗) 5. 简单的哈希问题(频率计数和东西) 6.前缀和问题...

    lrucacheleetcode-Python_DataStruc-Algo:Leetcode&Lintcode数据结构和算法

    Sqrt(x) 二分查找 (0071)。 简化路径堆栈 (0076)。 最小窗口子串两个指针 (0121)。 买卖股票的最佳时机DP (0125)。 有效回文_两个指针_ (0138)。 使用随机指针哈希复制列表,O(1) 空间 (0139)。 断字DP (0140)。 断...

Global site tag (gtag.js) - Google Analytics