【LeetCode】367. Valid Perfect Square 解题报告（Java & Python）

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

目录

题目描述题目大意解题方法方法一：完全平方式性质方法二：暴力求解方法三：二分查找方法四：牛顿法 日期

题目地址：https://leetcode.com/problems/valid-perfect-square/description/

题目描述

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

这个性质就是说一个完全平方数是从1开始的若干连续奇数的和。

代码如下。

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

方法二：暴力求解

第一想法，直接看比这个数小的数的平方能否有等于这个数的，注意比较的范围是num/2+1，宁愿多比较一个数也不能让结果错误。

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; } }

方法三：二分查找

注意的是left调整到mid+1,right调整到mid-1,这样交叉着才能保证left<= right的判断条件有效。

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

方法四：牛顿法

牛顿法详见：https://en.wikipedia.org/wiki/Newton's_method.

这个问题其实就是求f(x)=num - x ^ 2的零点。

那么，Xn+1 = Xn - f(Xn)/f'(Xn).

又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 日 —— 感恩节快乐～