leetcode

题目描述

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

完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16 输出：true 解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。示例 2：

输入：num = 14 输出：false 解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

1 <= num <= 231 - 1

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/valid-perfect-square 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

题目要求不能使用任何内置的库函数，如 sqrt
为了提高性能,使用二分法查找数:\

定义临时变量t来核验是否为完全平方数,二分数n来进行二分查找

t, n := num/2, num/4//定义临时变量t来核验是否为完全平方数,二分数n来进行二分查找
//满足下列条件即可输出
if t*t == num || (t+1)*(t+1) == num {
   return true
  }
  if t*t < num && (t+1)*(t+1) > num {
   return false
  }

二分查找语法,n不断缩小为自身的1/2,以达到二分的效果,当小于就加上1/2;大于就减去1/2直到达到目的为止

if t*t > num {//大于就减去1/2
   t = t - n
   n = n / 2
  } else if t*t < num {//当小于就加上1/2
   t = t + n
   n = n / 2
  }

执行结果

法1

func isPerfectSquare(num int) bool {
 if num == 1 {
  return true
 }
 t, n := num/2, num/4 //定义临时变量t来核验是否为完全平方数,二分数n来进行二分查找
 for n > 0 {
  if t*t > num {//大于就减去1/2
   t = t - n
   n = n / 2
  } else if t*t < num {//当小于就加上1/2
   t = t + n
   n = n / 2
  }
  if t*t == num || (t+1)*(t+1) == num {
   return true
  }
  if t*t < num && (t+1)*(t+1) > num {
   return false
  }
  if n < 1 {
   n = 1
  }
 }
 return false
}

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户内存消耗： 1.8 MB , 在所有 Go 提交中击败了 75.35% 的用户通过测试用例： 70 / 70 炫耀一下: