leetcode(103)

leetcode(103) 有效的完全平方数

题目描述：
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 ：
输入：num = 16
输出：true
提示：

• 1 <= num <= 231 - 1

解法

二分法。如果使用 Java，为防止溢出，可以通过 num / mid 与 mid 比较的方式来二分；python的话，则直接使用 mid*mid 与 num 比较的方式进行二分即可。

代码

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num
        while left < right:
            mid = left + (right - left + 1) // 2
            temp = num // mid
            if temp < mid:
                right = mid - 1
            else:
                left = mid
        return left ** 2 == num
      

测试结果

执行用时：28 ms, 在所有 Python3 提交中击败了 87.96% 的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了 71.67% 的用户

说明

算法题来源：力扣(LeetCode)