写点什么

LeetCode 第一个错误版本使用 JavaScript 解题

作者:大师兄
  • 2022 年 10 月 11 日
    北京
  • 本文字数:824 字

    阅读完需:约 3 分钟

有人相爱,有人夜里开车看海,我是 leetcode 第一题都做不出来

第一个错误版本

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


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


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


输入:n = 5, bad = 4

输出:4

解释:

调用 isBadVersion(3) -> false

调用 isBadVersion(5) -> true

调用 isBadVersion(4) -> true


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

解题思路

当一个版本为正确版本,则该版本之前的所有版本均为正确版本;


当一个版本为错误版本,则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。左边界值左边全是正确的,右边界值右边全是错误的



  • 第一步:获取边界值,只要左边界值小于右边界值就开始进入循环

  • 第二步:获取中间值,进行判断是不是错误版本

  • 第三步:如果是错误版本,则说明中间值右边边全是错误版本,在区间[left,mid]中间寻找;此中间值就是右边界值;如果是正确版本,则左侧全是正确版本,在区间[mid+1,right]中查找


var solution = function(isBadVersion) {  return function(n) {    // 是从1开始的    let left = 1,right = n;    while (left < right) {        // 获取中间版本      let mid = Math.floor((right - left)/2 + left);      if (isBadVersion(mid)) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  };};
复制代码



知识点

  • Math.floor是向下取整,返回小于或等于一个给定数字的最大整数。


为什么取中间值要用(right - left)/2 + left而不用(right + left)/2?


这是因为 left或者right都不会造成溢出,但是right + left就不一定了,可能会造成溢出

发布于: 刚刚阅读数: 4
用户头像

大师兄

关注

分享各种前端知识 2021.03.04 加入

欢迎关注公众号:前端实验室 分享面经,新技术,实战项目,一起来折腾吧

评论

发布
暂无评论
LeetCode第一个错误版本使用JavaScript解题_算法_大师兄_InfoQ写作社区