leetcode [#278]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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.

---

解决方案

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int i = 1;
        int j = n;
        if(isBadVersion(1)) return 1;
        while (i < j){
            int mid = i + (j - i) / 2;
            if(!isBadVersion(mid)){
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return isBadVersion(i) ? i : i+1;
    }
}

---

注意事项

1. 要清楚理解题意。待实现方法firstBadVersion()需要一个参数：即1~n的n，但是整个功能需要传入两个参数：数据范围、第一个出错版本的版本号。其中，n传递给firstBadVersion()，而第一个出错版本的版本号bad则在solution类实例化时通过在其构造函数中调用父类构造函数来传入。因此，在本地测试时要加上isBadVersion()方法的实现，整体代码如下：

   package task278;
   
   /** * Created by gaochang on 2016/11/25. */
    * Created by gaochang on 2016/11/25.
    */
   public class solution extends VersionControl{
       public solution(int pick){
           super(pick);
       }
       public int firstBadVersion(int n) {
           int i = 1;
           int j = n;
           if(isBadVersion(1)) return 1;
           while (i < j){
               int mid = i + (j - i) / 2;
               if(!isBadVersion(mid)){
                   i = mid + 1;
               } else {
                   j = mid - 1;
               }
           }
           return isBadVersion(i) ? i : i+1;
       }
       public static void main(String[] args){
           int n = 3;
           int bad = 2;
           solution s = new solution(bad);
           int re = s.firstBadVersion(n);
           System.out.println(re);
       }
   }
   
   class VersionControl {
       private int res;
   
       public VersionControl(int val){
           this.res = val;
       }
   
       public boolean isBadVersion(int version){
           return version >= res ? true : false;
       }
   }

2. 与使用二分查找某一具体元素稍有不同的是，本题是要在数组中找到第一个false（即第一个出错版本的版本号），二分查找，每次判断中间mid元素的正确性。如果正确，则在当前的后半段继续查找，如果错误，则在当前的前半段继续查找，跳出条件是头索引小于尾索引。这样，调出后的i并不一定指向的是第一个错误版本的序号，有可能是第一个错误版本的序号的前一个。因此最后返回的时候要再对i对应版本的正确性进行一次判断。