卖萌的弱渣

I am stupid, I am hungry.

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

Solution

  • Binary Search (2,num/2+1)
(Valid-Perfect-Square.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 1:
            return True

        r = num/2+1
        l = 2

        while l <= r:
            mid = (l+r)/2
            target = num/mid

            # num = 5
            if num%mid != 0 and target == mid:
                    return False

            if target == mid:
                return True

            if target < mid:
                r = mid-1
            else:
                l = mid+1
        return False