美文网首页
LeetCodeDay18 —— 第一个错误的版本

LeetCodeDay18 —— 第一个错误的版本

作者: GoMomi | 来源:发表于2018-04-26 19:32 被阅读0次

    278. 第一个错误的版本

    描述
    • 你是产品经理,目前正在领导一个团队开发一个新产品。不幸的是,您的产品的最新版本没有通过质量检查。由于每个版本都是基于之前的版本开发的,所以错误版本之后的所有版本都是不好的。
    说明
    • 假设你有 n 个版本 [1, 2, ..., n],你想找出第一个错误的版本,导致下面所有的错误。
    • 你可以通过 bool isBadVersion(version) 的接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。您应该尽量减少对 API 的调用次数。
    思路
    1. 题目进行了一个包装,本质就是在排序的列表中找到一个数,因此利用二分查找即可。
    2. 要注意与二分查找不同的是 end = mid 而不是 mid - 1。每次找到的BadVesion是一个待选版本,不能抛弃。
    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    class Solution_278 {
     public:
      int firstBadVersion(int n) {
        int start = 1, end = n;
        while(start < end){
          int mid = start + (end - start) / 2;
          if(isBadVersion(mid)) end = mid;
          else start = mid + 1;
        }
        return start == end ? start : -1;
      }
    };
    

    相关文章

      网友评论

          本文标题:LeetCodeDay18 —— 第一个错误的版本

          本文链接:https://www.haomeiwen.com/subject/cvimlftx.html