写在前面
重新熟悉下计算平方根的算法, 当然对于力扣的平方根69. x 的平方根 - 力扣（LeetCode）, 已经出现了不下五种的方法了, 这次简要总结下. 代码均为C++.
调包
return (int) sqrt(x);
return (int) pow(x, .5);
高级调包
应用了 \(\sqrt x=\exp(\frac{\ln x}2)\) 这一关系, 需要注意浮点数舍入误差.
int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = exp(0.5 * log(x));
return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
}
二分查找
class Solution {
public:
int mySqrt(int x) {
int l{}, r{x}, ans{-1};
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
return ans;
}
};
因为要找出小于等于$x$的最大整数$k$使$k$满足$k^2\leq x$, 这类最大化最小的问题当然可以通过二分来做.
相当经典的思路, 但是每次mid增减的量太少, 比较慢.
减奇数法
class Solution {
public:
int mySqrt(int x) {
int cnt{};
long long k{1};
while ((x = x - k) >= 0) k = 2 * (++cnt) + 1;
return cnt;
}
};
这里参考B站某位网友的评论, 整数的平方不是可以表示成奇数之和吗, 这个思路很新颖, 虽然时间上比较长.
牛顿迭代
数值分析中的经典算法, 任何初值只要迭代7次以内几乎都可以得到较为精确的结果, 何况这还只需要给出整数.
class Solution {
public:
int mySqrt(int x) {
if (!x) return 0;
double xk = x, xk1 = INT64_MAX;
while (fabs(xk - xk1) > 1e-7) {
xk = xk1;
xk1 = (xk + x / xk) / 2;
}
return static_cast<int>(xk);
}
};
当然还有牛顿迭代的位运算实现, 这里就不给出了, 具体可参考维基1.
位运算估计
这个方法算是相当高级的了, 但是也相当靠近计算机底层的算法, CS味道很浓, 这里只给出代码, 具体可参考Wikipedia2. 代码也参考Wikipedia.
class Solution {
public:
int mySqrt(int x) {
// cₙ
int c = 0;
// dₙ which starts at the highest power of four <= n
int d = 1 << 30; // The second-to-top bit is set.
// Same as ((unsigned) INT32_MAX + 1) / 2.
while (d > x) d >>= 2;
// for dₙ … d₀
while (d) {
if (x >= c + d) { // if Xₘ₊₁ ≥ Yₘ then aₘ = 2ᵐ
x -= c + d; // Xₘ = Xₘ₊₁ - Yₘ
c = (c >> 1) + d; // cₘ₋₁ = cₘ/2 + dₘ (aₘ is 2ᵐ)
} else {
c >>= 1; // cₘ₋₁ = cₘ/2 (aₘ is 0)
}
d >>= 2; // dₘ₋₁ = dₘ/4
}
return c; // c₋₁
}
};
实际执行速度并不快, 可能是因为编译器优化使得位运算的速度快的并不明显.
手算长除法
这里先给出C++代码, 具体的内容可以参考我的另一篇文章:
class Solution {
public:
int find_nice(int R, int b = 0) {
int l{}, r{9};
while (l <= r) {
int mid = l + (r - l) / 2;
if ((20 * b + mid) * mid > R)
r = mid - 1;
else
l = mid + 1;
}
return l - 1;
}
int mySqrt(int n) {
int dividend{}, quotient{}, reminder{}, i{};
vector<int> a(10, 0);
while (n) {
a[i++] = n % 100;
n /= 100;
}
for (int j = i - 1; j >= 0; --j) {
dividend = reminder * 100 + a[j];
int tmp = find_nice(dividend, quotient);
reminder = dividend - (20 * quotient + tmp) * tmp;
quotient = quotient * 10 + tmp;
}
return quotient;
}
};
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了36.80%的用户
看起来还是不错的, 并且是一种新方法, 我看大家的题解中并没有写过.