【LeetCode】278. First Bad Version 解答・解説【Python】

はじめに
問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
1. 解答1：
補足・参考・感想

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

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

1
2
3
4
5
6
7

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

1
2

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

Constraints:

1 <= bad <= n <= 2³¹ - 1

内容

あなたはプロダクトマネージャーであり、新製品の開発チームを率いています。

残念なことに、最新バージョンの品質チェックにsっ敗しました。

各バージョンは前のバージョンに基づいて開発されているからです。悪いバージョンがあるとそれ以降のバージョンは全て悪いものになります。

n個のバージョン[1,2,・・・,n]があるとすると、最初の悪いバージョンを見つけるとそれ以降のバージョンも全て悪くなります。

バージョンが悪いかを返すAPI isBadVersion(version)が与えられます。

最初の悪いバージョンを見つける関数を実装してください。

APIを呼び出す数を最小限にする必要があります。

※正しくない可能性があります。

方針

前提

二分探索を使う
最初の悪いバージョン以降は全て悪いバージョンになることを踏まえる

実装のイメージ

・バージョンの集合nに対して二分探索をかける

・middleはバージョン番号であり、middleをAPIにかけてTrue/Falseを調べる

→Falseの場合は前提2より、現在位置よりも右側に悪いバージョンがあるので、left = middle+1とする

→Trueの場合は、前提2より、現在位置よりも左端に悪いバージョンがあるので、right = middle-1とする

・最初の悪いバージョンを見つけたときの動き

→最初の悪いバージョンを見つけたので、right = middle-1とし、resultにmiddleを入れる

→次の探索範囲には悪いバージョンはない。APIはFalseとなるので、left = middle+1とする

→この後left<=rightの条件を外れすまで上記を繰り返す

解答

解答1：

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        return self.binary_search(n)

    def binary_search(self,n):
        left = 0
        right = n
        result = 0
        
        while left <= right:
            middle = (left+right)//2
            if isBadVersion(middle) is False:
                left = middle+1
            else:
                right = middle-1
                result = middle
        
        return result

# The isBadVersion API is already defined for you.

# def isBadVersion(version: int) -> bool:

class Solution:

def firstBadVersion(self, n: int) -> int:

return self.binary_search(n)

def binary_search(self,n):

left = 0

right = n

result = 0

while left <= right:

middle = (left+right)//2

if isBadVersion(middle) is False:

left = middle+1

else:

right = middle-1

result = middle

return result

悪いバージョンであるかはisBadVersionで判定にかけることで判断できる。

ただし、isBadVersionだと判定できたとしても、それが最初の悪いバージョンとは限らない。

※悪いバージョン以降は、全て悪いバージョンのため。

なので、悪いバージョンを見つけたときは、その場所(インデックス)を覚えておき、

その左側を探索範囲として引き続き調べる必要がある。

while文を最後まで回すと、悪いバージョンと良いバージョンの境目が来るはずなので、

その時に悪いバージョンとして記憶されていた場所が、最初の悪いバージョンの場所になる。

補足・参考・感想

■補足

■参考

前：7. Reverse Integer

次：11. Container With Most Water

LeetCode 解答・解説記事一覧