力扣刷题--数组--第三天
今天再做两道二分查找的题目,关于二分查找的知识可看我前两篇博客。话不多说,直接开干!
题目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
相关文章:

力扣刷题--数组--第三天
今天再做两道二分查找的题目,关于二分查找的知识可看我前两篇博客。话不多说,直接开干! 题目1:69.x 的平方根 题目详情: 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。由于返回类型是整数&#…...

开源即时通讯IM框架 MobileIMSDK v6.5 发布
一、更新内容简介 本次更新为次要版本更新,进行了bug修复和优化升级(更新历史详见:码云 Release Notes、Github Release Notes)。 MobileIMSDK 可能是市面上唯一同时支持 UDPTCPWebSocket 三种协议的同类开源IM框架。轻量级、高…...
React 第二十七章 Hook useMemo
useMemo 函数可以用于缓存计算结果,以避免不必要的重复计算。 在React的函数组件中,当组件重新渲染时,函数组件内的所有代码都会重新执行。有些计算可能是非常消耗资源的,例如进行复杂的计算或进行网络请求。如果这些计算的结果在…...

自己写的爬虫小案例
网址:aHR0cDovL2pzc2NqZ3B0Lmp4d3JkLmdvdi5jbi8/dXJsPS92aWV3L3dvcmtpbmdVbml0L3dvcmtpbmdVbml0Lmh0bWw 这串代码能够爬取勘察单位企业的详细信息。 import requests import time import csv f open(勘察单位公司信息.csv,w,encodingutf-8,newline) csv_writer …...
Kafka 环境搭建和使用之单机模式详细教程
上一篇:Kakfa 简介及相关组件介绍 下一篇:Kafka 环境搭建之伪分布式集群详细教程 Kafka 环境搭建 Kafka的环境搭建可以根据不同的需求和场景采取不同的模式,主要包括以下几种: 单机模式(Standalone Mode): 在这种模式下,Kafka、Zookeeper 以及生产者和消费者都在同一…...

Xamarin.Android项目使用ConstraintLayout约束布局
Xamarin.AndroidX.ConstraintLayout Xamarin.Android.Support.Constraint.Layout Xamarin.AndroidX.ConstraintLayout.Solver Xamarin.AndroidX.DataBinding.ViewBinding Xamarin.AndroidX.Legacy.Support.Core.UI Xamarin.AndroidX.Lifecycle.LiveData ![在这里插入图片描述]…...
探索Java 18:未来技术趋势与革新之路
Java,作为一门历史悠久而又历久弥新的编程语言,始终站在技术发展的前沿,引领着软件开发的潮流。随着Java 18的发布,我们再次见证了这门语言的自我迭代与革新。本文将深入探讨Java 18带来的新特性、技术趋势,以及它如何…...

毕业论文怎么写? 推荐4个AI工具
写作这件事一直让我们从小学时期就开始头痛,初高中时期800字的作文让我们焦头烂额,一篇作文里用尽了口水话,拼拼凑凑才勉强完成。 大学时期以为可以轻松顺利毕业,结果毕业前的最后一道坎拦住我们的是毕业论文,这玩意不…...

JVM认识之垃圾收集算法
一、标记-清除算法 1、定义 标记-清除算法是最基础的垃圾收集算法。它分为标记和清除两个阶段。先标记出所有需要回收的对象(即垃圾),在标记完成后再统一回收所有垃圾对象。 2、优点和缺点 优点:实现简单缺点: 可能…...

docker-compose部署gitlab
需要提前安装docker和docker-compose环境 参考:部署docker-ce_安装部署docker-ce-CSDN博客 参考:docker-compose部署_docker compose部署本地tar-CSDN博客 创建gitlab的数据存放目录 mkdir /opt/gitlab && cd mkdir /opt/gitlab mkdir {conf…...

Colab/PyTorch - 001 PyTorch Basics
Colab/PyTorch - 001 PyTorch Basics 1. 源由2. PyTorch库概览3. 处理过程2.1 数据加载与处理2.2 构建神经网络2.3 模型推断2.4 兼容性 3. 张量介绍3.1 构建张量3.2 访问张量元素3.3 张量元素类型3.4 张量转换(NumPy Array)3.5 张量运算3.6 CPU v/s GPU …...

翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习三
合集 ChatGPT 通过图形化的方式来理解 Transformer 架构 翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习一翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习二翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深…...
基于Seata实现分布式事务实现
Seata 是一个开源的分布式事务解决方案,它提供了高性能和简单易用的分布式事务服务。Seata 将事务的参与者分为 TC(Transaction Coordinator)、TM(Transaction Manager)和 RM(Resource Manager)…...

adss光缆是什么意思
adss光缆,adss光缆型号,adss光缆用途 什么是adss光缆 ADSS用于高压输电线路并利用电力系统输电塔干,整个光缆为非金属介质,自承悬挂于电力铁塔上的电力强度最小的位置。它运用于已建高压输电线路,具有安全性高&#…...

JavaScript异步编程——04-同源和跨域
同源和跨域 同源 同源策略是浏览器的一种安全策略,所谓同源是指,域名,协议,端口完全相同。 跨域问题的解决方案 从我自己的网站访问别人网站的内容,就叫跨域。 出于安全性考虑,浏览器不允许ajax跨域获取…...

出差——蓝桥杯十三届2022国赛大学B组真题
问题分析 该题属于枚举类型,遍历所有情况选出符合条件的即可。因为只需要派两个人,因此采用两层循环遍历每一种情况。 AC_Code #include <bits/stdc.h> using namespace std; string str;//选择的两人 bool ok(){if(str.find("A")!-1…...

UE5(射线检测)学习笔记
这一篇会讲解射线检测点击事件、离开悬停、进入悬停事件的检测,以及关闭射线检测的事件,和射线检测蓝图的基础讲解。 创建一个简单的第三人称模板 创建一个射线检测的文件夹RadiationInspection,并且右键蓝图-场景组件-命名为BPC_Radiation…...

语音识别的基本概念
语音识别的基本概念 言语是一种复杂的现象。人们很少了解它是如何产生和感知的。天真的想法常常是语音是由单词构成的,而每个单词又由音素组成。不幸的是,现实却大不相同。语音是一个动态过程,没有明确区分的…...

OpenCV Radon变换探测直线(拉东变换)
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 Radon变换可以将原始图像中直线特征的处理问题转化为变换域图像中对应点特征的处理问题,其中对应特征点的横坐标表示原始图像的旋转角度,一般来讲原始图像中的噪声不会分布在直线的特征上。因此,Radon变换在探测…...

六、Redis五种常用数据结构-zset
zset是Redis的有序集合数据类型,但是其和set一样是不能重复的。但是相比于set其又是有序的。set的每个数据都有一个double类型的分数,zset正是根据这个分数来进行数据间的排序从小到大。有序集合中的元素是唯一的,但是分数(score)是可以重复的…...

label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...

论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...

抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...