当前位置: 首页 > news >正文

力扣刷题--数组--第三天

今天再做两道二分查找的题目,关于二分查找的知识可看我前两篇博客。话不多说,直接开干!

题目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 00 x ∗ x x*x xx的值数组,然后将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

相关文章:

力扣刷题--数组--第三天

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

开源即时通讯IM框架 MobileIMSDK v6.5 发布

一、更新内容简介 本次更新为次要版本更新&#xff0c;进行了bug修复和优化升级&#xff08;更新历史详见&#xff1a;码云 Release Notes、Github Release Notes&#xff09;。 MobileIMSDK 可能是市面上唯一同时支持 UDPTCPWebSocket 三种协议的同类开源IM框架。轻量级、高…...

React 第二十七章 Hook useMemo

useMemo 函数可以用于缓存计算结果&#xff0c;以避免不必要的重复计算。 在React的函数组件中&#xff0c;当组件重新渲染时&#xff0c;函数组件内的所有代码都会重新执行。有些计算可能是非常消耗资源的&#xff0c;例如进行复杂的计算或进行网络请求。如果这些计算的结果在…...

自己写的爬虫小案例

网址&#xff1a;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&#xff0c;作为一门历史悠久而又历久弥新的编程语言&#xff0c;始终站在技术发展的前沿&#xff0c;引领着软件开发的潮流。随着Java 18的发布&#xff0c;我们再次见证了这门语言的自我迭代与革新。本文将深入探讨Java 18带来的新特性、技术趋势&#xff0c;以及它如何…...

毕业论文怎么写? 推荐4个AI工具

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

JVM认识之垃圾收集算法

一、标记-清除算法 1、定义 标记-清除算法是最基础的垃圾收集算法。它分为标记和清除两个阶段。先标记出所有需要回收的对象&#xff08;即垃圾&#xff09;&#xff0c;在标记完成后再统一回收所有垃圾对象。 2、优点和缺点 优点&#xff1a;实现简单缺点&#xff1a; 可能…...

docker-compose部署gitlab

需要提前安装docker和docker-compose环境 参考&#xff1a;部署docker-ce_安装部署docker-ce-CSDN博客 参考&#xff1a;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 张量转换&#xff08;NumPy Array&#xff09;3.5 张量运算3.6 CPU v/s GPU …...

翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习三

合集 ChatGPT 通过图形化的方式来理解 Transformer 架构 翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习一翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习二翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深…...

基于Seata实现分布式事务实现

Seata 是一个开源的分布式事务解决方案&#xff0c;它提供了高性能和简单易用的分布式事务服务。Seata 将事务的参与者分为 TC&#xff08;Transaction Coordinator&#xff09;、TM&#xff08;Transaction Manager&#xff09;和 RM&#xff08;Resource Manager&#xff09;…...

adss光缆是什么意思

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

JavaScript异步编程——04-同源和跨域

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

出差——蓝桥杯十三届2022国赛大学B组真题

问题分析 该题属于枚举类型&#xff0c;遍历所有情况选出符合条件的即可。因为只需要派两个人&#xff0c;因此采用两层循环遍历每一种情况。 AC_Code #include <bits/stdc.h> using namespace std; string str;//选择的两人 bool ok(){if(str.find("A")!-1…...

UE5(射线检测)学习笔记

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

语音识别的基本概念

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

OpenCV Radon变换探测直线(拉东变换)

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

六、Redis五种常用数据结构-zset

zset是Redis的有序集合数据类型&#xff0c;但是其和set一样是不能重复的。但是相比于set其又是有序的。set的每个数据都有一个double类型的分数&#xff0c;zset正是根据这个分数来进行数据间的排序从小到大。有序集合中的元素是唯一的&#xff0c;但是分数(score)是可以重复的…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...