关于java:LeetCode278第一个错误的版本

9次阅读

共计 1216 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：你是产品经理，目前正在率领一个团队开发新的产品。可怜的是，你的产品的最新版本没有通过品质检测。因为每个版本都是基于之前的版本开发的，所以谬误的版本之后的所有版本都是错的。

假如你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个谬误的版本。

你能够通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个谬误的版本。你应该尽量减少对调用 API 的次数。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：二分法

别离用 low 和 high 记录第一个元素和最初一个元素，而后用二分法求解，求解过程如下：

用 mid 记录两头地位，即 low + (high - low) / 2，而后调用isBadVersion(mid) 办法判断以后版本是否是谬误版本；

如果以后版本是谬误版本且以后版本后面的一个版本 (须要再次调用isBadVersion 办法)也是谬误版本，则将 high 重置为mid-1，而后进行下一轮解决；

如果以后版本是谬误版本然而以后版本的后面一个版本不是谬误版本，则以后版本即是第一个谬误版本，返回以后版本；

如果以后版本不是谬误版本，则将 low 重置为mid+1，而后进行下一轮解决。

循环终结的条件就是 low 大于 high。

最初，如果没有找到谬误的版本，返回 -1。

public class LeetCode_278 extends VersionControl {
    /**
     * 二分法
     *
     * @param n
     * @return
     */
    public static int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low <= high) {int mid = low + (high - low) / 2;
            if (isBadVersion(mid)) {if (mid > low && isBadVersion(mid - 1)) {high = mid - 1;} else {return mid;}
            } else {low = mid + 1;}
        }
        return -1;
    }

    public static void main(String[] args) {System.out.println(firstBadVersion(2126753390));
    }
}

class VersionControl {
    /**
     * 测试数据，前 1702766718 个版本都不是谬误版本，从第 1702766719 个版本开始都是谬误版本
     */
    public static boolean isBadVersion(int version) {if (version < 1702766719) {return false;} else {return true;}
    }
}