LeetCode 278. First Bad Version题目分析代码

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases. Subscribe to see which companies asked this question.

题目

代码库的版本号是从 1 到 n 的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。

你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错,具体接口详情和调用方法请见代码的注释部分。

注意事项

请阅读上述代码,对于不同的语言获取正确的调用 isBadVersion 的方法,比如java的调用方式是SVNRepo.isBadVersion(v)

样例 给出 n=5

调用isBadVersion(3),得到false

调用isBadVersion(5),得到true

调用isBadVersion(4),得到true

此时我们可以断定4是第一个错误的版本号

分析

二分法

代码

/**
 * public class SVNRepo {
 *     public static boolean isBadVersion(int k);
 * }
 * you can use SVNRepo.isBadVersion(k) to judge whether 
 * the kth code version is bad or not.
*/
class Solution {
    /**
     * @param n: An integers.
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        // write your code here
        int start = 1, end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(SVNRepo.isBadVersion(mid)){
                end = mid;
            } else {
                start = mid;
            }
        }
            
        if (SVNRepo.isBadVersion(start)) {
            return start;
        }
        return end;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一枝花算不算浪漫

页面静态化技术Freemarker技术的介绍及使用实例.

3976
来自专栏Java 源码分析

MyBatis笔记二:配置

1516
来自专栏Rgc

使用line_profiler查看api接口函数每行代码执行时间

项目情景描述:   在restful架构风格的项目交付测试的过程中,某接口出现 请求超时导致的http 502 Bad Gateway,于是开始排查具体是接口函...

4454
来自专栏Java进阶架构师

解密Dubbo:自己动手编写一个较为完善的RPC框架(两万字干货)

现在很多企业都在使用Dubbo或者Spring Cloud做企业的微服务架构,其实对于Dubbo最核心的技术就是RPC调用,现在我们就来动手自己编写一个RPC框...

1985
来自专栏用户2442861的专栏

X皮书之初识Redis(基本操作)

http://www.cnblogs.com/baochuan/archive/2012/10/30/2740600.html

941
来自专栏三丰SanFeng

Linux进程间通信(四) - 共享内存

共享内存的优势 采用共享内存通信的一个显而易见的好处是效率高,因为进程可以直接读写内存,而不需要任何数据的拷贝。对于像管道和消息队列等通信方式,则需要在内核和用...

3035
来自专栏大内老A

.NET Core采用的全新配置系统[5]: 聊聊默认支持的各种配置源[内存变量,环境变量和命令行参数]

较之传统通过App.config和Web.config这两个XML文件承载的配置系统,.NET Core采用的这个全新的配置模型的最大一个优势就是针对多种不同配...

2039
来自专栏JackieZheng

Spring实战——缓存

缓存 提到缓存,你能想到什么?一级缓存,二级缓存,web缓存,redis…… 你所能想到的各种包罗万象存在的打着缓存旗号存在的各种技术或者实现,无非都是宣扬缓...

20510
来自专栏IMWeb前端团队

教你做一个异步的fis3插件

本文作者:IMWeb 黄龙 原文出处:IMWeb社区 未经同意,禁止转载 不清楚fis3是什么的可以先看这个链接 http://fis.baidu.c...

2039
来自专栏知识分享

关于原子哥ENC28J60网络通信模块接收数据代码的一点疑惑

---恢复内容开始--- 这几天做STM32的ENC28J60网络通信模块,自己在原子哥的代码上进行修改测试,,发现一个问题,电脑和板子进行通信的时候总隔一段时...

3608

扫码关注云+社区

领取腾讯云代金券