Good Hacker——模拟&&双向队列
2023-09-27 14:27:45 时间
题意:给定一个字符串,长度为$n(1 \leq n \leq 3 \times {10}^5)$,求源字符串。该字符串包括“[”(表示光标移动到最前端),“]”(移动到最后端),“>”(右移一位),“<”(左移一位),“_”(空格),"-"(backspace,删除键)。注意光标仅仅移动(或删除)当行动是有效的。
样例:
Sample Input 1 subwat-y_interchange[location_] Sample Output 1 location_subway_interchange Sample Input 2 time------day___d<we>>>>nesday Sample Output 2 day___wednesday Sample Input 3 aabbcc------ Sample Output 3 ?
分析:
用python的list切片会超时,需要自己写链表,为了O(1)的维护index,采用双向链表。
这个Python双向链表模板不错
class Node(object): def __init__(self, data=None): self.data = data self.pre = None self.next = None class DoublyLinkedList(object): # 初始化双向链表 def __init__(self): head = Node() tail = Node() self.head = head self.tail = tail self.cur = tail self.head.next = self.tail self.tail.pre = self.head # 插入节点 def insert(self, cur, data): next_node = cur if next_node: node = Node(data) pre_node = next_node.pre pre_node.next = node node.pre = pre_node node.next = next_node next_node.pre = node return node # 删除节点 def delete(self, cur): node = cur.pre if node: node.pre.next = node.next node.next.pre = node.pre return True return False # 打印链表 def show(self, order=1): node = self.head.next while node is not self.tail: print(node.data, end="") node = node.next ls = DoublyLinkedList() str = input().strip() for ch in str: if (ch >= 'a' and ch <= 'z') or (ch == '_'): ls.insert(ls.cur, ch) elif ch == '-': if ls.cur.pre != ls.head: ls.delete(ls.cur) elif ch == '<': if ls.cur.pre != ls.head: ls.cur = ls.cur.pre elif ch == '>': if ls.cur != ls.tail: ls.cur = ls.cur.next elif ch == '[': ls.cur = ls.head.next elif ch == ']': ls.cur = ls.tail if ls.head.next == ls.tail: print("?") else: ls.show()
相关文章
- GNN-静态表征-随机游走-2016:Node2vec【 步骤:①有偏随机游走策略生成每个节点的训练序列(DFS&BFS),得到训练数据集;②套用Word2vec算法得到节点表示】【浅层模型、同质图】
- 【Kubernetes】概述 & 搭建
- SecureCRT & SecureFx 绿色破解版
- Android学习之 换肤功能模块的实现<二>
- (转载)极大似然估计&最大后验概率估计
- 【Python & mxnet】模拟实现:自定义线性回归(创建数据集 || 数据读取 || 初始化模型参数 || 定义模型 || 损失函数 || 优化 || 训练)
- 黑马程序员&传智播客 python生成器 学习笔记
- JSP&Servlet学习笔记----第4章
- Python的神奇功能——函数&装饰器&MetaClass
- php:版本控制工具的使用&安装老版本php5.6问题
- 费马平方和定理&&斐波那契恒等式&&欧拉四平方和恒等式&&拉格朗日四平方和定理
- Openstack 中的消息总线 & AMQP
- 【C++ 压缩&解压缩 开源库】ZIP入门使用总结
- 我的Android进阶之旅------>Android中通过adb shell input来模拟滑动、按键、点击事件
- 我的Android进阶之旅------>Android中使用HTML作布局文件以及调用Javascript