[LeetCode/LintCode] First Bad Version

lowett 发布于2019-08-15 15:46 / 978人阅读

摘要：分析最后一次循环的时刻当与相差小于时，总是那么如果是，下一次直接跳出循环，返回当与相差大于时，是，变成，如果是，循环结束的条件将是循环结束，返回

Problem

The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case, so it caused this version and the following versions are all failed in the unit tests. Find the first bad version.

You can call isBadVersion to help you determine which version is the first bad one. The details interface can be found in the code"s annotation part.

Notice

Please read the annotation in code area to get the correct way to call isBadVersion in different language. For example, Java is SVNRepo.isBadVersion(v)

Example

Given n = 5:

isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true
Here we are 100% sure that the 4th version is the first bad version.

Challenge

You should call isBadVersion as few as possible.

Solution

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1, end = n;
        while (start <= end) {
            int mid = start+(end-start)/2; 
            //分析最后一次循环的时刻：
            //当start与end相差小于2时，mid总是start, 那么如果start是bad，下一次直接跳出循环，返回start
            //当start与end相差大于2时，mid是bad，end变成mid-1，如果mid是first bad，循环结束的条件将是：
            //end stays on the same position, start = end+1 --> start goes to the first bad position
            //循环结束，返回start
            if (isBadVersion(mid)) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }
        return start;
    }
}

Update 2018-9

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n == 0) return 0;
        int i = 1, j = n;
        while (i < j) {
            int mid = i+(j-i)/2;
            //mid could be the first bad, so DON"T do: j = mid-1
            if (isBadVersion(mid)) j = mid;
            //when mid is not bad, just DO: i = mid+1 
            else i = mid+1;
        }
        return j;
    }
}

idc机房托管私有云 Bad bad request bad file descriptor Version

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69263.html

[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
[LeetCode/LintCode] Largest Palindrome Product

Problem Find the largest palindrome made from the product of two n-digit numbers. Since the result could be very large, you should return the largest palindrome mod 1337. Example Input: 2Output: 987Ex...

Barry_Ng 2019-08-15 18:16 评论0 收藏0
[LeetCode/LintCode] Course Schedule II

Problem There are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed a...

Lavender 2019-08-15 17:49 评论0 收藏0
[Leetcode] First Bad Version 第一个错误版本

摘要：二分搜索法复杂度时间空间思路因为一个版本是错误，其后面的所有版本都是错误的，所以我们可以用二分搜索，当取中点时，如果中点是错误版本，说明后面都是错误的，那第一个错误版本肯定在前面。如果中点不是错误版本，说明第一个错误版本肯定在后面。 First Bad Version You are a product manager and currently leading a team to ...

senntyou 2019-08-14 12:33 评论0 收藏0
[LeetCode/LintCode] Is Subsequence

Problem Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) ...

terasum 2019-08-19 11:05 评论0 收藏0