Given a positive integer num, write a function which returns True if num is a perfect square else False.
样例
For example:
Given num =
16
Returns True
解法一: 牛顿迭代器
class Solution {
public:
/**
* @param num: a positive integer
* @return: if num is a perfect square else False
*/
bool isPerfectSquare(int num) {
// write your code here
double pre = 0,
res = 1;
while (pre != res) {
pre = res;
res = (res + num / res) / 2;
}
int t = (int) res;
return t * t == num;
}
};
解法二: 二分法
class Solution {
public:
/**
* @param num: a positive integer
* @return: if num is a perfect square else False
*/
bool isPerfectSquare(int num) {
// write your code here
long left=0,right=num,mid;
while(left<=right)
{
mid=left+(right-left)/2;
long res=mid*mid;
if(res<num)
{
left=mid+1;
}
else if(res>num)
{
right=mid-1;
}
else
{
return true;
}
}
return false;
}
};
LintCode 777. Valid Perfect Square
来源: http://www.bubuko.com/infodetail-2478708.html