LeetCode #278 First Bad Version 第一個壞的版本

英文原文如下

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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

中文翻譯

你是一位產品經理而且現在正在帶領團隊開發新產品中。不幸的是，你們產品的最新版本在品質測試中失敗了。因為每一個版本都是基於前一個版本開發的，所以所有在一個壞版本後後面的所有版本都會是壞的。

假設你有 n 個版本 [1, 2, …, n] ，然後你想要找到第一個壞掉的版本，就是它導致接下來所有版本都壞掉的。

給予你一個 API bool isBadVersion(version) 會回傳該版本(version)是否為壞版本。實作一個函數來找到第一個壞版本，你需要將呼叫 API 的次數降到最低。

範例及題目限制

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

• 1 <= bad <= n <= 2³¹ – 1

解題思路

在這個問題中，我們需要使用API並找到第一個回傳為 true 的版本

當然，我們可以使用 for 的方式，從最前面或是最後面開始找，但那鐵定不會是最優解 – O(n)

故，我們在這裡也可以使用 binary search 的方式來降低找到的平均次數

C# 解決方案

方案1

/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int max =n;
        int min =0;

        while(min<max)
        {
            n = min+(max-min)/2;
            if(IsBadVersion(n))
            {
                max = n;
            }
            else
            {
                min = n+1;
            }
        }
        return max;
    }
}

時間複雜度: O(log n)

Java解決方案

方案1

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int max = n;
        int min = 0;

        while(min<max)
        {
            n = min+(max-min)/2;
            if(isBadVersion(n))
            {
                max = n;
            }
            else
            {
                min = n+1;
            }
        }
        return max;
    }
}

時間複雜度: O(log n)

結論

就跟程式一樣，要是前面的版本有Bug一直沒發現，後面的版本就容易全部壞掉呢~

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

⭐大力徵求合作邀約或是友站夥伴 ➡ 附上 2023網站回顧

題目連結 : First Bad Version – LeetCode

一些隨機的LeetCode文章