文档章节

278. First Bad Version

初雪之音
 初雪之音
发布于 2017/02/24 18:26
字数 356
阅读 40
收藏 0

Description

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.

原题

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

给出 n=5
调用isBadVersion(3),得到false
调用isBadVersion(5),得到true
调用isBadVersion(4),得到true
此时我们可以断定4是第一个错误的版本号

解题思路

  • 相当于找第一个target元素,例如找第一个1
    00000001111111111111111

代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int result = 0;

		if (n > 0) {
			int left = 0, right = n;
			while (left + 1 < right) {
				int mid = left + (right - left) / 2;
				if (isBadVersion(mid)) {
					right = mid;
				} else {
					left = mid;
				}
			}
			if (isBadVersion(right)) {
				result = right;
			} else {
				result = left;
			}
		}

		return result;
    }
}

 

© 著作权归作者所有

共有 人打赏支持
初雪之音
粉丝 47
博文 268
码字总数 150009
作品 0
广州
程序员
278. First Bad Version - LeetCode

Question 278. First Bad Version Solution 题目大意:产品有5个版本1,2,3,4,5其中下一个版本依赖上一个版本,即版本4是坏的,5也就是坏的,现在要求哪个版本是第一个坏的。 思路:二分法...

yysue
08/07
0
0
[LeetCode] First Bad Version

题目 https://leetcode.com/problems/first-bad-version/ You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your ......

u013553529
2017/11/25
0
0
请问一个关于android dx命令生成dex文件时的问题

在用dx生成dex文件时,出现异常:com.android.dx.cf.code.SimException: bad range: 5..6; actual size 5 at com.android.dx.cf.code.BytecodeArray.parseInstruction(BytecodeArray.java:8......

bbflys
2013/10/30
3.4K
1
LeetCode:First Bad Version - 第一个坏版本

1、题目名称 First Bad Version(第一个坏版本) 2、题目地址 https://leetcode.com/problems/first-bad-version/ 3、题目内容 英文: You are a product manager and currently leading a ......

北风其凉
2015/09/13
1K
0
POST数据返回之后多了Content-Type: Content-Length:Access-Control-Allow-Methods

http://phpcms.web.xinet.com.cn/123.php string(952) "HTTP/1.1 200 OK Server: Tengine Date: Sun, 09 Sep 2018 10:04:39 GMT Content-Type: application/json;charset=UTF-8 Content-Leng......

voolezhang
09/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

利用责任链模式设计一个拦截器

前言 近期在做 Cicada 的拦截器功能,正好用到了责任链模式。 这个设计模式在日常使用中频率还是挺高的,借此机会来分析分析。 责任链模式 先来看看什么是责任链模式。 引用一段维基百科对其...

编程SHA
20分钟前
1
0
IDE,SATA,SCSI,SAS,FC,SSD说明与区别

DE是俗称的并口,SATA是俗称的串口,这两种硬盘是个人电脑和低端服务器常见的硬盘。SCSI是”小型计算机系统专用接口”的简称,SCSI硬盘就是采用这种接口的硬盘。SAS就是串口的SCSI接口。一般...

mskk
23分钟前
1
0
MySQL面试题集锦

什么是数据库索引?索引有哪几种类型?什么是最左前缀原则?索引算法有哪些?有什么区别? 索引是对数据库表中一列或多列的值进行排序的一种结构。一个非常恰当的比喻就是书的目录页与书的正...

老道士
58分钟前
1
0
使用 LogStash 归集日志

elastic 官网: https://www.elastic.co/ 为了便于集中查看多台主机的业务日志,使用 Filebeat, Redis, Logstash的方式进行收集: (1) Filebeat 监控日志文件的变化, 将新增部分写入redis中, 每...

ouhoo
今天
1
0
java序列化(六) - protostuff序列化

添加依赖 <dependency> <groupId>io.protostuff</groupId> <artifactId>protostuff-core</artifactId> <version>1.5.9</version> </de......

晨猫
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部