LeetCode演算法題-First Bad Version（Java實現-三種解法）
這是悅樂書的第200 次更新，第210 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第66題（順位題號是278）。您是產品經理，目前領導團隊開發新產品。不幸的是，您產品的最新版本未通過質量檢查。由於每個版本都是基於以前的版本開發的，因此壞版本之後的所有版本也是壞的。
假設您有n個版本[1,2，...，n]並且您想找出第一個壞的版本，這會導致以下所有版本都不好。您將獲得一個API bool isBadVersion（版本），它將返回版本是否錯誤。 實現一個函式來查詢第一個壞版本。 您應該最小化對API的呼叫次數。
例如：
給定n = 5，版本= 4是第一個壞版本。
呼叫isBadVersion（3） - > false
呼叫isBadVersion（5） - > true
呼叫isBadVersion（4） - > true
然後4是第一個壞版本。
isBadVersion方法在父類VersionControl中定義。
boolean isBadVersion（int version）;
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
對於從1到n的所有版本中，假設好壞版本的臨界是第mid個，那麼從1到mid-1都是好版本，在呼叫isBadVersion方法時總是返回false;從mid到n都是壞版本，呼叫isBadVersion方法時返回的都是true。
直接使用for迴圈，指標從1開始，依次呼叫isBadVersion方法，如果返回true，則返回當前指標所表示的版本，反之返回n，即最後一個版本。
此解法的時間複雜度是O(n)，空間複雜度是O(1)，但是提交後提示超時了，我們需要一個更快的方法。
public int firstBadVersion(int n) {
for (int i = 1; i < n; i++) {
if (isBadVersion(i)) {
return i;
}
}
return n;
}
03 第二種解法
從第一種解法的分析那裡，相信你應該可以將此問題再抽象下，就變成資料查詢問題了，從一個指定大小的容器中找出具體的某一個值。
如果你玩過猜大小的遊戲，那麼使用二分法來求解，你一定不陌生。不斷使用中間數，向預期的結果逼近。
使用二分法需要注意兩點：
在求中間數的時候，如果資料型別選用int，直接使用(1+n)/2，如果n是Integer的最大值，加1後會存在溢位的風險，此時我們可以曲線救國，換一種寫法，1 + (n-1)/2，就可以避免這種風險，另外也可以將其換成範圍更大的long型別，不過就需要強轉了。
如果中間值呼叫isBadVersion方法時返回false，是不能直接判定臨界版本就是mid，因為你無法保證mid的前幾位都是好版本，正確的做法是讓範圍縮小到1到mid，再去求中間值進行判斷。
此解法的時間複雜度是O(log(n))，空間複雜度是O(1)。
public int firstBadVersion2(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = (right-left)/2 + left;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
04 第三種解法
這是遞迴的解法，思路和第二種解法一樣。
public int firstBadVersion3(int n) {
if (n == 0) {
return 0;
}
return helper(n, 1, n);
}
public int helper(int n, int start, int end) {
if (start >= end) {
return start;
}
int middle = start + (end - start)/2;
if (isBadVersion(middle)) {
return helper(n, start, middle);
} else {
return helper(n, middle + 1, end);
}
}
05 小結
演算法專題目前已連續日更超過一個月，演算法題文章66 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！