j

jaryue

V1

2023/03/30阅读:18主题:默认主题

leetcode367有效完全平方数

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
为了提高性能,使用二分法查找数:\

  1. 定义临时变量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
  }
  1. 二分查找语法,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 炫耀一下:

分类:

后端

标签:

Golang

作者介绍

j
jaryue
V1