<abbr id="quo0c"></abbr>

[LeetCode/LintCode] First Bad Version

lowett 發布于2019-08-15 15:46 / 1240人閱讀

摘要：分析最后一次循環的時刻當與相差小于時，總是那么如果是，下一次直接跳出循環，返回當與相差大于時，是，變成，如果是，循環結束的條件將是循環結束，返回

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;
    }
}

云服務器 GPU云服務器 Bad bad request bad file descriptor Version

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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