力扣(LeetCode)276

wushuiyong 发布于2019-08-16 15:55 / 1268人阅读

摘要：不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。示例给定，并且是第一个错误的版本。否则把搜索下界变成因为左边一定都是，代表左边没有错误版本代码

题目地址：
https://leetcode-cn.com/probl...
题目描述：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

解答：
二分搜索，假设现在查找的版本号为mid，若isBadVersion(mid)为true，则表示
mid以后的版本号都为true，那么记录下mid，并且把搜索下界变成mid-1(因为mid右边一定都是true，那右边的一定不是第一个了。)
否则把搜索下界变成mid+1(因为mid左边一定都是false，代表左边没有错误版本)

java ac代码：

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int begin = 1,end = n;
        int ans = 0;
        while(begin <= end)
        {
            int mid = begin + (end - begin)/2;
            if(isBadVersion(mid))
            {
                ans = mid;
                end = mid-1;
            }
            else begin = mid+1;
        }
        return ans;
    }
}

GPU云服务器云服务器力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73778.html

力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
[LeetCode] 276. Paint Fence

Problem There is a fence with n posts, each post can be painted with one of the k colors.You have to paint all the posts such that no more than two adjacent fence posts have the same color.Return the ...

codeKK 2019-08-14 15:20 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
力扣(LeetCode)452

摘要：对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。解答这是一道区间覆盖问题，不太好说清楚，利用模板即可。题目地址：https://leetcode-cn.com/probl...题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方...

fanux 2019-08-16 15:20 评论0 收藏0