文本编辑器设计, 要求append, insert, delete均为O(1)# JobHunting - 待字闺中
m*p
1 楼
append就是加到末尾, insert是加到中间, delete是任何位置的删除
linkedlist + hashtable 或者 array + hashtable?
已跪, 请问具体如何实现?
linkedlist + hashtable 或者 array + hashtable?
已跪, 请问具体如何实现?
l*a
2 楼
中间指"正中间"，还是给个index想insert在什么地方就是什么地方
【在 m***p 的大作中提到】
: append就是加到末尾, insert是加到中间, delete是任何位置的删除
: linkedlist + hashtable 或者 array + hashtable?
: 已跪, 请问具体如何实现?
【在 m***p 的大作中提到】
: append就是加到末尾, insert是加到中间, delete是任何位置的删除
: linkedlist + hashtable 或者 array + hashtable?
: 已跪, 请问具体如何实现?
n*1
3 楼
加到中间的话要O（1）的话 deque?
A*c
4 楼
底层表示用双向链表。
类里边定义光标位置。
【在 m***p 的大作中提到】
: append就是加到末尾, insert是加到中间, delete是任何位置的删除
: linkedlist + hashtable 或者 array + hashtable?
: 已跪, 请问具体如何实现?
类里边定义光标位置。
【在 m***p 的大作中提到】
: append就是加到末尾, insert是加到中间, delete是任何位置的删除
: linkedlist + hashtable 或者 array + hashtable?
: 已跪, 请问具体如何实现?
l*i
5 楼
something similar to Java LinkedHashMap
s*x
6 楼
Insert in the middle for deque is O(n).
【在 n*******1 的大作中提到】
: 加到中间的话要O（1）的话 deque?
【在 n*******1 的大作中提到】
: 加到中间的话要O（1）的话 deque?
m*p
7 楼
是加到任意位置
【在 l*****a 的大作中提到】
: 中间指"正中间"，还是给个index想insert在什么地方就是什么地方
【在 l*****a 的大作中提到】
: 中间指"正中间"，还是给个index想insert在什么地方就是什么地方
m*p
8 楼
为了可以O(1)访问任意位置, 还需要一个hashtable吧?
【在 A*********c 的大作中提到】
: 底层表示用双向链表。
: 类里边定义光标位置。
【在 A*********c 的大作中提到】
: 底层表示用双向链表。
: 类里边定义光标位置。
b*f
9 楼
Mark
A*c
10 楼
这个应该是没说清楚，几乎没有文本编辑器有随机修改任意位置的需求。
word，vi, emacs, mitbbs，you name it. 都是对光标位置进行插入和删除操作。
【在 m***p 的大作中提到】
: 为了可以O(1)访问任意位置, 还需要一个hashtable吧?
word，vi, emacs, mitbbs，you name it. 都是对光标位置进行插入和删除操作。
【在 m***p 的大作中提到】
: 为了可以O(1)访问任意位置, 还需要一个hashtable吧?
j*d
11 楼
这个题目，如果“任意位置”是指给出任意的位置索引，要求实现查、删、添，那就是
要求集成
Hashtable，Linkedlist，Array的O(1)，觉得不可能实现。
要求集成
Hashtable，Linkedlist，Array的O(1)，觉得不可能实现。
n*1
12 楼
光标移动应该是必须的 否则应该无解 还是用deque
s*d
13 楼
gap buffer 和 rope的复杂度是多少？
相关阅读
C++疑问：Animal a，Animal* a，哪种访问方式快问个题？求质数用trie统计字符串的疑惑intel的资深HR周六下午3点电话讲座和答疑recruiter联系我，可是这个位置太高关于FLAMG这类大公司refernce check的问题农学PHD的OPT 能去工业界找统计之类的工作吗？leetcode似乎c++11支持不完全?测试转开发要注意些什么？今年就业形势 好像 不如去年啊关于被雷现在公司都流行各种不理人么聪明的给帮忙解道题，Relocation 费是税前还是税厚呀？C++是否能实现java那样的reflect机制？做了一下Kth small in young tablet 和 largest rectangle contain 1slayoff以后i539的问题EE方向求opt volunteer 挂靠。。。Job Openings: Software Design Engineer, Hardware Design Engineer ......Please contact me if you are good at C/C++ and/or compiler