leetcode每日一练-第278题-第一个错误的版本

一、思路
二分查找——因为它可以快速地将版本范围缩小一半,从而更快地找到第一个坏版本。
二、解题方法
维护一个左边界 left 和一个右边界 right,在每一步循环中,我们计算中间版本 mid,然后检查它是否是坏版本。如果是坏版本,说明第一个坏版本在 mid 或者它之前,我们将 right 更新为 mid。如果不是坏版本,说明第一个坏版本在 mid 之后,我们将 left 更新为 mid + 1。最终,当 left 和 right 相等时,就找到了第一个坏版本。
三、code
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int left=1;//设定一个左边界 left 和一个右边界 rightint right=n;while(left<right){int mid=left+(right-left)/2;if(isBadVersion(mid)){right=mid;}else{left=mid+1;}}return left;//也可以是right。当 left 和 right 相等时,就找到了第一个坏版本。}
};
=====================================================================
①
二分查找(Binary Search)是一种高效的搜索算法,适用于已排序的数据集。它的核心思想是将待查找的数据与数据集的中间元素进行比较,从而排除一半的数据,然后继续在剩余的一半中继续查找,以此类推,直到找到目标元素或者确定目标元素不存在。
二分查找的步骤如下:
-
确定查找范围的起始点和终点,通常是整个数据集的起始和终止位置。
-
计算中间元素的位置。这可以通过
(start + end) / 2来获得,也可以使用(start + end) >> 1来获得,这两种方法在整数运算中可以避免溢出问题。 -
比较中间元素与目标元素的大小关系,如果相等,则找到了目标元素,算法结束。
-
如果中间元素比目标元素大,那么目标元素应该在左半部分,将终点位置更新为中间位置减一。
-
如果中间元素比目标元素小,那么目标元素应该在右半部分,将起始位置更新为中间位置加一。
-
重复步骤2到步骤5,直到起始位置大于终点位置,表示查找范围为空,目标元素不存在。
二分查找是一种时间复杂度为 O(log n) 的算法,因此在处理大规模数据时非常高效。然而,它要求数据集是已排序的,否则无法正确进行查找。
错误:使用线性搜索来解决这个问题,但是可能因为版本数量很多而导致超时。
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
for (int i = 1; i <= n; ++i) {
if (isBadVersion(i) == true) {
return i;
}
}
return -1; // 如果没有找到坏版本,可以根据题目要求返回一个特定值
}
};
相关文章:
leetcode每日一练-第278题-第一个错误的版本
一、思路 二分查找——因为它可以快速地将版本范围缩小一半,从而更快地找到第一个坏版本。 二、解题方法 维护一个左边界 left 和一个右边界 right,在每一步循环中,我们计算中间版本 mid,然后检查它是否是坏版本。如果是坏版本…...
最小生成树笔记(Prim算法Kruskal算法)
1.最小生成树 最小生成树(Minimum Spanning Tree,简称MST)是指:在一个连通无向图中,找到一个包含所有顶点的树,且该树的所有边的权重之和最小。 换句话说,最小生成树是原图中的一个子图&#…...
4、数据清洗
4、数据清洗 前面我们处理的数据实际上都是已经被处理好的规整数据,但是在大数据整个生产过程中,需要先对数据进行数据清洗,将杂乱无章的数据整理为符合后面处理要求的规整数据。 数据去重 1.删除重复数据groupby().count():可以…...
Python-OpenCV 图像的基础操作
图像的基础操作 获取图像的像素值并修改获取图像的属性信息图像的ROI区域图像通道的拆分及合并图像扩边填充图像上的算术运算图像的加法图像的混合图像的位运算 获取图像的像素值并修改 首先读入一副图像: import numpy as np import cv2# 1.获取并修改像素值 # 读…...
test111
step3:多线程task 首先,实现两个UserService和AsyncUserService两个服务接口: package com.example.demospringboot.service;public interface UserService {void checkUserStatus(); }package com.example.demospringboot.service.impl;im…...
17. Spring 事务
目录 1. 事务定义 2. MySQL 中的事务使用 3. 没有事务时的插入 4. Spring 编程式事务 5. Spring 声明式事务 5.1 Transactional 作用范围 5.2 Transactional 参数说明 5.3 Transactional 工作原理 1. 事务定义 将⼀组操作封装成一个执行单元(封装到一起…...
【C# 基础精讲】运算符和表达式
在C#编程中,运算符和表达式是构建复杂逻辑的关键元素。运算符用于执行各种数学、逻辑和其他操作,而表达式则由运算符、变量、常量和函数组成,用于生成计算结果。本文将详细介绍C#中常见的运算符和表达式的概念,以及它们在程序中的…...
【搜索】DFS连通性模型
算法提高课笔记 目录 迷宫题意思路代码 红与黑题意思路代码 DFS 的搜索分为两大部分: 内部搜索:一个图中从一个点搜到另一个点外部搜索:从一张图(状态)搜到另一张图(状态) 在第一个部分里是图…...
项目优化后续 ,手撸一个精简版VUE项目框架!
之前说过项目之前用的vben框架,在优化完性能后打包效果由原来的纯代码96M变成了56M,后续来啦,通过更换框架,代码压缩到了36M撒花~ 现在就来详细说说是怎么手撸一个框架的! 方案: 搭建一套 vite vue3 a…...
【深度学习笔记】TensorFlow 基础
在 TensorFlow 2.0 及之后的版本中,默认采用 Eager Execution 的方式,不再使用 1.0 版本的 Session 创建会话。Eager Execution 使用更自然地方式组织代码,无需构建计算图,可以立即进行数学计算,简化了代码调试的过程。…...
面试题-springcloud中的负载均衡是如何实现的?
一句话导读 Springcloud中的负载均衡是通过Ribbon实现的,自带有很多负载均衡策略,如:包括轮询(Round Robin)、随机(Random)、加权轮询(Weighted Round Robin)、加权随机&…...
flink的ProcessWindowFunction函数的三种状态
背景 在处理窗口函数时,ProcessWindowFunction处理函数可以定义三个状态: 富函数getRuntimeContext.getState, 每个key每个窗口的状态context.windowState(),每个key的状态context.globalState,那么这几个状态之间有什么关系呢? …...
day50-springboot+ajax分页
分页依赖: <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.0.0</version> </dependency> 配置: …...
Win7 专业版Windows time w32time服务电脑重启后老是已停止
环境: Win7 专业版 问题描述: Win7 专业版Windows time w32time服务电脑重启后老是已停止 解决方案: 1.检查启动Remote Procedure Call (RPC)、Remote Procedure Call (RPC) Locator,DCOM Server Process Launcher这三个服务是…...
全网最强,接口自动化测试-token登录关联实战总结(超详细)
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 在PC端登录公司的…...
OLAP ModelKit Crack,ADO.NET和IList
OLAP ModelKit Crack,ADO.NET和IList OLAP ModelKit是一个多功能的.NET OLAP组件,用C#编写,只包含100%托管代码。它具有XP主题的外观,并能够使用任何.NET数据源(ADO.NET和IList)。借助任何第三方组件(尤其是图表组件)呈现数据的能力扩展了产品…...
4 三组例子,用OpenCV玩转图像-AI-python
读取,缩放,旋转,写入图像 首先导入包,为了显示导入matplotlib/为了在matplotlib显示 导入CV2/查看版本 导入图片/查看图片类型 图片数组 数组大小 对于opencv通道顺序蓝色B、绿色G、红色R matplotlib通道顺序为 红色R、绿色G、蓝…...
计算机网络-三种交换方式
计算机网络-三种交换方式 电路交换(Circuit Switching) 电话交换机接通电话线的方式称为电路交换从通信资源分配的角度来看,交换(Switching)就是按照某种方式动态的分配传输线路的资源 电话交换机 为了解决电话之间通信两两之间连线过多,所以产生了电话…...
03 制作Ubuntu启动盘
1 软碟通 我是用软碟通制作启动盘。安装软碟通时一定要把虚拟光驱给勾选上,其余两个可以看你心情。 2 镜像文件 我使用清华镜像网站找到的Ubuntu镜像文件。 Index of /ubuntu-releases/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 请自己选择镜像…...
【JavaSE】String类中常用的字符串方法(超全)
目录 1.求字符串的长度 2.判断字符串是否为空 3.String对象的比较 3.1 判断字符串是否相同 3.2 比较字符串大小 3.3 忽略大小写比较 4.字符串查找 5.转化 5.1 数值和字符串转化 5.1.1 数字转字符串 valueof 5.1.2 valueOf的其他用法 5.1.3 字符串转数字 5.2 大小写转…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
