原题链接:http://oj.leetcode.com/problems/sqrtx/这是一道数值处理的题目,和Divide
Two Integers不同,这道题一般采用数值中经常用的另一种方法:二分法。基本思路是跟二分查找类似,要求是知道结果的范围,取定左界和右界,然后每次砍掉不满足条件的一半,知道左界和右界相遇。算法的时间复杂度是O(logx),空间复杂度是O(1)。代码如下:
public int sqrt(int x) {
if(x<0) return -1;
if(x==0) return 0;
int l=1;
int r=x/2+1;
while(l<=r)
{
int m = (l+r)/2;
if(m<=x/m && x/(m+1)<m+1)
return m;
if(x/m<m)
{
r = m-1;
}
else
{
l = m+1;
}
}
return 0;
}
二分法在数值计算中非常常见,还是得熟练掌握。其实这个题目还有另一种方法,称为牛顿法。不过他更多的是一种数学方法,算法在这里没有太多体现,不过牛顿法是数值计算中非常重要的方法,所以我还是介绍一下。不太了解牛顿法基本思想的朋友,可以参考一下牛顿法-维基百科。一般牛顿法是用数值方法来解一个f(y)=0的方程(为什么变量在这里用y是因为我们要求的开方是x,避免歧义)。对于这个问题我们构造f(y)=y^2-x,其中x是我们要求平方根的数,那么当f(y)=0时,即y^2-x=0,所以y=sqrt(x),即是我们要求的平方根。f(y)的导数f'(y)=2*y,根据牛顿法的迭代公式我们可以得到y_(n+1)=y_n-f(n)/f'(n)=(y_n+x/y_n)/2。最后根据以上公式来迭代解以上方程。
public int sqrt(int x) {
if (x == 0) return 0;
double lastY = 0;
double y = 1;
while (y != lastY)
{
lastY = y;
y = (y + x / y) / 2;
}
return (int)(y);
}
实际面试遇到的题目可能不是对一个整数开方,而是对一个实数。方法和整数其实是一致的,只是结束条件换成左界和右界的差的绝对值小于某一个epsilon(极小值)即可。这里注意一个小问题,就是在java中我们可以用==来判断两个double是否相等,而在C++中我们则需要通过两个数的绝对值差小于某个极小值来判断两个double的相等性。实际上两个double因为精度问题往往是不可能每一位完全相等的,java中只是帮我们做了这种判定。
比较典型的数值处理的题目还有Divide
Two Integers,Pow(x,n)等,其实方法差不多,一般就是用二分法或者以2为基进行位处理的方法。
分享到:
相关推荐
LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034 Find First and ...
leetcode 答案 LeetCode 69 题 1.题目要求 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例...
第 343 章LeetCode解题笔记 代码请于src目录笔记见笔记目录下文档README 不更新了,直接提交。。。...69.Sqrt(x) 48.旋转图像 2017.10.30 46.排列 2017.10.29 40.组合和II 39.组合和112.路径和 201
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_...
sqrt(int x)。 计算并返回 x 的平方根。 x 保证为非负整数。 1 位数 编写一个函数,该函数接受一个无符号整数并返回它具有的“1”位数(也称为汉明权重)。 例如,32 位整数“11”的二进制表示为 ...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
69.Sqrt(x); 300.LongestIncreasingSubsequence。 338. 计数位数419. 棋盘中的战舰461. 汉明距离476.数字补码500.键盘排93.恢复IP地址344.反向字符串463.岛屿周长485.最大连续数513. 查找左下树值406.按高度重构队列...
leetcode-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by JavaScript and TypeScript. easy 66.加一 (Plus One) 67.二进制求和 (Add Binary) 69.x 的平方根 (Sqrt(x)) 70.爬楼梯 ...
Leetcode算法练习 Leetcode算法练习 ...MaximumSubarray 58_LengthOfLastWord 66_PlusOne 67_AddBinary 69_Sqrt(x) 70_ClimbStairs 83_RemoveDuplicatesFromSortedList 88_MergeSortedArray 100_SameT
sqrt(int x)。 计算并返回 x 的平方根。 **单号** 说明:单号 给定一个整数数组,每个元素出现两次,除了一个。 找到那一个。 注意您的算法应该具有线性运行时复杂度。 你能在不使用额外内存的情况下实现它吗? **...
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...
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卡 Datawhale-DatasSructure-Sorting-binarySearch 第三个任务(2天) 排序 1.实现归并排序、快速排序、插入排序、冒泡...Sqrt(x) (x 的平方根) :OK_hand: 最近在准备星期六的考试,先打卡,剩下的之后补上。
leetcode 天线距离两点之间的距离 曼哈顿距离 定义为 Math.abs(x2-x1) + Math.abs(y2-y1)。 切比雪夫距离 众所周知,给定点 (x, y) 并且您需要计算它们之间的曼哈顿距离 而不是使用 |x1-x2|+|y1-y2| 您可以先将所有...
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
x 10^8次汁算,如果题目给出的时间限制カ1s,那么你选择的算法执行的计算次数最多应该在10^8量级オ有可能解决这个题目。一般O(n)的算法能解决的数据范围在n < 10^8。 O(n*logn)的算法能解决的数据范围在n <= 10...
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 ...
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2...
Sqrt(x) 二分查找 (0071)。 简化路径堆栈 (0076)。 最小窗口子串两个指针 (0121)。 买卖股票的最佳时机DP (0125)。 有效回文_两个指针_ (0138)。 使用随机指针哈希复制列表,O(1) 空间 (0139)。 断字DP (0140)。 断...
leetcode中文版到 CP 的路线图 第一组基本资料 1.图案印刷问题 2.时间复杂度分析 3. 线性搜索和循环数组表示 4. 基本数问题的回文和其他数(完美,阿姆斯特朗) 5. 简单的哈希问题(频率计数和东西) 6.前缀和问题...