打卡群刷题总结0606——第一个错误的版本

木又AI帮

发布于 2020-06-09 12:34:11

2640

发布于 2020-06-09 12:34:11

文章被收录于专栏：木又AI帮木又AI帮

题目：278. 第一个错误的版本

链接：https://leetcode-cn.com/problems/missing-number

问题：

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后版本出错的第一个错误版本。你可以通过调用bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。示例: 给定 n=5，并且 version=4 是第一个错误的版本。调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。

解题：

1、暴力破解，直接遍历。但是内存超出！

2、二分查找，找到第一个符合条件的数。

代码：

# The isBadVersion API is already defined for you.# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 1、暴力破解，for循环，内存限制
        # for i in range(1, n + 1):
        #     if isBadVersion(i):
        #         return i
        # 2、二分查找
        # 找到满足条件的第一个数
        l, r = 0, n
        while l <= r:
            mid = (l + r) // 2
            if not isBadVersion(mid):
                l = mid + 1
            else:
                r = mid - 1
        # r: False, l: True
        return l

PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。

PPS：还是得日更呀，总结一下总是好的。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-06-06，如有侵权请联系 cloudcommunity@tencent.com 删除

单元测试