​LeetCode刷题实战278:第一个错误的版本

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 第一个错误的版本,我们先来看题面:
https://leetcode-cn.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 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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.


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

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

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


示例


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

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

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


解题

二分法解答

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

 
public class Solution extends VersionControl {
  public int firstBadVersion(int n) {
    if (isBadVersion(1)) {
      return 1;
    }
 
    int max = n;
    int min = 1;
    int record = 0;
    while (min < max) {
      record = max / 2 + min / 2;
      boolean rec = isBadVersion(record);
      if (rec) {
        max = record;
      } else {
        min = record + 1;
      }
    }
    return min;
  }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-260题汇总,希望对你有点帮助!
LeetCode刷题实战261:以图判树
LeetCode刷题实战262:行程和用户
LeetCode刷题实战263:丑数
LeetCode刷题实战264:丑数 II
LeetCode刷题实战265:粉刷房子II
LeetCode刷题实战266:回文排列
LeetCode刷题实战267:回文排列II
LeetCode刷题实战268:丢失的数字
LeetCode刷题实战269:火星词典
LeetCode刷题实战270:最接近的二叉搜索树值
LeetCode刷题实战271:字符串的编码与解码
LeetCode刷题实战272:最接近的二叉搜索树值 II
LeetCode刷题实战273:整数转换英文表示

LeetCode刷题实战274:H指数

LeetCode刷题实战275:H 指数 II

LeetCode刷题实战276:栅栏涂色

LeetCode刷题实战277:搜寻名人


​LeetCode刷题实战278:第一个错误的版本

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/11890.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息