🧮 Algorithm Notebook
1、算法准备
1.1 牛客网编程OJ的典型输入输出
2、算法框架
2.1 动态规划
2.1.1 斐波那契数列
2.1.2 背包问题
2.1.3 贪心算法
2.1.4 序列和数组类问题
2.1.5 编辑距离
2.1.6 高楼扔鸡蛋
2.1.7 股票问题系列通解
2.1.8 最长有效括号
2.1.9 剪绳子
2.1.10 正则表达式匹配
2.2 二分查找
2.2.1 二分查找框架
2.2.2 搜索旋转排序数组
2.3 链表
2.3.1 反转链表
2.3.2 相交链表
2.3.3 合并链表
2.3.4 链表中倒数第k个节点
2.3.5 复制带随机指针的链表
2.4 排序算法
2.4.1 常见排序算法
2.5 二叉树
2.5.1 二叉树遍历
2.5.2 岛屿问题
2.5.3 二叉树路径问题
2.5.4 构造二叉树
2.6 回溯算法
2.6.1 回溯算法解题框架
2.6.2 N皇后
2.7 数组
2.7.1 删除有序数组中的重复项
2.7.2 滑动窗口最大值
2.7.3 调整数组顺序使奇数位于偶数前面
2.7.4 螺旋矩阵
2.7.5 多数元素
2.7.6 最大数
2.7.7 和为s的两个数字
2.7.8 构建乘积数组
2.7.9 两数之和
2.8 字符串
2.8.1 最小覆盖子串
2.8.2 比较版本号
2.8.3 验证IP地址
2.8.4 基本计算器 II
2.8.5 字符串解码
2.8.6 移掉 K 位数字
2.8.7 无重复字符的最长子串
2.8.8 第一个只出现一次的字符
2.8.9 翻转字符串里的单词
2.8.10 字符串转换整数 (atoi)
2.8.11 字符串四则运算
2.9 栈
2.9.1 最小栈
2.9.2 弹出序列
2.10 数学
2.10.1 用 Rand7() 实现 Rand10()
2.10.2 只出现一次的数字
2.10.3 整数反转
2.10.4 求1+2+…+n
2.10.5 二进制中1的个数
2.10.6 幂运算
2.10.7 1~n 整数中 1 出现的次数
2.10.8 数字序列中某一位的数字
2.10.9 丑数
2.10.10 n个骰子的点数
2.10.11 圆圈中最后剩下的数字
2.10.12 不用加减乘除做加法
2.10.13 x 的平方根
2.11 设计
2.11.1 LRU 缓存机制
-
+
tourist
register
Sign in
x 的平方根
## 题目 > 题目来源:[69. x 的平方根](https://leetcode-cn.com/problems/sqrtx)。 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 **示例 1:** ```txt 输入: 4 输出: 2 ``` **示例 2:** ```txt 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。 ``` ## 解题思路 ### 二分查找法 #### 问题分析 1. 题目实际上是找到一个数 $num$ 使得: $$ num * num \le x $$ 并且 $$ (num + 1) * (num + 1) \gt x $$ 而这个数一定不大于 $\frac12 x$。 2. 因此题目实际上可以看做查找一个 $num \in [1, \frac12 x]$ 符合上述条件,因此可以采用二分法来进行查找。 #### 参考代码 ```java /** * 69. x 的平方根 * @param x 待求整数 * @return x 的平方根的整数部分 */ public int sqrt(int x) { if (x == 1) {return 1;} int left = 1, right = x / 2, res = 0; while(left <= right) { int mid = left + (right - left) / 2; if ((long)mid * mid <= x) { res = mid; left = mid + 1; } else { right = mid - 1; } } return res; } ``` ### 牛顿迭代法 #### 问题分析 1. 牛顿迭代法是一种可以用来快速求解函数零点的方法。 2. 为了叙述方便,我们用 $C$ 表示待求出平方根的那个整数,显然,$C$ 的平方根就是函数 $$ y = f(x) = x^2 - C $$ 的零点。 3. 牛顿迭代法的本质是借助泰勒级数,从初始值快速向零点逼近: 1. 我们任取一个 $x_0$ 作为初始值,在每一步的迭代中,我们找到函数图像上的点 $(x_i, f(x_i))$,过该点做一条斜率为该点导数 $f^{'}(x_i)$ 的直线,与横轴的交点记为 $x_{i + 1}$,$x_{i + 1}$ 相较于 $x_i$ 而言距离零点更近。 2. 在经过多次迭代后,我们就可以得到一个距离零点非常接近的交点,下图给出了从 $x_0$ 开始迭代两次,得到 $x_1$ 和 $x_2$ 的过程。 ![fig1](https://notebook.ricear.com/media/202107/2021-07-11_1944290.35472416583845645.png) 4. 我们选择 $x_0 = C$ 作为初始值,在每一步迭代中,我们通过当前交点 $x_i$,找到图像上的点 $(x_i, x_i^2 - C)$,作一条斜率为 $f^{'}(x_i) = 2x_i$ 的直线,直线的方程为 $$ y - (x_i^2 - C) = 2x_i(x - x_i) $$ 化简后得 $$ y = 2x_ix - (x_i^2 + C) $$ 与横轴的交点为方程 $$ 2x_ix - (x_i^2 + C) = 0 $$ 的解,即为新的迭代结果 $x_{i + 1}$: $$ x_{i + 1} = \frac12 (x_i + \frac{C}{x_i}) $$ 在进行 $k$ 次迭代后,$x_k$ 的值与真实的零点 $\sqrt C$ 足够接近,即可作为答案。 > :thinking: 为什么选择 $ x_0 = C $ 作为初始值? > 因为 $y = x^2 - C$ 有两个零点 $-\sqrt C$ 和 $\sqrt C$,如果我们取得初始值较小,可能会迭代到 $-\sqrt C$ 这个零点,而我们希望找到的是 $\sqrt C$ 这个零点,因此选择 $x_0 = C$ 作为初始值,每次迭代均有 $x_{i + 1} < x_i$,零点 $\sqrt C$ 在其左侧,所以我们一定会迭代到这个零点。 > :thinking: 迭代到何时才算结束? > 每一次迭代后,我们都会距离零点更进一步,所以当相邻两次迭代得到的交点非常接近时,我们就可以断定,此时的结果已经足够我们得到答案了,一般来说,可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数 $\varepsilon$,其中 $\varepsilon$ 一般可以取 $ 10^{-6} $ 或 $ 10^{-7} $。 > :information_desk_person: 牛队迭代法也适用于 『精确到多少位小数』或者『误差不小于 0.001』的情况。 #### 参考代码 ```java /** * 69. x 的平方根(版本 4:牛顿迭代法) * @param x 待求整数 * @return x 的平方根的整数部分 */ public int sqrt(int x) { if (x == 0) {return 0;} double x0 = (double)x, x1; while (true) { x1 = 0.5 * (x0 + x / x0); if (x0 - x1 <= 1e-7) {break;} x0 = x1; } return (int)x1; } ``` ## 参考文献 1. [x 的平方根](https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution)。
ricear
July 23, 2022, 11:04 a.m.
©
BY-NC-ND(4.0)
转发文档
Collection documents
Last
Next
手机扫码
Copy link
手机扫一扫转发分享
Copy link
Markdown文件
share
link
type
password
Update password