力扣每日一练之二分查找 Day10
力扣每日一练之二分查找 Day10
🍕前面的话🥞
大家好!本篇文章将介绍代码随想录的题,本文将以 2 道题作为背景,介绍二分查找,展示语言为 java(博主学习语言为 java)。今天呢,是博主开始刷力扣的第十天,如果有想要开始准备自己的算法面试的同学,可以跟着我的脚步一起,共同进步。大家都是并肩作战的伙伴,一起努力奋力前行,路漫漫其修远兮,吾将上下而求索,相信我们一定都可以拿到自己期望的 offer,冲冲冲!
👩💻博客主页:京与旧铺的博客主页
✨欢迎关注🖱点赞🎀收藏⭐留言✒
🔮本文由京与旧铺原创,csdn 首发!
😘系列专栏:java 学习
💻首发时间:🎞2022 年 5 月 24 日🎠
🎨你做三四月的事,八九月就会有答案,一起加油吧
🔏参考在线编程网站:🎧力扣
🀄如果觉得博主的文章还不错的话,请三连支持一下博主哦
🎧最后的话,作者是一个新人,在很多方面还做的不好,欢迎大佬指正,一起学习哦,冲冲冲
🏓导航小助手📻
[TOC]
图片
🍞Leetcode 367.有效的完全平方数
给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
进阶:不要 使用任何内置的库函数,如 sqrt 。
🌮源代码
🎏思路
考虑使用二分查找来优化方法二中的搜索过程。因为 \textit{num}num 是正整数,所以若正整数 xx 满足 x \times x = \textit{num}x×x=num,则 xx 一定满足 1 \le x \le \textit{num}1≤x≤num。于是我们可以将 11 和 \textit{num}num 作为二分查找搜索区间的初始边界。
细节
因为我们在移动左侧边界 \textit{left}left 和右侧边界 \textit{right}right 时,新的搜索区间都不会包含被检查的下标 \textit{mid}mid,所以搜索区间的边界始终是我们没有检查过的。因此,当\textit{left} = \textit{right}left=right 时,我们仍需要检查 \textit{mid} = (\textit{left}+\textit{right}) / 2mid=(left+right)/2。
🌮69. x 的平方根
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
**注意:**不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
示例 2:
👸源代码
🧈思路
题意分析
这道题要求我们实现平方根函数,输入是一个非负整数,输出也是一个整数;但是题目当中说:结果只保留整数的部分,小数部分将被舍去。这是什么意思呢?我们分析一下示例。
示例 1: 输入: 4 输出: 2 这是显然的,44 本身是一个完全平方数,2^2 = 42 2 =4。虽然在数学上一个数的平方根有正有负,但是这个题目只要求我们返回算术平方根。 示例 2 : 输入: 8 输出: 2 因为 88 的平方根实际上是 2.828422.82842,题目要求我们将小数部分舍去。因此输出 22。于是我们知道:由于输出结果的时候,需要将小数部分舍去,因此问题的答案,平方以后一定不会严格大于输入的整数。这里返回 33 就不对了,这是因为 3^2 = 9 > 83 2 =9>8。
思路分析从题目的要求和示例我们可以看出,这其实是一个查找整数的问题,并且这个整数是有范围的。
如果这个整数的平方 恰好等于 输入整数,那么我们就找到了这个整数;如果这个整数的平方 严格大于 输入整数,那么这个整数肯定不是我们要找的那个数;如果这个整数的平方 严格小于 输入整数,那么这个整数 可能 是我们要找的那个数(重点理解这句话)。因此我们可以使用「二分查找」来查找这个整数,不断缩小范围去猜。
猜的数平方以后大了就往小了猜;猜的数平方以后恰恰好等于输入的数就找到了;猜的数平方以后小了,可能猜的数就是,也可能不是。很容易知道,题目要我们返回的整数是有范围的,直觉上一个整数的平方根肯定不会超过它自己的一半,但是 00 和 11 除外,因此我们可以在 11 到输入整数除以 22 这个范围里查找我们要找的平方根整数。00 单独判断一下就好。
对代码编写逻辑的解释:
一、写 if 和 else 的原因:
猜的数是 mid ,根据上面的分析,如果 mid 的平方 严格大于 x,mid 肯定不是解,比 mid 大的整数也肯定不是解,因此问题的答案只可能存在区间 [left..mid - 1],此时设置 right = mid - 1;else 的情况就是 if 的反面,只要 if 的分支和对应的区间分析对了,else 的区间是 [left..mid - 1] 的反面区间,即 [mid..right] ,此时设置 left = mid。二、为什么最后返回 left。
退出 while (left < right) 循环的时候,由于边界搜索是 left = mid 与 right = mid - 1,因此退出循环的时候一定有 left 与 right 重合,返回 right 也可以。
评论