文档章节

LeetCode(63)-First Bad Version

fengsehng
 fengsehng
发布于 2016/11/09 09:16
字数 256
阅读 0
收藏 0

题目:

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.

思路:

  • 题意:给定1~n个数字代表产品,其中一个产品坏了,后面的全坏,要求检测第一个坏的(提供了函数)
  • 二分法,这里的二分法判断条件比较特殊,当然后面的设置变量要用long,没想明白

代码:

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
         long begin = 1;  
        long end = n;  
        if(n<1) return 0;  
        while(begin<end){  
            long mid = (begin+end)/2;  
            if(isBadVersion((int)mid)){  
                end = mid-1;  
            }else{  
                begin = mid+1;  
            }  
        }  
        if(isBadVersion((int)begin)) return (int)begin;  
        return (int)begin+1;  
    }
}

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 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:First Bad Version - 第一个坏版本

1、题目名称 First Bad Version(第一个坏版本) 2、题目地址 https://leetcode.com/problems/first-bad-version/ 3、题目内容 英文: You are a product manager and currently leading a ......

北风其凉
2015/09/13
1K
0
278. First Bad Version - LeetCode

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

yysue
08/07
0
0
Leetcode日记6

(2015/11/28) LeetCode 303 Range Sum Query - Immutable:(Easy) 1)超时的算法:每次调用sumRange函数进行一次累加运算。 2)不超时的算法:改变数组的内容,存储从0下标到当前下标所有...

fxdhdu
2015/11/28
73
0
Leetcode日记7

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

fxdhdu
2016/01/03
48
0

没有更多内容

加载失败,请刷新页面

加载更多

ppwjs之bootstrap文字排版:字体大小写设置

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
20分钟前
0
0
线性代数入门

线性代数的概念对于理解机器学习背后的原理非常重要,尤其是在深度学习领域中。它可以帮助我们更好地理解算法内部到底是怎么运行的,借此,我们就能够更好的做出决策。所以,如果你真的希望了...

牛奋Debug
35分钟前
0
0
开发5分钟,调试2小时 - 该如何debug?

几年来我在答疑群、论坛、公众号、知乎回答的各种问题,没有一万也有八千。其中有三分之二以上都是在帮人看报错,帮人 debug(调试代码)。 可以说,会不会 debug,有没有 debug 的意识,懂不...

crossin
35分钟前
0
1
SQL count(*) 和count(1)的区别

开发中经常会使用这两个聚合函数,作用都是用来统计记录行,今天查找资料发现,其实这两个函数并没有区别, 实践才是检验的标准,首先看执行计划(表是我自己建立的): 可以看到,两个执行计...

一曲图森破
40分钟前
1
0
区块链100讲:详解区块链之P2P网络

1 P2P网络 如果我们简单来看 P2P 技术,它的应用领域已经非常广泛了,从流媒体到点对点通讯、从文件共享到协同处理,多种领域都有它的身影出现。 同样的,P2P 的网络协议也有很多,比较常见的...

HiBlock
57分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部