LeetCode | 0278. First Bad Version第一個(gè)錯(cuò)誤的版本【Python】

LeetCode 0278. First Bad Version第一個(gè)錯(cuò)誤的版本【Easy】【Python】【二分】

Problem

LeetCode

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.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

問題

力扣

你是產(chǎn)品經(jīng)理斥废,目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是,你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)成艘。由于每個(gè)版本都是基于之前的版本開發(fā)的讹弯,所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的土浸。

假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]昼弟,你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。

你可以通過調(diào)用 bool isBadVersion(version) 接口來(lái)判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)普办。實(shí)現(xiàn)一個(gè)函數(shù)來(lái)查找第一個(gè)錯(cuò)誤的版本工扎。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)。

示例:

給定 n = 5衔蹲,并且 version = 4 是第一個(gè)錯(cuò)誤的版本肢娘。

調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true

所以,4 是第一個(gè)錯(cuò)誤的版本舆驶。 

思路

二分查找

因?yàn)榘姹臼菑?1 到 n橱健,所以 low 初值設(shè)為 1,high 初值設(shè)為 n沙廉。

時(shí)間復(fù)雜度: O(logn)
空間復(fù)雜度: O(1)

Python代碼

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        low, high = 1, n  # 1-n
        while low <= high:
            mid = int((low + high) / 2)
            if isBadVersion(mid) == False:
                low = mid + 1
            else:
                high = mid - 1
        return low

代碼地址

GitHub鏈接

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末畴博,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子蓝仲,更是在濱河造成了極大的恐慌,老刑警劉巖官疲,帶你破解...
    沈念sama閱讀 219,539評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件袱结,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡途凫,警方通過查閱死者的電腦和手機(jī)垢夹,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,594評(píng)論 3 396
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)维费,“玉大人果元,你說(shuō)我怎么就攤上這事∠耍” “怎么了而晒?”我有些...
    開封第一講書人閱讀 165,871評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)阅畴。 經(jīng)常有香客問我倡怎,道長(zhǎng),這世上最難降的妖魔是什么贱枣? 我笑而不...
    開封第一講書人閱讀 58,963評(píng)論 1 295
  • 正文 為了忘掉前任监署,我火速辦了婚禮,結(jié)果婚禮上纽哥,老公的妹妹穿的比我還像新娘钠乏。我一直安慰自己,他們只是感情好春塌,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,984評(píng)論 6 393
  • 文/花漫 我一把揭開白布晓避。 她就那樣靜靜地躺著簇捍,像睡著了一般。 火紅的嫁衣襯著肌膚如雪够滑。 梳的紋絲不亂的頭發(fā)上垦写,一...
    開封第一講書人閱讀 51,763評(píng)論 1 307
  • 那天,我揣著相機(jī)與錄音彰触,去河邊找鬼梯投。 笑死,一個(gè)胖子當(dāng)著我的面吹牛况毅,可吹牛的內(nèi)容都是我干的分蓖。 我是一名探鬼主播,決...
    沈念sama閱讀 40,468評(píng)論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼尔许,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼么鹤!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起味廊,我...
    開封第一講書人閱讀 39,357評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤蒸甜,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后余佛,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體柠新,經(jīng)...
    沈念sama閱讀 45,850評(píng)論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,002評(píng)論 3 338
  • 正文 我和宋清朗相戀三年辉巡,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了恨憎。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,144評(píng)論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡郊楣,死狀恐怖憔恳,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情净蚤,我是刑警寧澤钥组,帶...
    沈念sama閱讀 35,823評(píng)論 5 346
  • 正文 年R本政府宣布,位于F島的核電站今瀑,受9級(jí)特大地震影響者铜,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜放椰,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,483評(píng)論 3 331
  • 文/蒙蒙 一作烟、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧砾医,春花似錦拿撩、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,026評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)影暴。三九已至,卻和暖如春探赫,著一層夾襖步出監(jiān)牢的瞬間型宙,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,150評(píng)論 1 272
  • 我被黑心中介騙來(lái)泰國(guó)打工伦吠, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留妆兑,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,415評(píng)論 3 373
  • 正文 我出身青樓毛仪,卻偏偏與公主長(zhǎng)得像搁嗓,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子箱靴,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,092評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容