美文网首页
02_第一个错误的版本

02_第一个错误的版本

作者: butters001 | 来源:发表于2019-11-01 14:12 被阅读0次
    # The isBadVersion API is already defined for you.
    # @param version, an integer
    # @return a bool
    def isBadVersion(version):
        if version >= 71:
            return True
        else:
            return False
    
    # 16ms
    class Solution(object):
        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            直接 range(n, 0, -1) 会报 MemoryError 错误
            思路:二分查找
            """
            # pre = 1
            # for i in range(n, 0, -1):
            #     if isBadVersion(i):
            #         return pre
            #     pre = i
    
            left = 0
            right = n
            while True:
                mid = (left + right) // 2
                if isBadVersion(mid) == False and isBadVersion(mid+1) == True:
                    return mid + 1
                elif isBadVersion(mid) == False and isBadVersion(mid+1) == False:
                    left = mid
                elif isBadVersion(mid) == True and isBadVersion(mid+1) == True:
                    right = mid
    
    
    # leetcode 上最优解 4ms
    class Solution2(object):
        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            """
            if not isBadVersion(n): return n
    
            left = 1
            right = n
    
            while left < right:
    
                mid = (left + right) >> 1
    
                if not isBadVersion(mid):
                    left = mid + 1
                else:
    
                    right = mid
    
            return left
    
    
    n = 1004
    s = Solution()
    print(s.firstBadVersion(n))
    
    

    相关文章

      网友评论

          本文标题:02_第一个错误的版本

          本文链接:https://www.haomeiwen.com/subject/smbfbctx.html