大厂面试真题:第一个错误的代码版本

简介: 大厂面试真题:第一个错误的代码版本

代码库的版本号是从 1 到 n 的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错,具体接口详情和调用方法请见代码的注释部分。

在线评测地址:领扣刷题官网

样例

n = 5:

    isBadVersion(3) -> false
    isBadVersion(5) -> true
    isBadVersion(4) -> true

因此可以确定第四个版本是第一个错误版本。

算法:二分
假设第k个版本为第一个错误版本,那么1---n个版本分为1---k-1为正确版本,k---n为错误版本,
我们需要以尽量少的次数去找到这个k,显然我们如果一个个找过去的平均复杂度是O(n)
那么我们可以考虑用二分来找到这个k,二分的复杂度为O(logn)

  • 二分[1,n]这个区间
  • 判断isBadVersion(mid)

    • 如果为false 说明第一个错误版本在mid的右边,令 left = mid
    • 反之则在mid左边,令 right = mid
  • 缩小判断范围,当left+1>=right的时候结束二分
  • 最后再次判断下isBadVersion(left),如果是错误版本的话返回left,反之返回right

复杂度分析

  • 时间复杂度O(logn)

    • 二分的时间复杂度
  • 空间复杂度O(1)

    • 无需额外空间
public class Solution {
    /**
     * @param n: An integer
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        int left = 1, right = n; // 左右边界
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            // 判断mid是否为正确版本,如果是的话,那么说明错误版本在mid的右边,反之则在左边
            if (SVNRepo.isBadVersion(mid)){
                right = mid; // 向[left,mid]查找错误版本
            }
            else { 
                left = mid; // 向[mid,right]查找错误版本
            }
        }
        // 最后判断下left是否是错误版本
        if (SVNRepo.isBadVersion(left)){
            return left;
        }
        return right;
    }
}

更多题解参考:九章Solution

相关文章
|
2月前
|
前端开发
【面试题】如何使用ES6 ... 让代码优雅一点?
【面试题】如何使用ES6 ... 让代码优雅一点?
|
2月前
|
存储 前端开发 JavaScript
【面试题】你是如何让js 代码变得简洁的?
【面试题】你是如何让js 代码变得简洁的?
|
1月前
|
存储 算法 Java
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
2月前
|
数据采集 数据挖掘 Python
最全妙不可言。写出优雅的 Python 代码的七条重要技巧,2024年最新被面试官怼了还有戏吗
最全妙不可言。写出优雅的 Python 代码的七条重要技巧,2024年最新被面试官怼了还有戏吗
|
2月前
|
数据采集 XML 程序员
最新用Python做垃圾分类_python垃圾分类代码用key和format,5年经验Python程序员面试27天
最新用Python做垃圾分类_python垃圾分类代码用key和format,5年经验Python程序员面试27天
最新用Python做垃圾分类_python垃圾分类代码用key和format,5年经验Python程序员面试27天
|
2月前
|
数据采集 机器学习/深度学习 人工智能
最新用python代码画爱心,来自程序猿的浪漫~_python画爱心代码(1),2024年最新面试简历模板免费
最新用python代码画爱心,来自程序猿的浪漫~_python画爱心代码(1),2024年最新面试简历模板免费
最新用python代码画爱心,来自程序猿的浪漫~_python画爱心代码(1),2024年最新面试简历模板免费
|
2月前
|
Python
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
|
2月前
|
缓存 监控 算法
Python性能优化面试:代码级、架构级与系统级优化
【4月更文挑战第19天】本文探讨了Python性能优化面试的重点,包括代码级、架构级和系统级优化。代码级优化涉及时间复杂度、空间复杂度分析,使用内置数据结构和性能分析工具。易错点包括过度优化和滥用全局变量。架构级优化关注异步编程、缓存策略和分布式系统,强调合理利用异步和缓存。系统级优化则涵盖操作系统原理、Python虚拟机优化和服务器调优,需注意监控系统资源和使用编译器加速。面试者应全面理解这些层面,以提高程序性能和面试竞争力。
33 1
Python性能优化面试:代码级、架构级与系统级优化
|
2月前
|
前端开发 JavaScript 编译器
【面试题】 你知道怎么调试线上代码吗?
【面试题】 你知道怎么调试线上代码吗?
|
2月前
|
前端开发 JavaScript 网络安全
【面试题】 本地运行的前端代码,如何让他人访问?
【面试题】 本地运行的前端代码,如何让他人访问?