成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

[Leetcode] First Bad Version 第一個(gè)錯(cuò)誤版本

senntyou / 998人閱讀

摘要：二分搜索法復(fù)雜度時(shí)間空間思路因?yàn)橐粋€(gè)版本是錯(cuò)誤，其后面的所有版本都是錯(cuò)誤的，所以我們可以用二分搜索，當(dāng)取中點(diǎn)時(shí)，如果中點(diǎn)是錯(cuò)誤版本，說(shuō)明后面都是錯(cuò)誤的，那第一個(gè)錯(cuò)誤版本肯定在前面。如果中點(diǎn)不是錯(cuò)誤版本，說(shuō)明第一個(gè)錯(cuò)誤版本肯定在后面。

First Bad Version 
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.
二分搜索法 復(fù)雜度

時(shí)間 O(logN) 空間 O(1)

思路

因?yàn)橐粋€(gè)版本是錯(cuò)誤，其后面的所有版本都是錯(cuò)誤的，所以我們可以用二分搜索，當(dāng)取中點(diǎn)時(shí)，如果中點(diǎn)是錯(cuò)誤版本，說(shuō)明后面都是錯(cuò)誤的，那第一個(gè)錯(cuò)誤版本肯定在前面。如果中點(diǎn)不是錯(cuò)誤版本，說(shuō)明第一個(gè)錯(cuò)誤版本肯定在后面。

注意

這里直接使用min <= max的二分模板，因?yàn)槲覀兤鋵?shí)要找的是好和壞的分界點(diǎn)，即這個(gè)點(diǎn)既不是好也不是壞，所以是找不到的，按照模板的特點(diǎn)，最后退出循環(huán)時(shí)，max指向小于目標(biāo)的點(diǎn)，min指向大于目標(biāo)的點(diǎn)，這里第一個(gè)壞的version較大，所以返回min

代碼 
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int min = 1, max = n, mid = 0;
        while(min <= max){
            mid = min + (max - min) / 2;
            if(isBadVersion(mid)){
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64555.html

相關(guān)文章

  • 【刷算法】LeetCode.278-第一個(gè)錯(cuò)誤的版本

    摘要：不幸的是，你的產(chǎn)品的最新版本沒(méi)有通過(guò)質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開(kāi)發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。假設(shè)你有個(gè)版本，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。示例給定，并且是第一個(gè)錯(cuò)誤的版本。 題目描述 你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開(kāi)發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒(méi)有通過(guò)質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開(kāi)發(fā)的，所以錯(cuò)誤的版本之后的所有...

    JerryC 評(píng)論0 收藏0

  • [LeetCode/LintCode] First Bad Version

    摘要：分析最后一次循環(huán)的時(shí)刻當(dāng)與相差小于時(shí)，總是那么如果是，下一次直接跳出循環(huán)，返回當(dāng)與相差大于時(shí)，是，變成，如果是，循環(huán)結(jié)束的條件將是循環(huán)結(jié)束，返回 Problem The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case,...

    lowett 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...

    tain335 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線(xiàn)網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線(xiàn)網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • LeetCode 精選TOP面試題【51 ~ 100】

    摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問(wèn)題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...

    Clect 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<