資訊專欄INFORMATION COLUMN
摘要：分析最后一次循環(huán)的時刻當與相差小于時，總是那么如果是，下一次直接跳出循環(huán)，返回當與相差大于時，是，變成，如果是，循環(huán)結(jié)束的條件將是循環(huán)結(jié)束，返回
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.
NoticePlease read the annotation in code area to get the correct way to call isBadVersion in different language. For example, Java is SVNRepo.isBadVersion(v)
ExampleGiven 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.
You should call isBadVersion as few as possible.
Solutionpublic class Solution extends VersionControl {
public int firstBadVersion(int n) {
int start = 1, end = n;
while (start <= end) {
int mid = start+(end-start)/2;
//分析最后一次循環(huán)的時刻：
//當start與end相差小于2時，mid總是start, 那么如果start是bad，下一次直接跳出循環(huán)，返回start
//當start與end相差大于2時，mid是bad，end變成mid-1，如果mid是first bad，循環(huán)結(jié)束的條件將是：
//end stays on the same position, start = end+1 --> start goes to the first bad position
//循環(huán)結(jié)束，返回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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69263.html
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...
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...
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...
摘要：二分搜索法復雜度時間空間思路因為一個版本是錯誤，其后面的所有版本都是錯誤的，所以我們可以用二分搜索，當取中點時，如果中點是錯誤版本，說明后面都是錯誤的，那第一個錯誤版本肯定在前面。如果中點不是錯誤版本，說明第一個錯誤版本肯定在后面。 First Bad Version You are a product manager and currently leading a team to ...
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) ...
閱讀 3055·2021-11-22 09:34
閱讀 2521·2021-09-30 09:47
閱讀 1457·2021-09-03 10:32
閱讀 3726·2021-08-16 10:49
閱讀 1798·2019-08-30 15:55
閱讀 2475·2019-08-30 15:52
閱讀 3333·2019-08-30 15:44
閱讀 1365·2019-08-30 15:44
