思路这题的关键是同时满足两个要求O(1) 查找所以要用HashMap。维护最近使用顺序所以要用双向链表。只用HashMap可以 O(1) 找到 key但不知道哪个是“最近最少使用”的只用链表可以维护顺序但查找是 O(n)。所以要把两者结合起来。数据结构设计维护一个双向链表链表头部表示最近使用的尾部表示最久未使用的。同时维护一个HashMapInteger, Node用来 O(1) 找到某个 key 对应的节点。get(key)如果 key 不存在返回-1。如果存在把对应节点移到链表头部表示最近使用过然后返回它的值。put(key, value)如果 key 已存在更新node里的value值并把节点移到链表头部。如果 key 不存在先新建节点插入链表头部并放入 map。再判断如果超过容量就删除链表尾部节点同时从 map 中移除。movetohead把当前链表中有的节点移到最前面 先removenode再addtoheadaddtohead把新建的节点插入到头部removetail移除tail.prev即最后一个节点removenode移除链表中指定节点初始head - tailhead - 1 - tail假设当前是head - A - tail要插入新节点 X注意顺序执行前 head - A - tail 第1步 node.next head.next X.next A 第2步 node.prev head X.prev head 第3步 head.next.prev node A.prev X 第4步 head.next node head.next X 执行后 head - X - A - tailremoveNode(node)假设当前是head - A - B - C - tail要删除 B执行前 A - B - C 第1步 A.next C B的前驱指向B的后继 第2步 C.prev A B的后继指向B的前驱 执行后 A - C B被摘掉moveToHead(node)就是先摘掉再插到头部。比如head - A - B - C - tail moveToHead(B) 先 removeNode(B) head - A - C - tail 再 addToHead(B) head - B - A - C - tailremoveTail()直接取tail.prev就是最久未使用的节点然后把它摘掉。class LRUCache {class Node{ int key; int value; Node prev; Node next; public Node(int key,int value ){ this.keykey; this.valuevalue; } } private final int capacity; private final MapInteger,Node map; private final Node head; private final Node tail; public LRUCache(int capacity) { this.capacitycapacity; this.mapnew HashMap(); headnew Node(0,0); tailnew Node(0,0); head.nexttail; tail.prevhead; } public int get(int key) { if(!map.containsKey(key)) return -1; Node nodemap.get(key); movetohead(node); return node.value; } public void put(int key, int value) { if(map.containsKey(key)){ Node nodemap.get(key); node.valuevalue; movetohead(node); return; } Node nodenew Node(key,value); map.put(key,node); addtohead(node); if(map.size()capacity){ Node lastnodetail.prev; removetail(); map.remove(lastnode.key); return; } } private void addtohead(Node node){ head.next.prevnode; node.prevhead; node.nexthead.next; head.nextnode; } private void removenode(Node node){ node.prev.nextnode.next; node.next.prevnode.prev; } private void movetohead(Node node){ removenode(node); addtohead(node); } private Node removetail(){ Node lastnodetail.prev; removenode(lastnode); return lastnode; }}/**Your LRUCache object will be instantiated and called as such:LRUCache obj new LRUCache(capacity);int param_1 obj.get(key);obj.put(key,value);*/二叉树的中序遍历中序遍历左根右思路1.递归 dfs(左子树) 根 dfs(右子树)先递归遍历左子树再访问当前节点把值加入结果最后递归遍历右子树2.用栈模拟递归stack一路向左从当前节点开始不断往左走把沿途节点全部压栈。这样栈顶就是最左边的节点应该最先访问。弹栈访问弹出栈顶节点把它的值加入结果这就是根的位置。转向右边把当前指针移到这个节点的右子树然后重复第1步。栈思路只要当前节点不为空或者栈也不为空就先一路把左节点push进栈当某一时刻为null时将栈顶元素出栈并且加入结果数组然后指针转向右子树重复循环继续一路把左节点push进栈保证了左 根 右class Solution {public List inorderTraversal(TreeNode root) {ArrayList resnew ArrayList();ArrayDeque stacknew ArrayDeque();TreeNode curroot;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}curstack.pop();res.add(cur.val);curcur.right;}return res;}}