10-14 LeetCode 367. Valid Perfect Square

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

Solution 1:

这个题目看上去就非常简单，但是我第一次提交的代码就超时了，我想大多数人都会像我一样，第一个想到的算法是优化后的穷举，但是当数字太大时循环次数还是太多，导致超时。超时后想改进一下算法，发现还是有一些难度的。

第一个方法是与数学有关，高中还是初中学的等差数列求和。一个以1做首项，2为公差的等差数列的和为n*n。

a[1] = 1, a[2] = 3, a[n] = a[n-1] + 2
a[1] + a[2] + ... + a[n] = 1 + 3 + 5 + ... + 2*n-1
                         = n * n

然后很自然而然的有了下面的代码：

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        result = 0
        i = 1
        while result < num:
            result += i
            i += 2
            if result == num:
                return True
        return False

Solution 2:

第一个方法的运行速度很慢，也不是我自己想出来的。因为高中数学知识已经还给体育老师了。

我自己后来想到的方法是二分法，类似于二分查找，只是在判断等于条件时与二分查找有些区别。但这些都不是重点，介绍这个方法的重点是如何写好一个二分查找。二分查找的思路都是一样的，但是在代码实现上一些细节的改变也会改变二分查找的效率。

我写的这个二分发是我在看《代码之美》时看到的，我的代码与书上还有些区别，毕竟我是求平方，所以直接用《代码之美》上的二分来解释为什么这个二分比较好。

《代码之美》上的二分是Java写的，我改写成Python。算法部分没有区别！

def binarySearch(lists, target):
    low, high = -1， len(lists)

    while high - low > 1:
        mid = (low + high) >>> 1
        mid_val = lists[mid]
        if mid_val < target:
            low = mid
        elif mid_val > target:
            high = mid

    if low == -1 or lists[low] != target:
        return -1 
    return low

最重要的地方是程序在循环中没有判断是否找到目标值。《代码之美》是这样解释的。

假设我们有一个N个元素的数组（N值很大），那么从该数组中第一次找到目标的概率为1/N（一个很小的数值），下一次为1/(N/2)，仍然不是很大，以此类推下去，只有当元素个数减少到10到20时，以此找到目标的概率才有意义，而对于10到20个元素进行查找大概需要4次循环，当查找失败时（在大多数应用中很普遍），那些额外的测试会编程额外开销。所以省去判断，只在最后进行是否找到目标值得判断。

感想

即使一个简单的算法也值得去深究，当数据变大时，小的优化也很关键