[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进行测试 原项目地址 部分功能展示 删除代办 查找代办 下面给出思路 思路 其实这是一个很简单的增删改查的实现ÿ…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
