前言
算法作为极其重要的一点,是大学生毕业找工作的核心竞争力,所以为了不落后与人,开始刷力扣算法题!
第一遍,不求最优解,但求能过!!!
📢 这是我刷第 6/100 道力扣简单题
一、题目描述
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
难度:简单
二、实例
三、题目解析
首先想到的肯定是暴力循环,一个一个遍历
遍历从 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
复制代码
结语
坚持最重要,每日一题必不可少!
评论