資訊專(zhuān)欄INFORMATION COLUMN
摘要：不幸的是，你的產(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ò)誤的版本之后的所有版本都是錯(cuò)的。
假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。
你可以通過(guò)調(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ò)誤的版本。
代碼實(shí)現(xiàn)// 二分查找變種
/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let l = 1, r = n;
while(l <= r) {
let mid = l + Math.floor((r-l)/2);
if(isBadVersion(mid))
r = mid-1;
else
l = mid+1;
}
return l;
};
};
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/97243.html
摘要：在掘金上看到了一位大佬發(fā)了一篇很詳細(xì)的面試記錄文章一年半經(jīng)驗(yàn)，百度有贊阿里面試總結(jié)，為了查漏補(bǔ)缺，抽空就詳細(xì)做了下。 在掘金上看到了一位大佬發(fā)了一篇很詳細(xì)的面試記錄文章-《一年半經(jīng)驗(yàn)，百度、有贊、阿里面試總結(jié)》，為了查漏補(bǔ)缺，抽空就詳細(xì)做了下。（估計(jì)只有我這么無(wú)聊了哈哈哈） 有給出的或者有些不完善的答案，也盡力給出/完善了（可能有錯(cuò)，大家自行辨別）。有些很困難的題目（例如實(shí)現(xiàn)Promi...
摘要：在掘金上看到了一位大佬發(fā)了一篇很詳細(xì)的面試記錄文章一年半經(jīng)驗(yàn)，百度有贊阿里面試總結(jié)，為了查漏補(bǔ)缺，抽空就詳細(xì)做了下。 在掘金上看到了一位大佬發(fā)了一篇很詳細(xì)的面試記錄文章-《一年半經(jīng)驗(yàn)，百度、有贊、阿里面試總結(jié)》，為了查漏補(bǔ)缺，抽空就詳細(xì)做了下。（估計(jì)只有我這么無(wú)聊了哈哈哈） 有給出的或者有些不完善的答案，也盡力給出/完善了（可能有錯(cuò)，大家自行辨別）。有些很困難的題目（例如實(shí)現(xiàn)Promi...
摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問(wèn)題的約束。四題目分析貪心算法，總是做出在當(dāng)前看來(lái)是最好的選擇，不從整體最優(yōu)上加以考慮，也就是說(shuō)，只關(guān)心當(dāng)前最優(yōu)解，按照貪心策略，不關(guān)心以后，我們只關(guān)心當(dāng)前利益。 一、寫(xiě)在前面 為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數(shù)人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中...
閱讀 2322·2021-11-24 09:39
閱讀 3055·2021-10-15 09:39
閱讀 3106·2021-07-26 23:38
閱讀 2301·2019-08-30 11:14
閱讀 3420·2019-08-29 16:39
閱讀 1723·2019-08-29 15:23
閱讀 791·2019-08-29 13:01
閱讀 2673·2019-08-29 12:29
