使用交互函数充当 check 进行二分

简介: 使用交互函数充当 check 进行二分

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 278. 第一个错误的版本 ,难度为 简单


Tag : 「二分」


你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。


假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。


你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。


示例:


给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。 
复制代码


二分



一道交互题,根据题意可知,是尽可能少调用 isBadVersion 方法来找到分割点。


考虑存在「没有错误版本」和「全是错误版本」的情况,但如果往头部插入一个正确版本,往尾部插入一个错误版本作为哨兵,仍然具有「二段性」。


实际上,只需要进行这样的思考即可,不需要真正插入这样的哨兵,把这个哨兵逻辑放到最后返回的时候判断一下即可。


那么只需要将 isBadVersion 当做 check 函数进行二分即可。


二分通常有以下两种写法,分别代表「找到最靠近中心的 True」 和「找到最靠近中心的 False」。


另外根据数据范围需要注意计算 mid 时的爆 int 问题,可以通过使用类似 l + (r - l) / 2 的做法解决,也可以通过一个临时 long 来解决。


代码:


public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            long tmp = (long)l + r >> 1;
            int mid = (int)tmp;
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}
复制代码


public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            long tmp = (long)l + r + 1 >> 1;
            int mid = (int)tmp;
            if (!isBadVersion(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return !isBadVersion(r) ? r + 1 : r;
    }
}
复制代码


  • 时间复杂度:O(\log{n})O(logn)
  • 空间复杂度:O(1)O(1)


其他「二分」相关题解




最后



这是我们「刷穿 LeetCode」系列文章的第 No.278 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
SQL 算法 Java
Apache Calcite入门
Apache Calcite入门
694 0
|
Docker 容器
docker使用阿里云镜像仓库
docker使用阿里云镜像仓库1:阿里云docker仓库 https://dev.aliyun.com/search.html 2:进去注册帐号后,点击自己的管理中心。 3:在管理中心点击加速器,右边面板会有你的加速地址,右边面板下面有详细设置步骤。
39182 1
|
7月前
|
Java 关系型数据库 MySQL
weixin050高校体育场管理系统+ssm(文档+源码)_kaic
本文针对高校体育场管理系统的开发与实现进行详细介绍。随着经济快速发展,人们对手机软件需求增加,高校体育场管理系统应运而生。系统采用JAVA技术、Mysql数据库和SSM框架等成熟技术,通过分析功能需求、可行性及性能,设计出包含管理员、用户和学生角色的功能模块。系统实现用户注册登录、信息管理等功能,简化传统手工统计模式,提高管理效率,满足用户对信息获取的及时性与准确性需求。
weixin050高校体育场管理系统+ssm(文档+源码)_kaic
|
11月前
|
存储 监控 容灾
容灾备份的具体操作步骤
【10月更文挑战第28天】容灾备份是指为了防止因自然灾害、人为破坏、系统故障等原因导致数据丢失或业务中断,而提前采取的一系列数据备份和恢复措施。
|
人工智能 云栖大会
2024云栖大会,我们来了!
2024云栖大会亮点介绍
420 1
|
存储 缓存 数据处理
计算机随机访问存储器 (RAM)
【8月更文挑战第1天】
2638 5
|
安全 JavaScript 数据安全/隐私保护
SELinux 安全模型——MLS
BLP 模型:于1973年被提出,是一种模拟军事安全策略的计算机访问控制模型,它是最早也是最常用的一种多级访问控制模型,主要用于保证系统信息的机密性,是第一个严格形式化的安全模型
182 3
SELinux 安全模型——MLS
|
JavaScript 前端开发
如何将你的项目上传到 npm
如何将你的项目上传到 npm
789 0
|
SQL 关系型数据库 数据库
postgresql报:ERROR: column “i“ of relation “test“ does not exist LINE 1: UPDATE怎么解决?
解决“ERROR: column "i" of relation "test" does not exist”错误的关键在于核实列名的准确性,修正更新语句,确保列名的引用正确无误,并考虑到任何可能影响列名引用的表别名、大小写、特殊字符或动态SQL生成等因素。通过上述步骤,你应该能有效定位并解决问题,保证SQL语句的正确执行。
1029 0
|
JavaScript 前端开发
Notepad++如何格式化JS代码
Notepad++如何格式化JS代码