本文主要是介绍力扣刷题--数组--第三天,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今天再做两道二分查找的题目,关于二分查找的知识可看我前两篇博客。话不多说,直接开干!
题目1:69.x 的平方根
题目详情:
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。提示:
0 <= x <= pow(2,31)-1
解题思路:
看到题首先想到的估计就是暴力求解吧,循环找到最接近x的索引,写完提交发现:
额,我只打败了9.07%的python3用户,哈哈哈哈,我真是个菜鸡。如果这道题使用二分查找怎么做呢,我开始还想着建立一个从 0 ∗ 0 0*0 0∗0到 x ∗ x x*x x∗x的值数组,然后将x视为target,使用二分查找即可,后来看了题解才发现大可不必。无需先生成一个数组。具体见代码:
class Solution:def mySqrt(self, x: int) -> int:lindex=0rindex=xwhile lindex<=rindex:mid=lindex+(rindex-lindex)//2# x仍作为target,mid*mid与target比较即可if mid*mid < x:lindex=mid+1elif mid*mid > x:rindex=mid-1else:# x的算数平方根是个整数,则满足mid*mid=xreturn mid# 若x算术平方根不是整数,故找不到一个索引满足条件# 这里返回的是rindex或者lindex-1return rindex
为什么最后返回值是rindex或者是lindex-1呢,理解二分查找算法的或者看过我第一天做题的博客应该知道,其中有道题和这道的返回值极为相似。当跳出循环时,满足rindex<lindex且rindex+1=lindex。在lindex左边的值一定都小于x的算法平方根,lindex是第一个大于x的算法平方根的索引,因为最终取算法平方根的整数部分,故返回的应该是lindex-1。同理可以从rindex的角度推得最终返回rindex。
题目2:367. 有效的完全平方数
题目详述:
给你一个正整数 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 <= pow(2,31)-1
解题思路:
这道题和上面那道完全一样,返回值更加简单,不再详述。
class Solution:def isPerfectSquare(self, num: int) -> bool:lindex=0rindex=numwhile lindex<=rindex:mid=lindex+(rindex-lindex)//2if mid*mid > num:rindex=mid-1elif mid*mid < num:lindex=mid+1else:return Truereturn False
这篇关于力扣刷题--数组--第三天的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!