第一个错误的版本
题目描述:你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例说明请见LeetCode官网。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-bad-version/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一:二分法
分别用low和high记录第一个元素和最后一个元素,然后用二分法求解,求解过程如下:
用mid记录中间位置,即
low + (high - low) / 2
,然后调用isBadVersion(mid)
方法判断当前版本是否是错误版本;如果当前版本是错误版本且当前版本前面的一个版本(需要再次调用
isBadVersion
方法)也是错误版本,则将high重置为mid-1
,然后进行下一轮处理;如果当前版本是错误版本但是当前版本的前面一个版本不是错误版本,则当前版本即是第一个错误版本,返回当前版本;
如果当前版本不是错误版本,则将low重置为
mid+1
,然后进行下一轮处理。循环终结的条件就是low大于high。
最后,如果没有找到错误的版本,返回-1。
public class LeetCode_278 extends VersionControl {
/**
* 二分法
*
* @param n
* @return
*/
public static int firstBadVersion(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isBadVersion(mid)) {
if (mid > low && isBadVersion(mid - 1)) {
high = mid - 1;
} else {
return mid;
}
} else {
low = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(firstBadVersion(2126753390));
}
}
class VersionControl {
/**
* 测试数据,前1702766718个版本都不是错误版本,从第1702766719个版本开始都是错误版本
*/
public static boolean isBadVersion(int version) {
if (version < 1702766719) {
return false;
} else {
return true;
}
}
}复制
【每日寄语】 如果成功有捷径,那条路一定是坚持。
文章转载自明日之X,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。
评论
相关阅读
2025年4月中国数据库流行度排行榜:OB高分复登顶,崖山稳驭撼十强
墨天轮编辑部
2457次阅读
2025-04-09 15:33:27
数据库国产化替代深化:DBA的机遇与挑战
代晓磊
1131次阅读
2025-04-27 16:53:22
2025年3月国产数据库中标情况一览:TDSQL大单622万、GaussDB大单581万……
通讯员
813次阅读
2025-04-10 15:35:48
2025年4月国产数据库中标情况一览:4个千万元级项目,GaussDB与OceanBase大放异彩!
通讯员
644次阅读
2025-04-30 15:24:06
数据库,没有关税却有壁垒
多明戈教你玩狼人杀
563次阅读
2025-04-11 09:38:42
天津市政府数据库框采结果公布,7家数据库产品入选!
通讯员
548次阅读
2025-04-10 12:32:35
国产数据库需要扩大场景覆盖面才能在竞争中更有优势
白鳝的洞穴
527次阅读
2025-04-14 09:40:20
最近我为什么不写评论国产数据库的文章了
白鳝的洞穴
502次阅读
2025-04-07 09:44:54
【活动】分享你的压箱底干货文档,三篇解锁进阶奖励!
墨天轮编辑部
451次阅读
2025-04-17 17:02:24
一页概览:Oracle GoldenGate
甲骨文云技术
449次阅读
2025-04-30 12:17:56