LeetCode题解——367. 有效的完全平方数
题目相关
题目链接
LeetCode中国，。
题目描述
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例
示例1
输入：16 输出：True
示例2
题目分析
LeetCode 给出本题难度简单。
题意分析
又是一个自己实现开方函数题目，哪么自然又是一题浮点数二分查找模板题。
样例数据分析
简单题目，就不分析。
算法设计
参考浮点数二分查找。
AC 参考代码
class Solution {
public:
unsigned int mySqrt(unsigned int x) {
//x 是非负整数
double left = 0;
double right = x;
double mid;
const double EPS = 1e-8;
//使用 mid 查找
while (abs(right-left) > EPS) {
mid = (left+right)/2;
if (mid*mid<x) {
left = mid;
} else {
right = mid;
}
}
return left+EPS;
}
bool isPerfectSquare(int num) {
int ans = mySqrt(num);
return ans*ans==num ? true : false;
}
};
