网站维护中是什么意思,上海奉贤网站建设 列表网,wordpress微信验证码登录,2018一级a做爰片免费网站今天再做两道二分查找的题目#xff0c;关于二分查找的知识可看我前两篇博客。话不多说#xff0c;直接开干#xff01;
题目1#xff1a;69.x 的平方根 题目详情#xff1a; 给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。由于返回类型是整数#…今天再做两道二分查找的题目关于二分查找的知识可看我前两篇博客。话不多说直接开干
题目169.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:lindex0rindexxwhile lindexrindex:midlindex(rindex-lindex)//2# x仍作为targetmid*mid与target比较即可if mid*mid x:lindexmid1elif mid*mid x:rindexmid-1else:# x的算数平方根是个整数则满足mid*midxreturn mid# 若x算术平方根不是整数故找不到一个索引满足条件# 这里返回的是rindex或者lindex-1return rindex为什么最后返回值是rindex或者是lindex-1呢理解二分查找算法的或者看过我第一天做题的博客应该知道其中有道题和这道的返回值极为相似。当跳出循环时满足rindexlindex且rindex1lindex。在lindex左边的值一定都小于x的算法平方根lindex是第一个大于x的算法平方根的索引因为最终取算法平方根的整数部分故返回的应该是lindex-1。同理可以从rindex的角度推得最终返回rindex。
题目2367. 有效的完全平方数 题目详述 给你一个正整数 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:lindex0rindexnumwhile lindexrindex:midlindex(rindex-lindex)//2if mid*mid num:rindexmid-1elif mid*mid num:lindexmid1else:return Truereturn False
