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
题目标签：Math
题目给了我们一个 num， 让我们判断它 是不是 perfect square。
可以利用binary search来找，需要注意overflow。
Java Solution:
Runtime beats 41.41%
完成日期：06/16/2017
关键词：binary search
关键点：利用binary search 来找到 mid * mid == num
1 class Solution 2 { 3 public boolean isPerfectSquare(int num) 4 { 5 if(num <= 0) 6 return false; 7 8 int left = 0; 9 int right = num; 10 11 while(left <= right) 12 { 13 int mid = left + (right - left) / 2; 14 15 int sq = mid * mid; 16 // check overflow here 17 if(sq != 0 && sq / mid != mid) 18 { 19 right = mid - 1; 20 continue; 21 } 22 23 24 if(sq == num) 25 return true; 26 else if(sq > num) { 27 right = mid - 1; 28 } 29 else 30 { 31 left = mid + 1; 32 } 33 34 } 35 36 return false; 37 } 38 }
参考资料：n/a
LeetCode 题目列表 - LeetCode Questions List
题目来源：https://leetcode.com/