【刷算法】LeetCode.278-第一个错误的版本

JerryC 发布于2019-08-23 11:38 / 1975人阅读

摘要：不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有个版本，你想找出导致之后所有版本出错的第一个错误的版本。示例给定，并且是第一个错误的版本。

题目描述

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

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

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

示例:

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

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

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

代码实现

// 二分查找变种
/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
      let l = 1, r = n;
      while(l <= r) {
        let mid = l  + Math.floor((r-l)/2);
        if(isBadVersion(mid))
          r = mid-1;
        else 
          l = mid+1;
      }
      
      return l;
    };
};

GPU云服务器云服务器第一个提出人工智能概念的是谁第一个数据第一个顶级域名 php第一个字符

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97243.html

刷《一年半经验，百度、有赞、阿里面试总结》·手记

摘要：在掘金上看到了一位大佬发了一篇很详细的面试记录文章一年半经验，百度有赞阿里面试总结，为了查漏补缺，抽空就详细做了下。在掘金上看到了一位大佬发了一篇很详细的面试记录文章-《一年半经验，百度、有赞、阿里面试总结》，为了查漏补缺，抽空就详细做了下。（估计只有我这么无聊了哈哈哈）有给出的或者有些不完善的答案，也尽力给出/完善了（可能有错，大家自行辨别）。有些很困难的题目（例如实现Promi...

codeKK 2019-08-23 13:48 评论0 收藏0
刷《一年半经验，百度、有赞、阿里面试总结》·手记

摘要：在掘金上看到了一位大佬发了一篇很详细的面试记录文章一年半经验，百度有赞阿里面试总结，为了查漏补缺，抽空就详细做了下。在掘金上看到了一位大佬发了一篇很详细的面试记录文章-《一年半经验，百度、有赞、阿里面试总结》，为了查漏补缺，抽空就详细做了下。（估计只有我这么无聊了哈哈哈）有给出的或者有些不完善的答案，也尽力给出/完善了（可能有错，大家自行辨别）。有些很困难的题目（例如实现Promi...

NusterCache 2019-08-29 17:27 评论0 收藏0
【LeetCode】贪心算法--买卖股票的最佳时机 II（122）

摘要：贪心算法每一步必须满足一下条件可行的即它必须满足问题的约束。四题目分析贪心算法，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，也就是说，只关心当前最优解，按照贪心策略，不关心以后，我们只关心当前利益。一、写在前面为什么要在LeetCode刷题？大家都知道不管是校招还是社招算法题是必考题，而这一部分恰巧是大多数人的短板，所以刷题首先是为了提高自身的编程能力，能够在算法面试中...

xbynet 2019-07-31 11:21 评论0 收藏0