当前位置：首页 > news >正文

LeetCode -- First Bad Version

news 来源：原创 2024/5/3 9:02:31

题目描述：

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

在从1到n的版本号中，找到第1个坏版本，已知如果第i个版本为坏版本，那么从i+1到n的版本都是坏版本。

思路：
又是一道二分查找题目，应用二分查找思路加入一些特殊逻辑处理即可：
1. 如果当前版本是坏版本：
1.1 上一个版本不是坏版本，返回当前版本
1.2 否则，向左找
2. 如果当前版本不是坏版本：
2.1 下一个版本为坏版本，返回下一个版本
2.2 否则，向右找

最后分别判断左右版本是否则坏版本即可。

注意中间索引m需要写成：
var m = (int)(l/2.0 + r/2.0);
这样做是防止一些大数字加运算越界。

实现代码：

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


public class Solution : VersionControl {
    public int FirstBadVersion(int n) 
    {
        var l = 0;
    	var r = n;
    	
    	while(l < r - 1){
    		var m = (int)(l/2.0 + r/2.0);
    		var mBad = IsBadVersion(m);
    		if(mBad)
    		{	
    			if(!IsBadVersion(m-1)){
    				return m;	
    			}
    			else{
    				r = m;
    			}
    		}
    		else{
    			if(IsBadVersion(m+1)){
    				return m+1;	
    			}
    			else{
    				l = m;
    			}
    		}
    	}
    	var leftBad = IsBadVersion(l);
    	var rightBad = IsBadVersion(r);
    	
    	if(leftBad){
    		return l;
    	}
    	else if(!leftBad && rightBad){
    		return r;
    	}
    	return -1;
    }
}