您现在的位置：程式師世界 >> 編程語言 > >> 更多編程語言 >> Python

＜LeetCode天梯＞Day036 第一個錯誤的版本（二分查找法） | 初級算法 | Python

編輯：Python

每天進步一點點，就已經很棒很棒了，堅持堅持，不要太累，拒絕內卷，從每日一練開始，每天十分鐘，快樂生活一輩子！疫情依舊反復，大家帶好口罩啊~ 繼續繼續，來，今天和車神哥一起來提升自己的Python編程和面試能力吧，刷天梯~

放上我拍的Photo吧！

每日推薦一首歌：稻香——Jay Chou

以下為我的天梯積分規則：

每日至少一題：一題積分+10分
若多做了一題（或多一種方法解答），則當日積分+20分（+10+10）
若做了三道以上，則從第三題開始算+20分（如：做了三道題則積分-10+10+20=40；做了四道題則積分–10+10+20+20=60）
初始分為100分
若差一天沒做題，則扣積分-10分（周六、周日除外注：休息）
堅持！！！

初級算法

刷題目錄

鏈表

題干

你是產品經理，目前正在帶領一個團隊開發新的產品。不幸的是，你的產品的最新版本沒有通過質量檢測。由於每個版本都是基於之前的版本開發的，所以錯誤的版本之後的所有版本都是錯的。

假設你有 n 個版本 [1, 2, …, n]，你想找出導致之後所有版本出錯的第一個錯誤的版本。

你可以通過調用 bool isBadVersion(version) 接口來判斷版本號 version 是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。

示例1：

輸入：n = 5, bad = 4
輸出：4
解釋：
調用 isBadVersion(3) -> false
調用 isBadVersion(5) -> true
調用 isBadVersion(4) -> true
所以，4 是第一個錯誤的版本。

示例2：

輸入：n = 1, bad = 1
輸出：1

二分查找法

分析：

是不是看這題目有點懵逼，就離譜。
但是細看好像又不是很難，我們用二分法來減少測試接口調用的次數，取中位數。不斷是試探，判斷是否是False，然後再不斷縮小區間，最終找到版本號。

# The isBadVersion API is already defined for you.# @param version, an integer# @return an integer# def isBadVersion(version):class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ # 二分搜索法 st = 0 end = n while st <= end: mid = st + (end - st)//2 if isBadVersion(mid): end = mid - 1 else: st = mid + 1 return st

好像就只有這麼解答了吧，兩天兩題，刷完排序和查找。