leetcode-367-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:

1
2
Input: 16
Output: true

Example 2:

1
2
Input: 14
Output: false

分析

题目要求不能用标准库里的 sqrt 函数，实际上第69题/)曾实现过一个 sqrt 函数，这里可以借用一下。

解决方案1(Python)

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
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left = 1
        right = x / 2
        if x < 2:
            return x
        while left <= right:
            mid = left + (right-left)/2
            if x/mid > mid:
                left = mid + 1
            elif x/mid < mid:
                right = mid - 1
            else:
                return mid
        return (left+right)/2
    
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        z = self.mySqrt(num)
        return z * z == num

题目来源