LeetCode - First Bad Version

5376 ワード
アルゴリズム#アルゴリズム# テキストリンク
質問する
製品マネージャで、チームを率いて新製品を開発しています.残念なことに、最新バージョンの品質検査に失敗しました.各バージョンは以前のバージョンに基づいて開発されているため、すべての不良バージョン以降のバージョンは不良バージョンです.
nバージョン[1,2,...,n]の最初のバージョンを確認します(次のバージョンはすべて無効です).
API bool isBadVersion(バージョン)を提供し、バージョンが無効かどうかを返します.関数を実装して、最初の不良バージョンを検索します.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
解決する
Binary Searchで解決.
  • は開始と終了を発表した.
    • 中間価格は
  • のmidと発表された.
  • endが中間値より小さい場合、endは左に1グリッド移動します.
  • startが中間値より小さい場合、startは右に1つ移動します.
  • は、endまたはstart値が変化するとmid値が自動的に変化する.
  • 以降、繰り返し文の終了時にstart値が返されます.
    • var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
      //isBadVersion이 함수이나 인자로 들어옴. 익명함수로 해소
        let start = 1;
        let end = n;
        let mid;
        while (end >= start) {
            mid = Math.floor((start+end)/2);
            if (isBadVersion(mid)) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }
        return start;
    };
};
    しょうすうを判別する
    git , github