278 - 第一个错误的版本(first-bad-version)

Create by jsliang on 2019-07-19 10:08:17
Recently revised in 2019-07-19 11:37:57

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 知识点
七 解题思路
八 进一步思考

二 前言

返回目录

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

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

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

示例:

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

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

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

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码
var solution = function (isBadVersion) {
  return function (n) {
    let i = 1,
        j = n;
    while (i <= j) {
      let mid = parseInt((j - i) / 2) + i;
      if (isBadVersion(mid)) {
        j = mid - 1;
      } else {
        i = mid + 1;
      }
    }
    return i;
  };
};

五 LeetCode Submit

返回目录

✔ Accepted
  ✔ 22/22 cases passed (60 ms)
  ✔ Your runtime beats 99.6 % of javascript submissions
  ✔ Your memory usage beats 40 % of javascript submissions (33.7 MB)

六 知识点

返回目录

  1. parseInt()parseInt(string, radix)string 为字符串,radix 为介于 2-36 之间的数。使用者告诉这个函数 string(比如 11)是 radix(比如 2 )进制的,函数将固定返回 string 以十进制时显示的数(3)。parseInt() 详细介绍

七 解题思路

返回目录

三分天下,二分算法

首先,今天先回顾下二分法:

[1, 2, 3, 4, 5]

假设有个数组如上所示,我们需要快速定位 4 的位置。

如果我们通过遍历,那么需要走的路是:1 -> 2 -> 3 -> 4。

那么使用二分法怎么查找呢?3 -> 4。

怎么理解呢?二分法,就是不停地比较目标和中间数:

  1. 目标 4。先获取数组 [1,2,3,4,5] 的中间值,即 3。跟 4 进行比较,而 3 比 4 小,所以数组范围缩小为:[3,4,5]
  2. 目标 4。再对数组 [3,4,5] 进行中间值对比,即 4。跟 4 进行比较,刚好找到值,从而返回结果。

这样,小伙伴们应该清楚二分法了。

然后,咱们根据题意,结合二分法进行解析:

var solution = function (isBadVersion) {
  return function (n) {
    let i = 1,
        j = n;
    while (i <= j) {
      let mid = parseInt((j - i) / 2) + i;
      if (isBadVersion(mid)) {
        j = mid - 1;
      } else {
        i = mid + 1;
      }
    }
    return i;
  };
};

假设有 [1, 2, 3, 4, 5] 共 5 个版本,然后我们先取中,通过 isBadVersion(3) 判断,返回 false,即这个版本是没有错误的版本,所以数组缩短到 [4, 5]

这时候,i = 4, j = 5,计算出 mid = 4,这时候 isBadVersion(4) 返回 true,所以数组变成 [4, 4]

到此,i === j,所以还要再执行一次循环,从而得到结果:i = 4, j = 3,从而得到结果为 4

最后,我们将 4 给返回出去即可。

八 进一步思考

返回目录

小伙伴可能还抱有幻想,我们直接遍历也是可行的啊:

var solution = function (isBadVersion) {
    return function (n) {
        for (let i = 1; i < n; i++) {
            if (isBadVersion(i)) {
                return i;
            }
        }
        return n;
    };
};

抱歉,LeetCode 就是来打击你的,人家的版本提交了 2126753390 次,错误的在 1702766719 版本,然后毫不客气地告诉你:

✘ Time Limit Exceeded
  ✘ 11/22 cases passed (N/A)
  ✘ testcase: '2126753390\n1702766719'
  ✘ answer: 
  ✘ expected_answer: 
  ✘ stdout:

尊敬的 LeetCode 官方,请告诉我,哪家的版本有这么多了,从远古时代开始提交的么?!


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-19 11:37:57

results matching ""

    No results matching ""