# 367. Valid Perfect Square 有效的完全平方数

@TOC

## # 题目描述

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
``````

## # 解题方法

### # 方法一：完全平方式性质

``````a square number is 1+3+5+7+... Time Complexity O(sqrt(N))
``````

``````public class Solution {
public boolean isPerfectSquare(int num) {
for(int i = 1; num > 0; i += 2){
num -= i;
}
return num == 0;
}
}
``````

python版本：

``````class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
i = 1
while num > 0:
num -= i
i += 2
return num == 0
``````

### # 方法二：暴力求解

``````public class Solution {
public boolean isPerfectSquare(int num) {
for(int i = 1; i <= num / 2 + 1; i++){
if(i * i == num){
return true;
}
}
return false;
}
}
``````

### # 方法三：二分查找

``````public class Solution {
public boolean isPerfectSquare(int num) {
long left = 0;
long right = num;
long mul = 0;
while(left <= right){
long mid = (right + left) / 2;
mul = mid * mid;
if(mul < num){
left = mid + 1;
}else if(mul > num){
right = mid - 1;
}else{
return true;
}
}
return false;
}
}
``````

python版本如下，注意我使用的其实这个模板，左闭右开的区间：

``````class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
l, r = 0, num + 1
# [l, r)
while l < r:
mid = l + (r - l) / 2
if mid * mid == num:
return True
if mid * mid < num:
l = mid + 1
else:
r = mid
return False
``````

### # 方法四：牛顿法

`f'(x) = -2x`.

`Xn+1 = Xn +(num - Xn ^ 2)/2Xn = (num + Xn ^ 2) / 2Xn = (num / Xn + Xn) / 2`.

`t = (num / t + t) / 2`.

``````public class Solution {
public boolean isPerfectSquare(int num) {
long t = num / 2 + 1;
while(t * t > num){
t = (num / t + t) / 2;
}
return t * t == num;
}
}
``````

python版本：

``````class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
x = num
while x * x > num:
x = (x + num / x) / 2
return x * x == num
``````

## # 日期

2017 年 5 月 4 日 2018 年 10 月 27 日 —— 10月份最后的周末！ 2018 年 11 月 22 日 —— 感恩节快乐～