leetcode-第一个错误的版本

题目描述

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

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

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

示例:

1
2
3
4
5
6
7
给定 n = 5,并且 version = 4 是第一个错误的版本。

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

所以,4 是第一个错误的版本。

方法一:二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int start=1;
int end=n;
//这里不能使用int half=(start+end)/2;
//当数值过大,相加之后会进行反转操作,变为负数,从而影响计算
int half=start/2+end/2;
while(start<end){
if(isBadVersion(half)){
end=half;
}else{
start=half+1;
}
half=start/2+end/2;
}
return start;
}
}
  • 执行用时 :13 ms, 在所有 java 提交中击败了89.64%的用户

  • 内存消耗 :32.7 MB, 在所有 java 提交中击败了71.38%的用户