问题描述:
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
说明:不要使用任何内置的库函数,如 sqrt
。
示例 1:
输入:16 输出:True
示例 2:
输入:14 输出:False
官方:
1 class Solution(object): 2 def isPerfectSquare(self, num): 3 """ 4 :type num: int 5 :rtype: bool 6 """ 7 left, right = 1, num 8 while left <= right: 9 mid = left + (right - left) / 2 10 if mid >= num / mid: 11 right = mid - 1 12 else: 13 left = mid + 1 14 return left == num / left and num % left == 0
官方2:
1 class Solution(object): 2 def isPerfectSquare(self, num): 3 """ 4 :type num: int 5 :rtype: bool 6 """ 7 self.num=num 8 if num==1: 9 return True 10 low=1 11 high=num 12 while high-low>1: 13 mid=int((high+low)/2) 14 if mid**2==num: 15 return True 16 if mid**2>num: 17 high=mid 18 if mid**2<num: 19 low=mid 20 return False
违反规定:
1 import math 2 class Solution(object): 3 def isPerfectSquare(self, num): 4 """ 5 :type num: int 6 :rtype: bool 7 """ #4.0 8 a = str(math.sqrt(num)).split(".")[1] 9 if a !='0': 10 return False 11 return True
另外:
1 import math 2 class Solution(object): 3 def isPerfectSquare(self, num): 4 """ 5 :type num: int 6 :rtype: bool 7 """ 8 if num < 0: 9 return False 10 i = 0 11 while i**2 < num: 12 i += 1 13 return i**2 == num
最后为什么时间超限:
1 class Solution(object): 2 def isPerfectSquare(self, num): 3 """ 4 :type num: int 5 :rtype: bool 6 """ 7 left = 1 8 right = num 9 while left <= num: # <= right 10 mid = (left + right) // 2 11 if mid**2 == num: 12 return True 13 if mid**2 < num: 14 left = mid + 1 15 if mid**2 > num: 16 right = mid -1 17 return False
2018-09-27 10:08:09