367.有效的完全平方数
题目描述
给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数,如 sqrt 。
示例 1:
示例 2:
提示:
- 1 <= num <= 2 - 1
浮点数二分
// 定义解决问题的类 Solution
class Solution {
public:
// 判断正整数 num 是否为完全平方数的函数
bool isPerfectSquare(int num) {
// 设置二分查找的范围,从0到num
double l = 0, r = num;
// 使用二分查找来逼近平方根的值
// 当左右边界的差距小于1e-6时停止查找
// 这里的1e-6是一个小的阈值,用于控制查找精度
while (r - l >= 1e-6) {
// 计算中点值
double mid = (r + l) / 2;
// 如果 mid 的平方大于或等于 num,更新右边界 r
if (mid * mid >= num) r = mid;
// 否则,更新左边界 l
else l = mid;
}
// 如何判断一个数是完全平方数?
// 一个数如果是完全平方数,其平方根一定是整数。
// 在二分查找结束后,r 保存了逼近的平方根值,
// 将其强制转换成整数然后再平方,看是否等于原始数值 num。
// 如果相等则表示 num 是完全平方数,返回 true
// 否则表示 num 不是完全平方数,返回 false
if ((int)r * (int)r == num) return true;
return false;
}
};
整数二分
// 定义解决问题的类 Solution
class Solution {
public:
// 函数用来判断 num 是否为完全平方数
bool isPerfectSquare(int num) {
// 使用 long long 类型来避免在计算过程中可能出现的整数溢出
long long l = 0;
long long r = num;
// 使用二分查找算法来确定是否存在整数 n 使得 n*n == num
while (l < r) {
// 计算中间值,注意这里为了运算符优先级,先进行加法操作,再进行右移一位操作以除以2
// 右移运算符具有比加法更高的优先级,所以必须确保加法在右移之前执行
long long mid = (r + l) >> 1;
// 如果 mid 的平方大于或等于 num,那么需要在左侧区间 [l, mid] 中继续查找
if (mid * mid >= num) {
r = mid;
}
// 如果 mid 的平方小于 num,那么需要在右侧区间 [mid+1, r] 中继续查找
else {
l = mid + 1;
}
}
// 经过上面的循环,如果 num 是完全平方数,则 l (或 r) 将等于 num 的平方根
// 检查 l 的平方是否等于 num 来确定 num 是否为完全平方数
if (l * l == num) return true;
// 如果 l 的平方不等于 num,则说明 num 不是完全平方数
return false;
}
};