- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
给你一个非负整数 x ,计算并返回 x 的算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sqrtx
(1)线性搜索
线性搜索是一种比较容易想到的方法,遍历 [0, x] 之间的所有整数,找出 <= x 的最大整数,然后将其返回。不过在编写代码时要注意整数溢出问题。此外需要说明的是,搜索区间虽然是 [0, x],但是在绝大多数情况下,不会遍历完整个区间,因为当 x 越大时, x 的算术平方根就越小于 x,当找到该值时,直接返回即可。
(2)二分搜索
由于搜索区间 [0, x]是有序的,所以可以使用二分搜索算法来降低查找的时间复杂度。
(3)袖珍计算器算法
思路参考本题官方题解
「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数,得到我们想要计算的结果。我们将 x \sqrt{x}x 写成幂的形式 x1/2,再使用自然对数 e 进行换底,即可得到
这样我们就可以得到 x \sqrt{x}x 的值了。
//思路1————线性搜索
class Solution {
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
for (int i = 2; i <= x; i++) {
int tmp1 = i * i;
int tmp2 = (i + 1) * (i + 1);
if (tmp1 == x || (tmp1 < x && tmp2 > x)) {
return i;
}
//出现整数溢出的情况
if (tmp2 < 0) {
return i;
}
}
return 1;
}
}
//思路2————二分搜索
class Solution {
public int mySqrt(int x) {
int left = 0, right = x;
int res = -1;
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;
}
}
//思路3————袖珍计算器算法
class Solution {
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int res = (int) Math.exp(0.5 * Math.log(x));
return (long) (res + 1) * (res + 1) <= x ? res + 1 : res;
}
}
开发者涨薪指南
48位大咖的思考法则、工作方式、逻辑体系
我正在尝试编写一个程序,在名为 items 的数组中进行顺序搜索和二分搜索,该数组具有 10000 个已排序的随机 int 值。第二个名为 targets 的数组加载了 1000 个 int 值(50
当我尝试使用图表并为其编写一些代码但没有成功时,我遇到了一个问题:/!! 我想创建一些东西来获取图形数据并检查它是否:1- 连接2-二分法3-有循环4-是一棵树 所以我想知道,例如,是否可以将其写入以
我是一名优秀的程序员,十分优秀!