博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[Lintcode]74. First Bad Version/[Leetcode]278. First Bad Version
阅读量:5307 次
发布时间:2019-06-14

本文共 1751 字,大约阅读时间需要 5 分钟。

  • 本题难度: [Lintcode]Medium/[Leetcode]
  • Topic: Binary Search

    Description

我的代码 for Leetcode(在Lintcode中因为isBadVersion调用太多次无法通过)

# The isBadVersion API is already defined for you.# @param version, an integer# @return a bool# def isBadVersion(version):class Solution:    def firstBadVersion(self, n):        """        :type n: int        :rtype: int        """        if isBadVersion(1) is True:            return 1        else:            if n==1:                return 0        l = 2        r = n        m = (l+r)//2        while(l<=r):            print(l,m,r)            t1 = isBadVersion(m-1)            t2 = isBadVersion(m)            print(t1,t2)            if t1 is False and t2 is True:                print("ok")                return m            else:                if t2 is False:                    l = m+1                else:                    if t1 is True:                        r = m-1            m = (l+r)//2

别人的代码 for Lintcode

#class SVNRepo:#    @classmethod#    def isBadVersion(cls, id)#        # Run unit tests to check whether verison `id` is a bad version#        # return true if unit tests passed else false.# You can use SVNRepo.isBadVersion(10) to check whether version 10 is a # bad version.class Solution:    """    @param n: An integer    @return: An integer which is the first bad version.    """    def findFirstBadVersion(self, n):        # write your code here        r = n-1        l = 0        while(l<=r):            mid = l + (r-l)//2            if SVNRepo.isBadVersion(mid)==False:                l = mid+1            else:                r = mid-1        return l

思路

大思路是二分法,但是我想岔了。

其实无需找到一个自身为true,前一个为false的id,只需要找到最后一个为false的id即可。这样可以减少一次比较。

  • 时间复杂度: O(log(n))

转载于:https://www.cnblogs.com/siriusli/p/10357078.html

你可能感兴趣的文章
Leet 145: Binary Tree Postorder Traversal
查看>>
Leetcode 156: Binary Tree Upside Down
查看>>
大数除法
查看>>
html语义化
查看>>
Lightoj 1016 - Brush (II)
查看>>
【代码笔记】iOS-NSLog的使用
查看>>
JavaScript 函数调用
查看>>
常见的磁盘I/O和网络I/O优化技巧
查看>>
java 利用反射完成自定义注解
查看>>
【2016常州一中夏令营Day4】
查看>>
php文件下载
查看>>
(4)[wp7数据存储] WP7 IsolatedStorage系列篇--读取、保存图片文件 [复制链接]
查看>>
C#让电脑发声,播放声音
查看>>
构造函数调用和复制构造函数调用
查看>>
silverlight的timer
查看>>
关于响应式布局
查看>>
Django ViewDoesNotExist error
查看>>
amazeui.css
查看>>
nginx 的uri、request_uri 区别
查看>>
发送邮件程序报错454 Authentication failed以及POP3和SMTP简介
查看>>