10-14 LeetCode 367. 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.
寫一個方法判斷一個數(shù)是不是平方數(shù)匠题。
不使用內(nèi)置庫中的函數(shù)。
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
Solution 1:
這個題目看上去就非常簡單古沥，但是我第一次提交的代碼就超時了羞秤，我想大多數(shù)人都會像我一樣拿霉，第一個想到的算法是優(yōu)化后的窮舉，但是當數(shù)字太大時循環(huán)次數(shù)還是太多，導致超時迎捺。超時后想改進一下算法，發(fā)現(xiàn)還是有一些難度的查排。
第一個方法是與數(shù)學有關(guān)凳枝，高中還是初中學的等差數(shù)列求和。一個以1做首項，2為公差的等差數(shù)列的和為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:
第一個方法的運行速度很慢叛买，也不是我自己想出來的。因為高中數(shù)學知識已經(jīng)還給體育老師了蹋订。
我自己后來想到的方法是二分法率挣，類似于二分查找，只是在判斷等于條件時與二分查找有些區(qū)別露戒。但這些都不是重點椒功，介紹這個方法的重點是如何寫好一個二分查找。二分查找的思路都是一樣的智什，但是在代碼實現(xiàn)上一些細節(jié)的改變也會改變二分查找的效率动漾。
我寫的這個二分發(fā)是我在看《代碼之美》時看到的，我的代碼與書上還有些區(qū)別荠锭，畢竟我是求平方旱眯，所以直接用《代碼之美》上的二分來解釋為什么這個二分比較好。
《代碼之美》上的二分是Java寫的证九，我改寫成Python删豺。算法部分沒有區(qū)別！
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
最重要的地方是程序在循環(huán)中沒有判斷是否找到目標值吼鳞。《代碼之美》是這樣解釋的叫搁。
假設(shè)我們有一個N個元素的數(shù)組（N值很大）赔桌，那么從該數(shù)組中第一次找到目標的概率為1/N（一個很小的數(shù)值），下一次為1/(N/2)渴逻，仍然不是很大疾党，以此類推下去，只有當元素個數(shù)減少到10到20時惨奕，以此找到目標的概率才有意義雪位，而對于10到20個元素進行查找大概需要4次循環(huán)，當查找失敗時（在大多數(shù)應(yīng)用中很普遍）梨撞，那些額外的測試會編程額外開銷雹洗。所以省去判斷，只在最后進行是否找到目標值得判斷卧波。
感想
即使一個簡單的算法也值得去深究时肿，當數(shù)據(jù)變大時，小的優(yōu)化也很關(guān)鍵
