[100天算法】-第一个错误的版本(day 62)
题目描述
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。示例:给定 n = 5,并且 version = 4 是第一个错误的版本。调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true所以,4 是第一个错误的版本。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-bad-version
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
方法1:二分法
思路
寻找最左边的满足条件的值
框架:
- 首先定义搜索区间为 [left, right],左右都闭合。
- 循环搜索条件为 left <= right,只要区间内有元素就继续寻找。
- 循环体内,我们不断更新 mid ,并判断 mid 是否符合题目要求。
- 如果 mid 符合要求,我们找到了一个备胎, 接着收缩右边界,继续看看左边还有没有。
- 否则收缩左边界,去右侧寻找。
- 最后我们定点到 left 元素上,由于不会提前返回,因此我们需要检查最终的 left 是否符合要求。
- 如果不符合题目要求,或者 left 出了右边的边界,说明没有找到,返回 -1。
- 否则返回 left 即可。
复杂度
- 时间复杂度:$O(logn)$
- 空间复杂度:$O(1)$
代码
Python Code
# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version):class Solution(object):def firstBadVersion(self, n):""":type n: int:rtype: int"""l, r, m = 1, n, 0while l <= r:m = l + (r - l) // 2if isBadVersion(m): r = m - 1else: l = m + 1return l# 本题中“错误版本”一定存在,不然还是需要检查最终的左指针# return l if l <= n and isBadVersion(l) else -1
相关文章:
[100天算法】-第一个错误的版本(day 62)
题目描述 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n],你…...
React 学习系列: 类组件生命周期方法
类组件生命周期方法 constructor 在类组件挂载的时候调用,用于构建一个类组件实例。 在构建类组件实例的时候, 会先执行基类构造函数( React.Component ) 使用父组件传入的 props 来初始化 props 属性, 然后执行自定义构造函数来初始化 state…...
Flume从入门到精通一站式学习笔记
文章目录 什么是FlumeFlume的特性Flume高级应用场景Flume的三大核心组件Source:数据源channelsink Flume安装部署Flume的使用案例:采集文件内容上传至HDFS案例:采集网站日志上传至HDFS 各种自定义组件例如:自定义source例如&#…...
Python150题day08
2.基础语法篇 2.1 if 条件句 ①单个条件分支 使用input函数接收用户的输入,如果用户输入的整数是偶数,则使用print函数输出"你输入的整数是:{value],它是偶数”,[value]部分要替换成用户的输入。 解答: value input("请输⼊⼀…...
正则表达式的修饰符
正则表达式的修饰符是用来修改和调整正则表达式的特殊字符或元字符。修饰符可以改变正则表达式的行为和匹配方式。以下是一些常见的正则表达式修饰符: g(全局):表示全局匹配,即在整个字符串中搜索所有匹配项ÿ…...
从行车记录仪恢复已删除/丢失视频的方法
“我的车里有行车记录仪。几天前,当我下班回家时,一辆卡车不知从哪里冒出来撞向了我。我们的两辆车都损坏了,但幸运的是,没有人受伤。我曾与卡车司机就修理我的汽车进行过会面,但他说我有错。我需要查看我的行车记录仪…...
TypeScript_抓取酒店价格数据
我们导入所需的库,包括http和request。然后,我们定义一个函数,该函数接受一个URL作为参数。 import http from http; import request from request;const fetchHotelPrices (url: string) > {// ... }接下来,我们使用request…...
vue前端实现多个url下载并合并为zip文件
一、安装 npm install jszip npm install file-saver 二、引入 import axios from axios import JSZip from "jszip"; import FileSaver from "file-saver"; 三、核心代码 videoData:[/video/26519f026fc012521605563015227403.mp4,/video/f7b9cdae14…...
Redis02-持久化策略
目录 RDB(Redis DataBase Backup file) RDB执行原理 AOF(Append-Only File) RDB和AOF对比 Redis支持多种持久化方式,以确保数据在内存中持久存储,以便在Redis服务器重启时数据不会丢失。Redis中持久化的…...
Crypto(9)[MRCTF2020]keyboard
下载题目,看看里面是什么 这是什么鬼,由题目可以获得线索,keyboard,不是键盘吗,然后看了看别人写的wp,发现是九键,有几个数字对应的密文就是第几个字母 比如第一个6,对应的字母是mno,…...
IOS自带的OCR识别功能
一、识别身份证 interface IDCardScanViewController () <AVCaptureMetadataOutputObjectsDelegate> property (nonatomic, strong) AVCaptureSession *captureSession; end implementation IDCardScanViewController - (void)viewDidLoad { [super viewDidLoad…...
1300*C. Product of Three Numbers(质数数学)
Problem - 1294C - Codeforces 解析: 首先这个数肯定不是质数,然后找到第一个因子p,对于n/p再判断质数,然后找到另外两个因子即可。 注意三个因子不能相同。 #include<bits/stdc.h> using namespace std; #define int long…...
【网络】五中IO模型介绍 + 多路转接中select和poll服务器的简单编写
高级IO 前言正式开始前面的IO函数简单过一遍什么叫做低效的IO钓鱼的例子同步IO和异步IO五种IO模型阻塞IO非阻塞IO信号驱动多路转接异步IO 小结 代码演示非阻塞IO多路转接select介绍简易select服务器timeout 为 nullptrtimeout 为 {0, 0}timeout 为 {5, 0}调用accept select编写…...
Camtasia2024破解版电脑屏幕录制剪辑软件
屏幕录制剪辑 TechSmith Camtasia for Mac v2021是 TechSmith 公司所开发出一款专业屏幕录像和编辑, Camtasia Studio2024版是由TechSmith公司官方进行汉化推出的最新版本,除2023版以下版本均没有官方汉化。 同时TechSmith公司打击第三方贩卖Camtasia Studio汉化的…...
c语言进阶部分详解(《高质量C-C++编程》经典例题讲解及柔性数组)
上篇文章我介绍了介绍动态内存管理 的相关内容:c语言进阶部分详解(详细解析动态内存管理)-CSDN博客 各种源码大家可以去我的github主页进行查找:唔姆/比特学习过程2 (gitee.com) 今天便接“上回书所言”,来介绍《高质…...
Unreal PythonScriptPlugin
Unreal PythonScriptPlugin 文章目录 Unreal PythonScriptPluginPython vs UnLua官方文档PyStubDoString 示例代码,引擎里有很多插件已经用 py 写编辑器脚本了 unreal.get_editor_subsystem(unreal.LevelEditorSubsystem).load_level("/Game/maps/UVlayoutTes…...
什么是数据可视化,为什么数据可视化很重要?
数据可视化是数据的图形表示,可以帮助人们更轻松地理解和解释复杂的信息。它涉及创建数据的视觉表示,例如图表、图形、地图和其他视觉元素,以传达数据中的见解、模式和趋势。数据可视化是将原始数据转化为可操作知识的关键工具。 以下是数据…...
chatgpt相关问题解答
1. openAI的chatgpt的收费方式有哪几种? 根据OpenAI官方的信息,ChatGPT的收费方式包括两种: 1.订阅计划(Subscription Plan):OpenAI提供了ChatGPT Plus订阅计划,每月收费20美元。订阅计划的用…...
nssm将exe应用封装成windows服务
一、简介 NSSM(Non-Sucking Service Manager)是一个用于在Windows操作系统上管理和运行应用程序作为服务的工具。它提供了一种简单的方法来将任意可执行文件转换为Windows服务,并提供了一些额外的功能和配置选项。 优点: 简单易…...
golang实现极简todolist
ToDoList 最近跟着qimi老师做了一个ToDoList,我做的GitHub地址贴在这里,但由于前端出了点问题,所以都是用postman进行测试 原项目地址 部分功能展示 删除代办 查找代办 下面给出思路 思路 其实这是一个很简单的增删改查的实现ÿ…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...
数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)
名人说:莫道桑榆晚,为霞尚满天。——刘禹锡(刘梦得,诗豪) 原创笔记:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 上一篇:《数据结构第4章 数组和广义表》…...
机器学习的数学基础:线性模型
线性模型 线性模型的基本形式为: f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法,得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...
