所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
抽象数据结构一般有序列、栈、队列、集合、图（键值对）、优先级队列等。具体数据结构一般有数组、链表、hash表、二分搜索树、二叉堆等。
图的实现：使用hashmap的话，优点是直接，缺点是hashmap有内存和代码的开销；另一种可选方法就是使用数组。如果给出的输入数据是边pair，那么就看存不存在重复边，如果重复，那么就不能使用数组。
树是一种逻辑上的结构，从内存角度来看，树可能是用数组装的。
堆逻辑上看是完全二叉树，内存来看，是用数组存储的，数组下标对应了二叉树的层次从上而下，从左到右的次序，这样：每次加入新元素，只需要在数组的最后面加入一个元素，然后在后续调整；每次删除堆顶的时候，可以把在后面找一个元素替代第一个位置的元素。
具体题目
232. Implement Queue using Stacks
题意：用栈实现队列。
解：栈先进后出，队列先进先出，思路就是使用两个栈来实现队列，负负得正。在第一个栈先压栈，然后弹出到第二个栈，最后在第二个栈出。问题是存入第二个栈的时机，该时机不是每次有元素加入的时候，如果是这样，那和一个栈效果一样。 正确做法就是将两个栈当作一个整体结构，在入栈的时候，把元素存到第一个栈里面，出栈的时候，看第二个栈是不是空的，如果是，那么将第一栈里面的元素全部弹出来，放入第二个栈。
时间复杂度：平摊起来是O(1)，仅在第二个栈为空的时候，才把第一个栈的所有元素放入第二个栈，而且第一个栈不用在还原了，因为元素已经到了第二个栈里面，没有任何操作会用到第一个栈了。也就是说，每个元素只会分别入栈出栈两次。
535.Encode and Decode TinyURL
题意：给一个URL，然后把URL域名后的部分转化成tinyURL（不多不少的6位数字字母组成的字符串）。还要求可以通过TinyURL转换成原来的URL。
解：关键在于设计两个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）时间内查找到有没有命中。
如果使用c++ list（本身就是双链表）实现。实现时候要注意的是list想要在O（1）时间删除，那么必须传给他的是迭代器。
所以hashmap的第二个元素是list的迭代器。要注意的是迭代器失效问题。如果list使用erase，那么erase的迭代器会失效，相应的map中装入的迭代器将会失效。解决迭代器失效的方案是：在修改list之后，要更新map中的迭代器。
也可以自己实现双端链表。注意的是删除操作，删除操作后要返回值，以便在map中删除对应的值。
460.LFU Cache
题意：实现一个（key，value）数据结构的LFU缓存。要实现O（1）时间的取值和存值两个函数。LFU是最近最不常用置换算法。注意的是LFU不是保存所有的页面的使用频率，而是只记录缓存中页面的访问频率，如果一个页面被换出了，那么下次他加载之后，访问次数还是从1开始算起。 总之，置换策略是优先看访问频率，如果访问频率一样，那么出最近未使用的那个。
解：使用三张hash表，第一张表（设为m）存储key映射到一个pair，pair的第一个元素为key对应的value，第二个元素为key的出现次数。m表对应缓存大小。也就是说，m表是存储key信息的表。
第二张表freq，记录访问次数（频率）到关键字链表的映射，关键字链表按关键字的时间先后放，时间最近的放后面，最前面的是最远使用的。
第三张表iter，记录key在freq表中key链表中的位置。是key到key链表迭代器的映射。
380. Insert Delete GetRandom O(1)
题意：实现getRandom的类，有插入，删除，获取随机数的功能，平摊时间要求为1。
解：此题如果直接使用unordered_set，想使用it + randomNum来在集合中取数是不行的，所以还是需要循环的++it操作，因此时间复杂度是O（n），不符合要求。
此题关键是设计数据结构：就是hashmap＋vector。hashmap是存元素指向元素在vector中的下标，vector装实际的元素。这里的技巧之处在于，删除的时候为了保证O（1）时间复杂度，可以将vector最后一个元素和要删除的元素进行交换，然后在map中修改原来最后一个元素的位置,最后删除vector的最后一个元素即可。
heap的数组实现中，也用到了这个技巧来保证数组中间不会出现“洞”。
PS.c++随机数使用方法：srand(time(0))配合rand（）。
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
题意：设计把嵌套链表压平的接口，也就是说接口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。Skiplist使用O(logN)时间来add，erase以及search，这和红黑树一样，但是Skiplist代码更短，
且容易实现。实现快速搜索的原理是基于随机概率算法实现的二分搜索，其中，使用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层。
