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

JerryC 發布于2019-08-23 11:38 / 2043人閱讀

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

題目描述

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

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

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

示例:

給定 n = 5，并且 version = 4 是第一個錯誤的版本。

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

所以，4 是第一個錯誤的版本。

代碼實現

// 二分查找變種
/**
 * 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;
    };
};

GPU云服務器云服務器第一個提出人工智能概念的是誰第一個數據第一個頂級域名 php第一個字符

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

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

刷《一年半經驗，百度、有贊、阿里面試總結》·手記

摘要：在掘金上看到了一位大佬發了一篇很詳細的面試記錄文章一年半經驗，百度有贊阿里面試總結，為了查漏補缺，抽空就詳細做了下。在掘金上看到了一位大佬發了一篇很詳細的面試記錄文章-《一年半經驗，百度、有贊、阿里面試總結》，為了查漏補缺，抽空就詳細做了下。（估計只有我這么無聊了哈哈哈）有給出的或者有些不完善的答案，也盡力給出/完善了（可能有錯，大家自行辨別）。有些很困難的題目（例如實現Promi...

codeKK 2019-08-23 13:48 評論0 收藏0
刷《一年半經驗，百度、有贊、阿里面試總結》·手記

摘要：在掘金上看到了一位大佬發了一篇很詳細的面試記錄文章一年半經驗，百度有贊阿里面試總結，為了查漏補缺，抽空就詳細做了下。在掘金上看到了一位大佬發了一篇很詳細的面試記錄文章-《一年半經驗，百度、有贊、阿里面試總結》，為了查漏補缺，抽空就詳細做了下。（估計只有我這么無聊了哈哈哈）有給出的或者有些不完善的答案，也盡力給出/完善了（可能有錯，大家自行辨別）。有些很困難的題目（例如實現Promi...

NusterCache 2019-08-29 17:27 評論0 收藏0
【LeetCode】貪心算法--買賣股票的最佳時機 II（122）

摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法，總是做出在當前看來是最好的選擇，不從整體最優上加以考慮，也就是說，只關心當前最優解，按照貪心策略，不關心以后，我們只關心當前利益。一、寫在前面為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中...

xbynet 2019-07-31 11:21 評論0 收藏0