测试岗位也越来卷了，除了基本的功能测试外，还要有编程基础、脚本经验才脱颖而出。

怎么才能提高我们的编程能力呢，刷LeetCode是最佳的途径之一，话不多数,刷题走起~

一、题目描述：

• 题目内容

  

• 题目示例

  

• 题目解析

  • startTime.length == endTime.length
  • 1 <= startTime.length <= 100
  • 1 <= startTime[i] <= endTime[i] <= 1000
  • 1 <= queryTime <= 1000

二、思路分析：

我们拿到本题，看到题目内容，背景是学生做作业的区间，其实是在多个区间中求出符合区间的次数，题目参数是怎么呈现的，我们继续审题：

• startTime 是学生们开始做作业的起始时间列表
• endTime 是学生们做完作业的时间列表
• startTime、endTime长度是一样的，索引index是学生id
• queryTime 是区间查询时间点

根据题目要求，我们能立马想到使用遍历方法模拟方法查询📖，思路如下：

• 方法一：遍历模拟法

  • startTime 与 endTime 两个列表中index是一一对应，使用迭代器zip()自动关联
  • 使用for循环遍历start,end在zip(startTime,endTime)中取值
  • 当queryTime大于等于start，queryTime小于等于end时，则ans 次数+1

  class Solution(object):
      def busyStudent(self, startTime, endTime, queryTime):
          """
          :type startTime: List[int]
          :type endTime: List[int]
          :type queryTime: int
          :rtype: int
          """
          ans = 0
          for start,end in zip(startTime,endTime):
              if queryTime >= start and queryTime <= end :
                  ans +=1
          return ans
  

• 方法二：差分数组

• 虽然使用遍历方法可以解答本题，但是当区间列表数据大量时，遍历方法显得不那么高效
• 关于区间问题的，通常有三种方法：差分数组、前缀和和线段树
• 差分数组定义：f[i]=d[i]-d[i-1]
• 差分数组用途：可以解决（1）快速处理区间加减操做（2）询问区间和问题
• 本题中使用差分数组，就比较清晰啦，思路如下：
  • 首先定义一个cnt数组，初始化[0]*maxlen
  • 通过for循环startTime,endTime列表，分别以其元素start,end为索引
  • 在cnt列表中cnt[start] +=1，cnt[end+1]-=1
  • 符合queryTime的区间则sum(cnt[:queryTime+1])

  class Solution(object):
      def busyStudent(self, startTime, endTime, queryTime):
          """
          :type startTime: List[int]
          :type endTime: List[int]
          :type queryTime: int
          :rtype: int
          """       
          cnt = [0]*1020
          for start,end in zip(startTime,endTime):
              cnt[start] +=1
              cnt[end+1] -=1
          for i in range(1,queryTime+1):
              cnt[i] += cnt[i-1]
          return cnt[queryTime]
  

三、总结：

本题是关于区间求解的问题，关于区间问题有前缀和、差分数组和线段树。本题中场景比较简单并且数据量比较小，因此采用遍历枚举方法可以解答，当数据大时且查询次数大时，我们可以使用差分数组。AC 提交记录如下：

• 时间复杂度：O(n)，startTime列表长度
• 空间复杂度：O(1)，没有使用额外空间

以上是本期内容，欢迎大佬们点赞评论，下期见～～～