所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

抽象数据结构一般有序列、栈、队列、集合、图（键值对）、优先级队列等。具体数据结构一般有数组、链表、hash表、二分搜索树、二叉堆等。

图的实现：使用hashmap的话，优点是直接，缺点是hashmap有内存和代码的开销；另一种可选方法就是使用数组。如果给出的输入数据是边pair，那么就看存不存在重复边，如果重复，那么就不能使用数组。

树是一种逻辑上的结构，从内存角度来看，树可能是用数组装的。

堆逻辑上看是完全二叉树，内存来看，是用数组存储的，数组下标对应了二叉树的层次从上而下，从左到右的次序，这样：每次加入新元素，只需要在数组的最后面加入一个元素，然后在后续调整；每次删除堆顶的时候，可以把在后面找一个元素替代第一个位置的元素。

具体题目

232. Implement Queue using Stacks

题意：用栈实现队列。

解：栈先进后出，队列先进先出，思路就是使用两个栈来实现队列，负负得正。在第一个栈先压栈，然后弹出到第二个栈，最后在第二个栈出。问题是存入第二个栈的时机，该时机不是每次有元素加入的时候，如果是这样，那和一个栈效果一样。 正确做法就是将两个栈当作一个整体结构，在入栈的时候，把元素存到第一个栈里面，出栈的时候，看第二个栈是不是空的，如果是，那么将第一栈里面的元素全部弹出来，放入第二个栈。

时间复杂度：平摊起来是O(1)，仅在第二个栈为空的时候，才把第一个栈的所有元素放入第二个栈，而且第一个栈不用在还原了，因为元素已经到了第二个栈里面，没有任何操作会用到第一个栈了。也就是说，每个元素只会分别入栈出栈两次。

225. Implement Stack using Queues

题意：用队列实现栈。

骨架

核心动作只有一个：旋转。把队首的元素出队再入队，重复 n-1 次，
最后入队的那个就转到了队首 —— 队首即栈顶。

推荐写法（单队列，代价放在 push）：
  push(x): 入队 x；然后旋转 size-1 次      O(n)
  pop():   直接出队                       O(1)
  top():   直接看队首                     O(1)

解：队列是先进先出，栈是后进先出，所以必须人为地把”最后进来的”搬到队首。办法就是旋转：把队首元素出队、立刻再入队，重复 n-1 次，剩下没被搬动的那个（也就是最新入队的）就来到了队首。

旋转放在哪一步，就决定了哪个操作是 O(n)：

写法一（推荐）：旋转放在 push

push 时先入队新元素，再旋转 size-1 次，于是队首永远是栈顶。这样 pop 和 top 都是 O(1)，代码也最短。

写法二：旋转放在 pop

push 直接入队（O(1)）；pop 时把队首元素（除最后一个外）依次重新添加到队尾，然后再出队，此时出来的就是栈顶。

两种写法总复杂度相同，但推荐把代价放在 push。理由是 top() 通常调用最频繁，而写法二里的 top() 要么也得旋转一遍、要么得额外维护一个变量记住栈顶，都更容易写错。

写法三：两个队列

push 时把新元素放进空的那个队列，再把另一个队列的全部元素倒过来，最后交换两个队列的角色。本质和写法一完全相同（都是让新元素排到队首），只是多用了一个容器，没有额外好处。

复杂度：push O(n)、pop O(1)、top O(1)、empty O(1)（写法一）。注意这是每次的真实开销，不是摊还。

为什么 225 比 232 贵：倒一次的效果不同

232 用两个栈实现队列能做到摊还 O(1)，而本题无论怎么写都有一个操作是每次 O(n)。根本原因在这里：

于是：

• 232：逆序两次就是正序，这就是”负负得正”。而且元素倒进第二个栈之后永久有效，不需要倒回来，所以每个元素一生只进出栈各两次 —— 摊还 O(1)。
• 225：倒一次等于什么都没做，加几个队列都换不来逆序。只能靠旋转 n-1 次硬造出”最后进的在队首”，而且下一次操作还得重新旋转一遍，代价无法被摊掉 —— 每次 O(n)。

换句话说：232 之所以成立是”负负得正”，225 之所以不成立是”正正还是正“。这也是这两道题被放在一起考的意义。

20. Valid Parentheses

题意： 给出字符串s，看s里面的括号是不是匹配的。

Input: s = “()[]{}” Output: true

Input: s = “([)]” Output: false

解：三种情况字符串是否匹配：

第一种：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以不匹配；

第二种：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以不匹配；

第三种：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号，不匹配；

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

535.Encode and Decode TinyURL

题意：设计一个短网址服务：把长 URL 编码成短 URL，并且能把短 URL 解码还原成原来的长 URL。

注意题目原文明确说了 “There is no restriction on how your encode/decode algorithm should work”——对编码方式没有任何限制，只要求 encode 之后能 decode 回去。下面用「6 位数字字母」和「只编码域名后的部分」都是自己的设计选择（62^6 约 568 亿，够用），不是题目要求。

解：关键在于设计两个map，一个是从tiny到普通（map1），一个从普通到tiny（map2）。普通到tiny的时候，可使用随机生成tiny的算法，生成之后保存普通到tiny的映射和tiny到普通的映射，每次遇到普通URL之前，先查map2，看是否已经有对应的tiny了，没有才去调用随机生成算法。

随机算法的过程是：使用数组保存所有数字和字母，然后从中随机取数组的下标，取6次拼接成tiny。

还原只需要从map1中取即可。

146.LRU Cache

题意：实现一个（key，value）数据结构的LRU缓存。要实现O（1）时间的取值和存值两个函数。

解：LRU就是将新访问的值，更新到序列的最前面，每次缓存满了，置换的时候，把序列最后面的元素置换掉。

使用hash表＋双向链表。双向链表用于保存值。使用双向链表的原因是可以在O（1）时间内删除元素，也可以在O（1）时间内在头部插入元素。

hash表记录cache中是否存在该元素。也就是保证O（1）时间内查找到有没有命中。

自己实现双向链表。注意的是删除操作，删除操作后要返回值，以便在map中删除对应的值。

PS. 如果使用c++ list（本身就是双链表）实现。实现时候要注意的是list想要在O（1）时间删除，那么必须传给他的是迭代器。

所以hashmap的第二个元素是list的迭代器。要注意的是迭代器失效问题。如果list使用erase，那么erase的迭代器会失效，相应的map中装入的迭代器将会失效。解决迭代器失效的方案是：在修改list之后，要更新map中的迭代器。

460.LFU Cache

题意：实现一个（key，value）数据结构的LFU缓存。要实现O（1）时间的取值和存值两个函数。LFU（Least Frequently Used）是最不经常使用置换算法（注意不是「最近最不常用」——「最近」是LRU的关键词，LFU看的是频率）。注意的是LFU不是保存所有的页面的使用频率，而是只记录缓存中页面的访问频率，如果一个页面被换出了，那么下次他加载之后，访问次数还是从1开始算起。 总之，置换策略是优先看访问频率，如果访问频率一样，那么出最近未使用的那个。

一句话抓住本质：

LFU = 按频率分桶的 LRU。每个桶内部就是一个小 LRU，另外用一个 minFreq 告诉你该动哪个桶。

解：需要维护四样东西，注意第四样是一个普通的 int，但少了它淘汰就做不到 O(1)：

为什么必须有 minFreq：淘汰时要找「频率最小的那一桶里最旧的那个」。如果不记录最小频率，就只能遍历 freqToKeys 去找最小值，那是 O(最大频率)，不是 O(1)。

容器选择：桶需要同时支持「O(1) 删任意元素」（提频时要把 key 从旧桶挪走）和「O(1) 取最旧的」（淘汰时）。Java 用 LinkedHashSet 两条都满足，插入顺序天然就是时间先后。C++ 用 list 的话，还需要额外一张 key -> 迭代器 的表，因为 list 要 O(1) 删任意元素必须给它迭代器——那张表是容器选择带来的，不是算法本身需要的。普通 HashSet 不行（无序），普通队列也不行（不能 O(1) 删中间元素）。

三个操作

核心动作叫提频，get 命中和 put 命中都要做一次：

touch(key):
    c = keyToCnt[key]
    keyToCnt[key] = c + 1
    从 freqToKeys[c] 删掉 key
    若 freqToKeys[c] 空了:
        删掉该桶
        若 minFreq == c:  minFreq = c + 1        ← 关键
    把 key 加到 freqToKeys[c+1] 的末尾

get(key):
    不存在 -> 返回 -1
    存在   -> touch(key)，返回 keyToVal[key]

put(key, val):
    已存在 -> keyToVal[key] = val; touch(key); 返回
    不存在:
        若已满 -> 淘汰：取 freqToKeys[minFreq] 的队首（最旧的），从各表中全删掉
        插入：keyToVal[key] = val, keyToCnt[key] = 1, freqToKeys[1] 末尾加 key
        minFreq = 1                               ← 无条件

两个微妙点（真正难的地方）

（1）minFreq 只在两处变化，而且提频时只会 +1。

• 插入新元素 -> minFreq = 1，无条件。因为新元素频率是 1，不可能有更小的。
• 提频后原桶变空、且原桶正好是 minFreq -> minFreq++。

为什么只 +1、不会跳更多？因为刚被提频的那个 key 此刻就落在 minFreq+1 这个桶里，那个桶一定非空。所以最小频率最多往上挪一格。

（2）桶内必须保持时间顺序。

因为「频率相同时淘汰最久未使用的」——这是 LFU 里面内嵌的一个 LRU。所以桶不能是无序集合，必须能按时间取出最旧的那个。

与 146 LRU 对照

看清这张表，LFU 就不是一个新结构，而是 LRU 加了一层「按频率分桶」的包装。

380. Insert Delete GetRandom O(1)

题意：实现一个集合类 RandomizedSet，支持三个操作，平均时间复杂度都要 O(1)：

• insert(val)：不存在则插入并返回 true，已存在则返回 false（集合语义，不允许重复元素）
• remove(val)：存在则删除并返回 true，不存在则返回 false
• getRandom()：随机返回集合中的一个元素，且每个元素被返回的概率必须相等

题目原文：“Each element must have the same probability of being returned.” 「等概率」这一条是整道题的题眼——正因为要等概率，才必须有一个支持 O(1) 随机下标访问的连续容器（vector）；纯 hash 容器做不到。

PS. 允许重复元素的版本是 381 Insert Delete GetRandom O(1) - Duplicates allowed。

骨架：三条要求各逼出一个部件

要「等概率随机」   → 必须能 O(1) 按下标随机访问 → 连续容器（vector / ArrayList）
要「O(1) 删任意」  → 但连续容器中间删是 O(n)   → 用「换到尾部再删尾部」
要「知道 val 在哪」→ hash 表：val -> 它的下标

三条要求各逼出一个部件，缺一不可。这不是拼凑出来的结构，是被要求推出来的。

解：此题如果直接使用unordered_set，想使用it + randomNum来在集合中取数是不行的，因为集合的迭代器不支持随机跳转，还是需要循环的++it操作，时间复杂度是O（n），不符合要求。「等概率随机」这条要求，逼着我们必须有一个能按下标直接访问的连续容器。

所以关键是设计数据结构：hash表 + vector。hash表存「元素 -> 元素在vector中的下标」，vector装实际的元素。

删除的四步（顺序不能换）：

i = idx[val]                      找到它在 vector 中的位置
last = vector 最后一个元素
① vector[i] = last                用尾部元素覆盖掉要删的位置
② idx[last] = i                   更新尾部元素的新下标
③ 删掉 vector 的尾部              连续容器删尾部是 O(1)
④ idx.erase(val)                  最后才把 val 从 hash 表移除

为什么 ② 必须在 ④ 之前：要删的元素可能正好就是最后一个（此时 last == val）。如果先把 val 从表里删掉、再执行 idx[last] = i，等于把刚删掉的键又加回去了，表里留下一个幽灵键，下次插入同一个值会误判为「已存在」。

为什么「换到尾部」是安全的：getRandom 只要求等概率，不要求任何顺序。所以元素在 vector 里怎么排都无所谓，把尾部元素搬到洞里，数组依然紧凑、随机下标依然等概率。反过来说，如果题目要求维持插入顺序，这个技巧就用不了了——「无序」这个自由度正是被这个解法吃掉的。

heap的数组实现中删除堆顶也用到了这个技巧（拿最后一个元素填坑），目的一样：保持数组紧凑，不在中间留洞。

PS.（1）c++随机数使用方法：srand(time(0))配合rand（）；Java用Random的nextInt(size)。

（2）Java 里有个重载陷阱：list.remove(list.size() - 1) 传的是 int，调用的是按下标删除，O(1)，这是我们要的；而 list.remove(Integer.valueOf(x)) 传的是 Object，会变成按值查找删除，O(n)。List<Integer> 上这两个重载极易搞混。另外 Integer i = map.get(val) 之后要判 null，别直接赋给 int，否则不存在时会 NPE。

（3）允许重复元素的版本是 381. Insert Delete GetRandom O(1) - Duplicates allowed：把 hash 表改成 val -> 下标集合，删除时从集合里任取一个下标做同样的换尾操作。那题的坑更大，因为 last == val 且集合中有多个下标时，更新集合的先删后加顺序要格外小心——和上面第 ② 步是同一类问题的放大版。

157. Read N Characters Given Read4

题意：给出read4，让实现readn。

解：此题不是简单的逻辑题，而是c风格的文件处理的问题。首先，使用read4之前，必须要自己配备一个缓冲区，其次，外面readn已经给readn配好缓存区了。另外，readn也要考虑下面情况：一个是文件中多于n个字符，以及文件中小于n个字符的情况。 如果是文件少余n个字符，那么也要尽可能的多读出来，也就是说，最终返回的值是能读出来的字节数，而参数buf只是给全局缓冲区返回读取的结果。

另外，还要注意字符小于4的时候，readn调用read4得出来的字符数不是4个，要单独处理。技巧就是如果使用read4读出来不足4个，那么说明文件里面字符不够了，

或者还有一种情况是如果读出来的4个加上已读出的大于n了，那么也要停止了。

158. Read N Characters Given Read4 II - Call multiple times

题意：此题与157的区别是，多次调用。调用一次的时候，多读出来无所谓，因为这一次读文件目的达到了，而多次调用不一样，因为文件已经打开了，大家应该去共享文件流指针，例如其中一次的read4，如果是其中只使用了2个字符，但是把后面2个字符提前读出来了，该怎么办。

解：解决方法是把之前read4多出来的字母做一个全局的缓存。设置一个temp字符数组和p指针，p指向buf数组中属于下一次调用的开始字母。len_t记录temp数组中的字符数量，因为不是每一次都能读出来4个字符。每当p小于count时候，从temp中读出结果写入buf结果数组，当p等于len_t的时候，p重置为0。设置index标记buf数组的字符总数，并作为结果返回。

341. Flatten Nested List Iterator

题意：设计一个迭代器把嵌套列表（nested list，即 List<NestedInteger>，每个元素要么是一个整数、要么又是一个列表）压平。next 取出压平之后的下一个单元素，hasNext 判断还有没有。

注意是列表不是链表——和 next 指针、链式存储没有关系，本质是一棵多叉树。

解：先递归把数组压平，存到queue里面，然后一个一个的取是不符合题意的，不可取。 此题思路是，以[[1, 1], 2]为例，如果要访问第一个1，那么先要解析整个[[1, 1], 2]，以及内部的[1,1]。 类似于先序遍历操作。给出的 getList 的实际操作相当于一次返回当前结点的全部子节点（这是多叉树，不是二叉树，所以没有「左子树」这回事）。使用栈，把下一层（getlist）的NestedInteger倒着压栈，然后每次取的时候，看栈顶是不是嵌套的（isInteger），如果是，那么就接着对栈顶getlist，倒着入栈，直到栈顶是一个非嵌套的单元素，那么返回true，说明hasNext。取出的时候，如果栈不为空，直接取栈顶即可。

PS. hashnext里面就要把栈顶处理为单元素，因为嵌套的integer可能为空，然后在栈里，可以让人误以为还元素可以弹出来，实际上并不是。

284. Peeking Iterator

题意：迭代器类已经提供了next和hasnext的接口了，现在要一个新的接口peek，而新类要继承以前的类。

解：网上说是装饰器模式。此题peek其实就是next指向的位置，唯一区别是next调用一次迭代器会变化，而调用peek不应该使得迭代器后移，所以peek不可以直接通过调用next来达到。 所以正确做法是缓存一组子类接口的结果，也就是next的返回值和hasNext的返回值。然后，取peek的时候，返回缓存下来的next结果就可以了，如果取next，那么就需要先保留上一个next，然后更新缓存hasNext并看是不是true（第一次的hasNext在构造函数中使用），如果是的话，那么更新缓存的next，然后返回上一个保留的next就可以了。如果取hasNext，那么就是直接返回缓存中的hasNext就可以了。

关键是一开始就取一对下来。

1206. Design Skiplist

题意：设计Skiplist，支持O(logN)的add、erase和search。

注意这个O(logN)是期望复杂度（依赖随机化，最坏情况可以退化到O(N)），而红黑树是最坏情况保证O(logN)。所以严格说两者不一样：跳表的平均性能与红黑树相当，但放弃了最坏情况保证，换来的是代码短得多、也容易实现得多。实现快速搜索的原理是基于随机概率算法实现的二分搜索，其中，使用logN的额外空间来存放冗余信息。 实现的数据结构是链表，具体来说，分为N层链表，第0层存放所有元素，第1层是第0层元素50%概率的复制，第2层是第1层元素50%概率的复制，以此类推。 //
// level 3: -Inf —————————-> 4 // level 2: -Inf ————> 2 ————> 4 // level 1: -Inf —-> 1 —-> 2 ————> 4 // level 0: -Inf —-> 1 —-> 2 —-> 3 —-> 4 解：此题难点是实现。一种实现方法的关键：

• 维持一个最高层的链表头指针leftTopHead
• 每层链表都要包含dummy node作为头节点。 search(num)：从leftTopHead开始，往右走，找到最后一个比num小的点。现在看下一个节点，如果等于num，说明元素存在；

否则向下走，如果走到最后一层还是不能发现下一个节点等于num的情况，那么说明元素不存在。

erase(num)：思路和search一样，但是区别是找到num的时候，不能提前停止，而是继续向下走，把下层的num也删除掉。

add(num)：最难的操作，难点在于，先要找到第0层的插入位置，之后才能按概率向高层加备份节点。可以使用栈结构来保存 1到N层的插入位置，这样就不需要链表节点支持向上走的操作了。 细节在于，在第N层插入的时候，此时说明第N层不再是一个元素了，此时需要新建一层，即第N+1层。

• 上一篇
  Leetcode按题目类型总结（六）
• 下一篇
  Leetcode按题目类型总结（八）