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: True
Example 2:
Input: 14
Returns: False
思路：所谓perfect Square，A perfect square is a number that can be expressed as the** product of two equal integers**.
可以参照perfect number的思路，从1到sqrt(num)依次比对，后来发现会提前跳出循环。突然灵机一动，想出了个取巧的方法。使用Python的**0.5代替sqrt，能被accept，不过好像还是不满足题目要求。
看了其他人的思路，发现还有一个牛顿法，以及二分法查找。二分法查找倒是非常直观。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
return (int(num**0.5)**2)==num
def isPerfectSquare2(self, num):
res = num
while(res*res > num):
res = (res + num/res) >> 1
return res*res == num
def isPerfectSquare3(self, num):
res = num
while res*res > num:
res = (res + num/res)/2
return res*res == num
def isPerfectSquare4(self, num):
low = 1
high = num
while(low < high):
mid = (low + high)/2
if(mid*mid>num):
high = mid -1
elif(mid*mid<num):
low = mid + 1
else:
return True
return False
if __name__ == '__main__':
sol = Solution()
print sol.isPerfectSquare(4)
print sol.isPerfectSquare(16)
print sol.isPerfectSquare(14)
print sol.isPerfectSquare(8)
print sol.isPerfectSquare(36)
print sol.isPerfectSquare2(16)
print sol.isPerfectSquare3(16)
print sol.isPerfectSquare4(16)
