【LeetCode】1656. 设计有序流
测试岗位也越来卷了,除了基本的功能测试外,还要有编程基础、脚本经验才脱颖而出。
怎么才能提高我们的编程能力呢,刷LeetCode是最佳的途径之一,话不多数,刷题走起~
一、题目描述:
-
题目内容
-
题目示例
-
题目解析
- 1 <= n <= 1000
- 1 <= id <= n
- value.length == 5
- value 仅由小写字母组成
- 每次调用 insert 都会使用一个唯一的 id恰好调用 n 次 insert
二、思路分析:
我们读取本题,题目要求实现一个有序流对象,里面包含一个insert()方法,传参是一个(id,value)需要返回一个ptr指针与id之间连续的字符串元素,还要一些细节需要注意:
- orderedStream(n),构造函数接收n个长度的流,并初始化ptr
- insert()传入idkey->value的数据
- 当idkey与ptr相等值时,返回从ptr开始最长连续增序列,ptr指针+1
- 否则返回一个空列表
根据题目说明,我们可以使用列表来模拟方式解答本题,思路大致如下:
- orderStream,构造函数时我们可以初始化长度为n的空字符列表self.deque,ptr指针赋值为0
- 在insert()方法传参idkey->value,因此直接self.deque[idkey-1] = value
- 使用while遍历self.deque列表,当self.deque[self.ptr] 不为空字符时,则self.ptr指针+1
- 如果self.deque[self.ptr]字符是空字符,则直接退出循环
- 结果返回为self.deque[idKey-1:self.ptr]片段
- 根据以上思路,我们使用python能快速实现,代码如下:
class OrderedStream(object): def __init__(self, n): """ :type n: int """ self.n = n self.deque = [""]*self.n self.ptr = 0 def insert(self, idKey, value): """ :type idKey: int :type value: str :rtype: List[str] """ self.deque[idKey-1] = value while self.ptr < self.n: if self.deque[self.ptr] != "": self.ptr +=1 else: break return self.deque[idKey-1:self.ptr]
三、总结:
本题考察对数组指针片段取值,我们需要找到起点和结束位置,在本题中idkey-1为列表开始为,结尾位置为ptr-1。AC提交记录如下:
- 时间复杂度:O(n),n为调用insert函数次数
- 空间复杂度:O(n),需要存储n次调用的结果
以上是本期内容,欢迎大佬们呢点赞评论,下期见~~~
转载自:https://juejin.cn/post/7133202251002642468