LeetCode 0367.有效的完全平方数【Go】

有效的完全平方数

LeetCode367. 有效的完全平方数

题目描述

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

思路

题目要求

• 给定一个数，判断其是否为完全平方数
• 结果返回true或false

等同于寻找算术平方根，若找到则返回true，若未找到则返回false。寻找算术平方根可以用二分法。

注意

由于完全平方数的定义：能表示成某个整数的平方的形式。

所以判断条件不能写mid == num/mid，只能写mid * mid == num，因为num/mid为int类型，会导致结果错误。

例如：当num=5, mid=2时，mid == num/mid为true，而num并不是完全平方数。而mid * mid == num为false，结果正确。

代码

Go

func isPerfectSquare(num int) bool {
  if num <= 1 {
    return true
  }
  left, right := 1, num/2
  for left <= right {
        mid := left + ((right-left)>>1)
    if mid*mid == num {
      return true
    } else if mid*mid < num {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return false
}

Link

GitHub