leetcode278-第一个错误的版本

原题

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

假设你有 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) {
        int start = 1;
        int end = n;
        int mid;
        while(start<end){
            mid = start + (end-start)/2;
            if(isBadVersion(mid)) end = mid;
            else start = mid+1;
        }
        return start;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode278-%e7%ac%ac%e4%b8%80%e4%b8%aa%e9%94%99%e8%af%af%e7%9a%84%e7%89%88%e6%9c%ac/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月1日
下一篇 2020年1月3日

相关推荐

  • leetcode13-罗马数字转整数

    原题 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2…

    算法 2020年4月25日
    080
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0110
  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode19-删除链表的倒数第N个节点

    原题 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为…

    算法 2019年12月15日
    090
  • 剑指offer62-圆圈中最后剩下的数字

    原题(来源Leetcode) 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如,0、1、2、3、4这5…

    算法 2020年3月30日
    0640
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0100
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • 程序员面试金典17.16-按摩师

    原题(来源Leetcode) 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,…

    算法 2020年3月24日
    0630
  • leetcode322-零钱兑换

    原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1…

    算法 2020年3月8日
    0130
  • leetcode494-目标和

    原题 给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。…

    算法 2019年12月12日
    080

发表回复

登录后才能评论