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
为了提高性能,使用二分法查找数:\
-
定义临时变量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 炫耀一下:
作者介绍
j
jaryue
V1