1.1-50
| 206. 反转链表 | 思路：递归函数返回一个反转后的链表 细节：节点a的next节点为b，则以b开头的子链表反转后的尾节点是b，b的next应该为a， 注意得到b之后置a.next = null防止循环链表 |
|---|---|
| 146. LRU缓存机制 | 思路：map+双向链表、head、tail、size、count 1. map保存{key:Node} 1. 双向链表链接Node 1. Node保存key、val、pre、next 1. 由于java内置的LinkedList无法O(1)删除一个元素，所以自定义一个双向链表 |
put(int key, int val)：
1. key存在时，更新map的val和双向链表中的key的位置到tail；
1. key不存在要判断是否超过最大存储个数，超过就需要删除头节点，然后map新增一个key-val，双向链表tail追加一个key
get(int key)：
1. key存在时更新map的val和双向链表中的key的位置到tail
1. key不存在返回-1
如何更新双向节点位置到tail
1. remove(node)
1. addTail(node)
addTail(Node node)：
1. 注意初始化head、tail
remove(Node node)：
1. 注意node为head、tail的情况
1. 注意node的pre、next为null的情况
（1）执行addTail(node）时不要使用map.size()来判断链表中节点数量，因为当链表节点为空时，如果先执行map.add(key,node)，后addTail(node)会判断错误，链表中节点此时为空，但map.size()为1
（2）put(key,value)时，map移除最久未使用的key时，不能用map.remove(head.key)因为如果先执行remove(head)那么head可能会被修改，所以使用一个局部变量来记录head |
| 3. 无重复字符的最长子串 | 思路：滑动窗口
map保存{key:index}，每次移动右指针right，重置左指针left = max(left,map.get(key)+1)，计算最大不重复子串长度
遇到重复字符直接重置left的原因：
1. 设老left为oldLeft, 在[oldLeft, map.get(c)]这个区间内所有元素，作为left能构成的不重复字符的子串都小于等于[oldLeft, map.get(c)-1]的长度
|
| 215. 数组中的第K个最大元素 | （1）排序（升序），第k个值，O(NlogN)
（2）堆：小根堆（存放最大的n-k+1个元素，第k大元素为堆顶)、大根堆(存放所有元素，删除k-1个元素后，第k大元素为堆顶）
容量大小为n-k+1的小根堆，将数组所有元素放入小根堆中，最后堆顶元素为第k大，O(n-k+1+Nlog(n-k+1))=O(NlogN）
将所有元素放入大根堆中，然后删除k-1个元素后堆顶元素为第k大，O(n+KlogN）=O(NlogN）
（3）快速选择，partition，O(N），使用随机化则递归深度为log(N)，遍历的所有序列长度为等比数列N、N/2、N/4、…、1，总和O(N)
每次partition可以确定一个位置的元素（idx），当idx
难点：自己实现堆、自己实现快速选择、随机化快速选择 |
| 25. K 个一组翻转链表 | 思路：递归
设f(node)可以返回k个一组翻转的链表，g(node)可以将node整个翻转则从node开始的后面k个元素作为一个单链表使用g翻转后，然后使用f(kAfterNode)对node的第k+1元素开始的子链表进行k个一组的翻转
注意：得到前k个元素的链表时，判断是否个数足够，且保存第k个节点和k+1个元素节点，对前k个元素整个翻转后，置node.next = f(kAfterNode) |
|
| |
| | |
| | |
| | |
| | |
2.51-100
3.101-150
4.151-200
5.201-250
5.251-300
若有收获，就点个赞吧
0 人点赞
