likes
comments
collection
share

【LeetCode】1656. 设计有序流

作者站长头像
站长
· 阅读数 42

【LeetCode】1656. 设计有序流

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

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

一、题目描述:

  • 题目内容

    【LeetCode】1656. 设计有序流

  • 题目示例

    【LeetCode】1656. 设计有序流

  • 题目解析

    • 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提交记录如下:

【LeetCode】1656. 设计有序流

  • 时间复杂度:O(n),n为调用insert函数次数
  • 空间复杂度:O(n),需要存储n次调用的结果

以上是本期内容,欢迎大佬们呢点赞评论,下期见~~~

转载自:https://juejin.cn/post/7133202251002642468
评论
请登录