<small id="eycio"></small>

<fieldset id="eycio"></fieldset>

[Leetcode] First Bad Version 第一個錯誤版本

senntyou 發布于2019-08-14 12:33 / 952人閱讀

摘要：二分搜索法復雜度時間空間思路因為一個版本是錯誤，其后面的所有版本都是錯誤的，所以我們可以用二分搜索，當取中點時，如果中點是錯誤版本，說明后面都是錯誤的，那第一個錯誤版本肯定在前面。如果中點不是錯誤版本，說明第一個錯誤版本肯定在后面。

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.

二分搜索法 復雜度

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

思路

因為一個版本是錯誤，其后面的所有版本都是錯誤的，所以我們可以用二分搜索，當取中點時，如果中點是錯誤版本，說明后面都是錯誤的，那第一個錯誤版本肯定在前面。如果中點不是錯誤版本，說明第一個錯誤版本肯定在后面。

注意

這里直接使用min <= max的二分模板，因為我們其實要找的是好和壞的分界點，即這個點既不是好也不是壞，所以是找不到的，按照模板的特點，最后退出循環時，max指向小于目標的點，min指向大于目標的點，這里第一個壞的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;
    }
}

云服務器 GPU云服務器 version版本號第一個數據第一個頂級域名 php第一個字符

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64555.html

【刷算法】LeetCode.278-第一個錯誤的版本

摘要：不幸的是，你的產品的最新版本沒有通過質量檢測。由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的。假設你有個版本，你想找出導致之后所有版本出錯的第一個錯誤的版本。示例給定，并且是第一個錯誤的版本。題目描述你是產品經理，目前正在帶領一個團隊開發新的產品。不幸的是，你的產品的最新版本沒有通過質量檢測。由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有...

JerryC 2019-08-23 11:38 評論0 收藏0
[LeetCode/LintCode] First Bad Version

摘要：分析最后一次循環的時刻當與相差小于時，總是那么如果是，下一次直接跳出循環，返回當與相差大于時，是，變成，如果是，循環結束的條件將是循環結束，返回 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 2019-08-15 15:46 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字?？偨Y本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0