Leetcode之二分法专题-278. 第一个错误的版本(First Bad Version)
2024-08-29 11:13:03
Leetcode之二分法专题-278. 第一个错误的版本(First Bad Version)
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n
个版本 [1, 2, ..., n]
,你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version)
接口来判断版本号 version
是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
分析:
给一个N,根据题目中所说,一个版本有错,后面的后续版本都有错。
那么我们可以写出二分的规则:
如果isBadVersion(mid)==false,证明该版本没有错误,向后查找,不需要保留没有错的版本,L=mid+1
如果isBadVersion(mid)==true,该版本有错误,但不知道它是不是第一个有错误的,所以需要保留住,并且向前查找,R=mid AC代码:
/* 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 L = 1;
int R = n;
while(L<R){
int mid = (L+R)>>>1;
if(isBadVersion(mid)==true){
R = mid;
}else{
L = mid+1;
}
}
return L;
}
}
相似题目,去做做加深印象吧:Leetcode之二分法专题-374. 猜数字大小(374. Guess Number Higher or Lower)
最新文章
- apche启动错误|httpd.pid overwritten — Unclean shutdown of previous Apache run?
- SharePoint 错误集 3
- 【JS笔记】私有变量
- linux之应用开发杂记(一)
- 减肥App计划
- 差别不在英语水平,而在汉语水平If you do not leave me, we will die together.
- vb combobox 用法问题总结
- Android万能适配器base-adapter-helper的源代码分析
- [转]Installing Snow Leopard (Client) on VMware Fusion 6.0.3
- 学习新手给Android新手的一些学习建议
- Linux 多用户系统
- oauth简单使用
- 【HotSpot】jps命令行详解
- 0_Simple__clock + 0_Simple__clock_nvrtc
- 【Android Studio安装部署系列】四、Android SDK目录和作用分析
- iOS NSDictionary 转Json 去掉换行去掉空格
- Python3 Flask+nginx+Gunicorn部署(上)
- ActiveMQ应用(1)-安装及示例
- C# 简单的反射机制实例
- Android编程权威指南(第三版)- 2.8 挑战练习:添加后退按钮