文档章节

LeetCode:First Bad Version - 第一个坏版本

北风其凉
 北风其凉
发布于 2015/09/13 10:25
字数 592
阅读 1289
收藏 1

1、题目名称

First Bad Version(第一个坏版本)

2、题目地址

https://leetcode.com/problems/first-bad-version/

3、题目内容

英文:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

中文:

假设你是一个领导团队开发新产品的项目经理,现在产品的最新版本没有通过质量检查,每个版本都是基于上一个版本开发的,如果有一个版本是坏版本,那么该版本后面的版本也是坏版本。假设现在你的产品有n个版本(从1到n),你现在需要找出第一个坏版本的位置,这个版本是导致后面版本都是坏版本的元凶。

题目中提供了一个返回值为布尔型的API函数isBadVersion,这个函数会返回某个版本号对应的版本是否是坏版本。写一个函数找出第一个坏版本,你需要将你调用API函数的次数降到最低。

4、解题方法

由于版本号是从1开始,一直到n,属于增序排列,因此可以采用二分查找的策略,减少比较次数。需要注意的是,在取二分查找的中间值时,不要使用左右相加后再除以2的方式,这样可能会在计算时产生溢出。

一段实现此方法的Java代码如下:

/**
 * 功能说明:LeetCode 278 - First Bad Version
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月13日
 */
public class Solution extends VersionControl {
    
    /**
     * 找到第一个坏版本
     * @param n 总版本数
     * @return 第一个坏版本的序号
     */
    public int firstBadVersion(int n) {
        
        if (n <= 0) {
            return 0;
        }

        if (isBadVersion(1)) {
            return 1;
        } else if (!isBadVersion(n)) {
            return Integer.MAX_VALUE;
        }
        
        int left = 1;
        int right = n;
        
        
        int mid;
        while (true) {
            mid = left + (right - left) / 2; //注意 left + right 有可能超过了整数的最大值
            if (mid == left) {
                return right;
            }
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
    }
}

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 118
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
278. First Bad Version - LeetCode

Question 278. First Bad Version Solution 题目大意:产品有5个版本1,2,3,4,5其中下一个版本依赖上一个版本,即版本4是坏的,5也就是坏的,现在要求哪个版本是第一个坏的。 思路:二分法...

yysue
2018/08/07
0
0
LeetCode算法题-First Bad Version(Java实现-三种解法)

这是悦乐书的第200次更新,第210篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第66题(顺位题号是278)。您是产品经理,目前领导团队开发新产品。不幸的是,您产品的最新版本...

小川94
2018/12/13
0
0
First Bad Version(leetcode278)

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is......

woshixin
2018/12/12
0
0
[LeetCode] First Bad Version

题目 https://leetcode.com/problems/first-bad-version/ You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your ......

u013553529
2017/11/25
0
0
Leetcode日记7

(2015/1/2) LeetCode 318 Maximum Product of Word Lengths 题目: 1)求一个字符串数组中,两个不同的字符串的长度乘积的最大值。 2)这两个字符串不能共同拥有同一个字符。(两个字符串的...

fxdhdu
2016/01/03
48
0

没有更多内容

加载失败,请刷新页面

加载更多

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

import java.util.Arrays; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { Arrays.sort(array); int count=0; for(int i=0;i<array.le......

南桥北木
8分钟前
0
0
关于FLAG_ACTIVITY_NEW_TASK的使用

参考文章: https://blog.csdn.net/u010389391/article/details/78558475 Context调用startActivity, 有部分情况会报出如下错误: Caused by: android.util.AndroidRuntimeException: Calli......

Gemini-Lin
24分钟前
0
0
Python开发工具:Webware for Python

原文来之:https://www.oschina.net/p/webware+for+python 前言 Webware for Python 是一组 Python 包和工具用来开发面向对象的 Web 应用。良好的设计模式,包含一个快速的应用服务器、Servl...

A_裙232550246
32分钟前
0
0
高并发场景下的缓存有哪些常见的问题?

一、缓存一致性问题 当数据时效性要求很高时,需要保证缓存中的数据与数据库中的保持一致,而且需要保证缓存节点和副本中的数据也保持一致,不能出现差异现象。 这就比较依赖缓存的过期和更新...

别打我会飞
47分钟前
3
0
List list = new ArrayList()为何父类引用指向子类对象(多态)

态:要有继承,方法的重写,父类引用指向子类对象 疑问一:父类引用指向子类对象 与指向父类对象 Animal cat = new Cat(); //向上转型。 父类引用指向子类对象,该引用不能再访问子类新增加的...

architect刘源源
48分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部