程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 278 First Bad Version(第一個壞版本)(二分法)(*)

LeetCode 278 First Bad Version(第一個壞版本)(二分法)(*)

編輯:C++入門知識

LeetCode 278 First Bad Version(第一個壞版本)(二分法)(*)


翻譯

你是一個產品經理,目前正在帶領團隊去開發一個新產品。

不幸的是,產品的上一個版本沒有通過質量檢測。

因為每個版本都是建立在前一個版本基礎上開發的,所以壞版本之後的版本也都是壞的。

假設你有n個版本[1,2,...,n],並且你想找出造成後面所有版本都變壞的第一個壞版本。

給你一個API——bool isBadVersion(version),它能夠確定一個版本是否是壞的。

實現一個函數去找出第一個壞版本。

你應該盡可能少地去調用這個API。

原文

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.

分析

其實題目說了這麼多,解出來只需要用二分法就夠了,只不過中間挺容易出錯的。

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (isBadVersion(mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

今天寫的第六道題了,好累哎……

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved