题目描述：

LeetCode 367. 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: True

Example 2:

Input: 14
Returns: False

题目大意：

给定一个正整数num，编写函数：如果num是完全平方数，返回True，否则返回False。

注意：不要使用任何内建函数，例如sqrt。

测试用例如题目描述。

解题思路：

解法I 牛顿迭代（Newton's Method）

求平方根可以转化为求函数y = x ^ 2 - num的根

迭代过程x = (x + num / x) * 1/2

另请参阅：https://leetcode.com/discuss/110671/3-4-short-lines-integer-newton-most-languages

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

解法II 二分法（Binary Search）

Python代码：

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        left, right = 0, num
        while left <= right:
            mid = (left + right) / 2
            if mid * mid >= num:
                right = mid - 1
            else:
                left = mid + 1
        return left * left == num

另一种解法，参考LeetCode Discuss：https://leetcode.com/discuss/110638/a-square-number-is-1-3-5-7-java-code

一个完全平方数可以分解为1 + 3 + 5 + 7 + ...

因为：(x + 1) ^ 2 - x ^ 2 = 2 * x + 1

Java代码：

public boolean isPerfectSquare(int num) {
    int i = 1;
    while (num > 0) {
        num -= i;
        i += 2;
    }
    return num == 0;
}

 

本文链接：http://bookshadow.com/weblog/2016/06/26/leetcode-valid-perfect-square/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码