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

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

 

一、思路

二分查找——因为它可以快速地将版本范围缩小一半,从而更快地找到第一个坏版本。

二、解题方法

维护一个左边界 left 和一个右边界 right,在每一步循环中,我们计算中间版本 mid,然后检查它是否是坏版本。如果是坏版本,说明第一个坏版本在 mid 或者它之前,我们将 right 更新为 mid。如果不是坏版本,说明第一个坏版本在 mid 之后,我们将 left 更新为 mid + 1。最终,当 leftright 相等时,就找到了第一个坏版本。

三、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)是一种高效的搜索算法,适用于已排序的数据集。它的核心思想是将待查找的数据与数据集的中间元素进行比较,从而排除一半的数据,然后继续在剩余的一半中继续查找,以此类推,直到找到目标元素或者确定目标元素不存在。

二分查找的步骤如下:

  1. 确定查找范围的起始点和终点,通常是整个数据集的起始和终止位置。

  2. 计算中间元素的位置。这可以通过 (start + end) / 2 来获得,也可以使用 (start + end) >> 1 来获得,这两种方法在整数运算中可以避免溢出问题。

  3. 比较中间元素与目标元素的大小关系,如果相等,则找到了目标元素,算法结束。

  4. 如果中间元素比目标元素大,那么目标元素应该在左半部分,将终点位置更新为中间位置减一。

  5. 如果中间元素比目标元素小,那么目标元素应该在右半部分,将起始位置更新为中间位置加一。

  6. 重复步骤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题-第一个错误的版本

一、思路 二分查找——因为它可以快速地将版本范围缩小一半&#xff0c;从而更快地找到第一个坏版本。 二、解题方法 维护一个左边界 left 和一个右边界 right&#xff0c;在每一步循环中&#xff0c;我们计算中间版本 mid&#xff0c;然后检查它是否是坏版本。如果是坏版本…...

最小生成树笔记(Prim算法Kruskal算法)

1.最小生成树 最小生成树&#xff08;Minimum Spanning Tree&#xff0c;简称MST&#xff09;是指&#xff1a;在一个连通无向图中&#xff0c;找到一个包含所有顶点的树&#xff0c;且该树的所有边的权重之和最小。 换句话说&#xff0c;最小生成树是原图中的一个子图&#…...

4、数据清洗

4、数据清洗 前面我们处理的数据实际上都是已经被处理好的规整数据&#xff0c;但是在大数据整个生产过程中&#xff0c;需要先对数据进行数据清洗&#xff0c;将杂乱无章的数据整理为符合后面处理要求的规整数据。 数据去重 1.删除重复数据groupby().count()&#xff1a;可以…...

Python-OpenCV 图像的基础操作

图像的基础操作 获取图像的像素值并修改获取图像的属性信息图像的ROI区域图像通道的拆分及合并图像扩边填充图像上的算术运算图像的加法图像的混合图像的位运算 获取图像的像素值并修改 首先读入一副图像&#xff1a; import numpy as np import cv2# 1.获取并修改像素值 # 读…...

test111

step3&#xff1a;多线程task 首先&#xff0c;实现两个UserService和AsyncUserService两个服务接口&#xff1a; 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. 事务定义 将⼀组操作封装成一个执行单元&#xff08;封装到一起…...

【C# 基础精讲】运算符和表达式

在C#编程中&#xff0c;运算符和表达式是构建复杂逻辑的关键元素。运算符用于执行各种数学、逻辑和其他操作&#xff0c;而表达式则由运算符、变量、常量和函数组成&#xff0c;用于生成计算结果。本文将详细介绍C#中常见的运算符和表达式的概念&#xff0c;以及它们在程序中的…...

【搜索】DFS连通性模型

算法提高课笔记 目录 迷宫题意思路代码 红与黑题意思路代码 DFS 的搜索分为两大部分&#xff1a; 内部搜索&#xff1a;一个图中从一个点搜到另一个点外部搜索&#xff1a;从一张图&#xff08;状态&#xff09;搜到另一张图&#xff08;状态&#xff09; 在第一个部分里是图…...

项目优化后续 ,手撸一个精简版VUE项目框架!

之前说过项目之前用的vben框架&#xff0c;在优化完性能后打包效果由原来的纯代码96M变成了56M&#xff0c;后续来啦&#xff0c;通过更换框架&#xff0c;代码压缩到了36M撒花~ 现在就来详细说说是怎么手撸一个框架的&#xff01; 方案&#xff1a; 搭建一套 vite vue3 a…...

【深度学习笔记】TensorFlow 基础

在 TensorFlow 2.0 及之后的版本中&#xff0c;默认采用 Eager Execution 的方式&#xff0c;不再使用 1.0 版本的 Session 创建会话。Eager Execution 使用更自然地方式组织代码&#xff0c;无需构建计算图&#xff0c;可以立即进行数学计算&#xff0c;简化了代码调试的过程。…...

面试题-springcloud中的负载均衡是如何实现的?

一句话导读 Springcloud中的负载均衡是通过Ribbon实现的&#xff0c;自带有很多负载均衡策略&#xff0c;如&#xff1a;包括轮询&#xff08;Round Robin&#xff09;、随机&#xff08;Random&#xff09;、加权轮询&#xff08;Weighted Round Robin&#xff09;、加权随机&…...

flink的ProcessWindowFunction函数的三种状态

背景 在处理窗口函数时&#xff0c;ProcessWindowFunction处理函数可以定义三个状态&#xff1a; 富函数getRuntimeContext.getState, 每个key每个窗口的状态context.windowState(),每个key的状态context.globalState&#xff0c;那么这几个状态之间有什么关系呢&#xff1f; …...

day50-springboot+ajax分页

分页依赖&#xff1a; <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.0.0</version> </dependency> 配置&#xff1a; …...

Win7 专业版Windows time w32time服务电脑重启后老是已停止

环境&#xff1a; Win7 专业版 问题描述&#xff1a; Win7 专业版Windows time w32time服务电脑重启后老是已停止 解决方案&#xff1a; 1.检查启动Remote Procedure Call (RPC)、Remote Procedure Call (RPC) Locator&#xff0c;DCOM Server Process Launcher这三个服务是…...

全网最强,接口自动化测试-token登录关联实战总结(超详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在PC端登录公司的…...

OLAP ModelKit Crack,ADO.NET和IList

OLAP ModelKit Crack,ADO.NET和IList OLAP ModelKit是一个多功能的.NET OLAP组件&#xff0c;用C#编写&#xff0c;只包含100%托管代码。它具有XP主题的外观&#xff0c;并能够使用任何.NET数据源(ADO.NET和IList)。借助任何第三方组件(尤其是图表组件)呈现数据的能力扩展了产品…...

4 三组例子,用OpenCV玩转图像-AI-python

读取&#xff0c;缩放&#xff0c;旋转&#xff0c;写入图像 首先导入包&#xff0c;为了显示导入matplotlib/为了在matplotlib显示 导入CV2/查看版本 导入图片/查看图片类型 图片数组 数组大小 对于opencv通道顺序蓝色B、绿色G、红色R matplotlib通道顺序为 红色R、绿色G、蓝…...

计算机网络-三种交换方式

计算机网络-三种交换方式 电路交换(Circuit Switching) 电话交换机接通电话线的方式称为电路交换从通信资源分配的角度来看&#xff0c;交换(Switching)就是按照某种方式动态的分配传输线路的资源 电话交换机 为了解决电话之间通信两两之间连线过多&#xff0c;所以产生了电话…...

03 制作Ubuntu启动盘

1 软碟通 我是用软碟通制作启动盘。安装软碟通时一定要把虚拟光驱给勾选上&#xff0c;其余两个可以看你心情。 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 大小写转…...

WPF虚拟桌宠组件:可嵌入、高性能、工程化UI生命体

1. 这不是“桌面宠物”&#xff0c;而是一个可嵌入的WPF UI组件化生命体你可能在Windows XP时代见过那只晃着尾巴、偶尔打哈欠的3D小猫&#xff0c;也可能在Win10系统托盘里点开过一个会眨眼的像素狐狸——但那些是独立进程、是系统级小工具、是“看一眼就关掉”的轻量娱乐。而…...

styled-theming 性能优化:如何避免主题切换时的性能瓶颈

styled-theming 性能优化&#xff1a;如何避免主题切换时的性能瓶颈 【免费下载链接】styled-theming Create themes for your app using styled-components 项目地址: https://gitcode.com/gh_mirrors/st/styled-theming styled-theming 是一个专为 styled-components …...

【数据结构与算法】数据结构基础——栈和队列

目录栈和队列1. 栈1.1 栈的概念1.2 栈的实现方式分析1.3 栈的实现1.3.1 栈的初始化与销毁1.3.2 入栈与出栈1.3.3 栈的判空与有效元素个数1.3.4 栈顶元素1.4 栈的扩展1.4.1 两栈共享空间2. 队列2.1 队列的概念2.2 队列的实现方式分析2.3 队列的实现2.3.1 队列的初始化与销毁2.3.…...

Metabase:零代码 BI 数据可视化工具,自建数据看板

Metabase&#xff1a;零代码 BI 数据可视化工具&#xff0c;自建数据看板 在数据驱动决策的时代&#xff0c;能快速看到业务数据的变化趋势至关重要。然而&#xff0c;专业 BI 工具&#xff08;如 Tableau、Power BI&#xff09;价格昂贵&#xff0c;而让每个业务同学都学 SQL …...

反向海淘站点常见配置故障复盘与数据一致性优化方案

摘要反向海淘独立站运行过程中&#xff0c;容易出现价格换算异常、页面语种错乱、商品同步失败、订单状态停滞、运费计算偏差等问题。多数故障并非系统底层缺陷&#xff0c;而是配置逻辑理解偏差、数据规范不统一引发。本文结合实际运维场景&#xff0c;汇总高频故障成因&#…...

使用Taotoken CLI工具一键配置多开发环境下的统一模型接入点

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 使用Taotoken CLI工具一键配置多开发环境下的统一模型接入点 在团队协作或管理多个AI应用项目时&#xff0c;一个常见的痛点是每个…...

Windows安卓应用安装终极指南:5分钟快速配置跨平台应用体验

Windows安卓应用安装终极指南&#xff1a;5分钟快速配置跨平台应用体验 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 还在为在Windows电脑上无法直接安装安卓应用而烦…...

ComfyUI-WanVideoWrapper深度解析:构建专业级AI视频生成工作流的完整方案

ComfyUI-WanVideoWrapper深度解析&#xff1a;构建专业级AI视频生成工作流的完整方案 【免费下载链接】ComfyUI-WanVideoWrapper 项目地址: https://gitcode.com/GitHub_Trending/co/ComfyUI-WanVideoWrapper 在AI视频生成技术快速发展的今天&#xff0c;ComfyUI-WanVi…...

Wand-Enhancer:3步解锁WeMod专业版功能的完整用户指南

Wand-Enhancer&#xff1a;3步解锁WeMod专业版功能的完整用户指南 【免费下载链接】Wand-Enhancer Advanced UX and interoperability extension for Wand (WeMod) app 项目地址: https://gitcode.com/gh_mirrors/we/Wand-Enhancer 你是否厌倦了WeMod免费版的种种限制&a…...

UE4.26实战:用蒙太奇和根运动实现角色‘钻洞’翻滚,解决碰撞体鬼畜问题

UE4.26实战&#xff1a;蒙太奇与根运动实现角色钻洞翻滚的工程化解决方案在横版过关或潜行类游戏开发中&#xff0c;角色穿越低矮空间的动画实现往往面临两大技术痛点&#xff1a;动画过渡生硬导致的"鬼畜"现象&#xff0c;以及碰撞体未同步调整引发的物理系统冲突。…...