文档章节

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
朝阳
程序员
私信 提问
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: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
2018/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

没有更多内容

加载失败,请刷新页面

加载更多

20个使用 Java CompletableFuture的例子

https://colobu.com/2018/03/12/20-Examples-of-Using-Java%E2%80%99s-CompletableFuture/

lemos
41分钟前
1
0
Apache 流框架 Flink,Spark Streaming,Storm对比分析

1.Flink架构及特性分析 Flink是个相当早的项目,开始于2008年,但只在最近才得到注意。Flink是原生的流处理系统,提供high level的API。Flink也提供 API来像Spark一样进行批处理,但两者处理...

hblt-j
44分钟前
1
0
什么是公网IP、内网IP和NAT转换?

搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网IP地址)和内网IP(即局域网IP地址),但他们的区别是什么? 1、引言 搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网I...

linuxprobe16
50分钟前
2
0
Spring Cloud搭建微服务架构----流量回放

前言 系统微服务化后,传统的自测/测试方式都变得比较困难: 依赖的服务可能不稳定。 服务无法提供期望的响应数据。 缺少场景构造标准。 随着整体业务越来越复杂,微服务依赖的越来越多,测试...

春哥大魔王的博客
今天
4
0
记一次springboot模块配置问题导致读取Apollo配置中心配置文件始终错误的问题

现在正在做的一个项目采用的是微服务,主框架是spring cloud,配置中心用的是携程的Apollo。 项目下有多个服务,在测试服务器上启动用户服务的时候发现在eureka中心另一个服务被启动了,尝试...

zcqshine
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部