写点什么

LeetCode 刷题 278- 简单 - 第一个错误版本

用户头像
ベ布小禅
关注
发布于: 1 小时前


前言

算法作为极其重要的一点,是大学生毕业找工作的核心竞争力,所以为了不落后与人,开始刷力扣算法题!


第一遍,不求最优解,但求能过!!!


📢 这是我刷第 6/100 道力扣简单题

一、题目描述

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。


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


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


难度:简单

二、实例



    输入:n = 1, bad = 1 输出:1
    复制代码

    三、题目解析

    首先想到的肯定是暴力循环,一个一个遍历


    遍历从 1-n,符合要求立马停止循环,返回当前值


    不过他题目要求是尽可能少的调用 API


    也就是说,暴力循环肯定是不行的


    不过,我才管他行不行,我先试试暴力循环


    毕竟我也只会暴力循环


    # The isBadVersion API is already defined for you.# @param version, an integer# @return an integer# def isBadVersion(version):
    class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ ans = 0 # 设置一个变量接收答案 for i in range(n): if isBadVersion(i+1): # 因为i从0开始,到n-1结束 ans = i+1 break return ans
    复制代码


    当我提交后,却出了红色,显示超出时间限制,也就是程序运行时间太长了


    我不由得陷入了沉思,看来只能换个办法了,但是以我当前的知识储备好像也没别的方法了


    我就瞄了一眼题解,发现需要使用二分查找法

    3.1 二分查找法是什么

    二分查找法是一种算法


    他经常用在:


    给定一个升序的数组/列表和一个目标值,尽可能快的查找其中的目标值

    若存在,返回目标值得索引

    若不存在,返回-1

    这样的场景


    因为是升序的,所以我们可以以数组中间的元素为中线,将数组分为左右两个数组


    target = 7  # 给一个目标值start = 0  # 用于计算中间值,和后面陆续的将数组划分为两个数组end = len(li)-1 # 用于计算中间值,记录列表最后值的索引li = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]while start<n:    # 记录一个循环    mid = (start+n)//2  # 值为4    """    一个升序数组/列表    以中间mid(//是保持中间值为整数)为界限    看似分成两个数组    li_left = [1, 2, 3 ,4, 5]    li_right = [6, 7, 8, 9, 10]    """  if target>li[mid]:        # 如果目标值比中间值大,就说名目标值(7)在右边的列表        start = mid+1 # 让start变成右边列表的第一个元素的索引        # 抛弃左边的列表不要,只看右边的列表li_right = [6, 7, 8, 9, 10]    else:        # 如果目标值小于等于中间值,就说明目标值在左边的列表        n = mid # 让n变成左边列表的最大值的索引        # 抛弃右边的列表不要,只看左边的列表
    复制代码


    随着循环的进行,列表会越来越小,最后只剩目标值,然后最小值的索引 start 就是我们需要的值

    3.2 将二分查找法应用在本题

    因为我们有了一个接口可以判断哪个是错的,所以我们可以将 bad 看成目标值,将 n(题干)看成列表的最大索引值 n(实例代码),将isBadVerson()看成target>li[mid]

    四、代码

    # The isBadVersion API is already defined for you.# @param version, an integer# @return an integer# def isBadVersion(version):
    class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ start = 0 # 定义一个最小值索引 while start<n: # 循环 mid = int((start+n)/2) # 计算中间值的索引 if isBadVersion(mid): # 判断相当于target>li[mid] # 如果为True,就说明目标值(bad)在左边,相当于目标值比中间值大 n=mid else: start=mid+1 return start
    复制代码

    结语

    坚持最重要,每日一题必不可少!



    发布于: 1 小时前阅读数: 2
    用户头像

    ベ布小禅

    关注

    还未添加个人签名 2021.04.06 加入

    平平无奇一萌新,默默无闻学IT,我是布小禅,一个网络专业却对编程及其感兴趣的小白! 目前在学python和Java,都很浅显,平时爱写点学习笔记。IT技术交流群:1039347613 也可以联系本人企鹅:2228660752 v:Smly0413

    评论

    发布
    暂无评论
    LeetCode刷题278-简单-第一个错误版本