LeetCode Valid Perfect Square
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16 Returns: TrueExample 2:
Input: 14 Returns: False
本题要判断一个数是否是完全平方数。有很多种解法，现列举如下： 解法1。牛顿法。牛顿法本是用来求解函数f(x)=0的根的，可以用来开方。$$f(x)=x^2-num$$等于0的正根就是num的根号。下面就是牛顿法求解f(x)=0的根的更新公式，$$x_{n+1}$$比$$x_n$$更接近f(x)=0的真实根。初始的时候可以随便代一个$$x_0$$到公式中。
对于函数$$f(x)=x^2-num$$，$$f'(x)=2x$$，所以牛顿递推式为$$!x_{n+1}=x_n-\frac{x_n^2-num}{2x_n}=(x_n+num/x_n)/2$$
所以我们可以初始代入$$x_n=num$$，然后不断用牛顿法，直到x*x<=num时，如果x*x==num，则num为完全平方数，否则不是。
关于牛顿法用于开放的原理介绍，果壳网上有个人介绍得很详细。
代码如下：
[cpp]
class Solution {
public:
bool isPerfectSquare(int num) {
long long x = num;
while (x*x > num) {
x = (x + num / x) / 2;
}
return x*x == num;
}
};
[/cpp]
本代码提交AC，用时0MS。
解法2。对于num，如果$$x=\frac{num}{2}$$的平方依然大于num，则$$x=\frac{x}{2}$$，如果x的平方依然大于num，则继续对x除以2，不断除，直到x平方小于等于num时，遍历[x,2*x]之间的数，看看x*x==num是否成立，如果成立，说明num是完全平方数，否则不是。这种解法在高级算法里好像讲过。完整代码如下：
[cpp]
class Solution {
public:
bool isPerfectSquare(int num) {
if (num == 1)return true;
long long x = num >> 1;
while (x*x > num)x >>= 1;
for (int y = x; y <= (x << 1); ++y) {
if (y*y == num)return true;
}
return false;
}
};
[/cpp]
本代码提交AC，用时3MS。
解法3。观测下面的等式发现完全平方数都是由连续奇数相加而来，所以我们也可以把连续奇数加起来，直到超过num时，看看和与num是否相等。
1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
….
1+3+…+(2n-1) = (2n-1 + 1)n/2 = n*n
代码如下：
[cpp]
class Solution {
public:
bool isPerfectSquare(int num) {
long long sum = 1;
for (int i = 3; sum < num; i += 2) sum += i;
return sum == num;
}
};
[/cpp]
本代码提交AC，用时3MS。
解法4。二分搜索。l=0,r=num，mid=(l+r)/2，根据mid*mid和num的大小关系一步步缩小范围。复杂度为O(lgn)，完整代码如下：
[cpp]
class Solution {
public:
bool isPerfectSquare(int num) {
long long l = 0, r = num;
while (l <= r) {
long long mid = (l + r) / 2;
long long prod = mid*mid;
if (prod == num)return true;
if (prod < num)l = mid + 1;
else r = mid – 1;
}
return l*l == num;
}
};
[/cpp]
本代码提交AC，用时0MS。
注意这个题的代码中，为了防止int越界，都需要用long long。
参考：
http://bookshadow.com/weblog/2016/06/26/leetcode-valid-perfect-square/
http://www.cnblogs.com/grandyang/p/5619296.html]]>