算法日记 - Day9
排序链表
这里说要使用O ( n log n ) O(n \log n)O(nlogn)的时间复杂度，其实很容易想到需要使用排序，因为我们既要保证最终的升序顺序，又不能超过O ( n 2 ) O(n^2)O(n2)的时间复杂度，所以这里借助归并排序，我们使用迭代的方法自下而上，不使用递归自上而下，因为它的空间复杂度不是常数级
思想是什么呢？
- 我需要先知道链表长度，因为只有知道长度才能知道最终归并排序的次数（第一次 每次组合结果是相邻两个元素排好序，第二次是相邻四个元素排好序，第三次是八个）
- 怎么把排好序的链表合并呢？可以参考我们之前做过的 合并两个有序链表，把两个排好序的链表合并成一个新链表
- 我们想想归并排序，我们既然有合并操作，就需要有拆分动作，因为我们拆分之后才好排序，对拆分后的子链表排序组合，但是排好序之后我们还需要放回原链表组成一个串，所以合并之后是需要返回头节点的。因为我们排序是先排前
n个，前n个排好之后，这些元素的最后一个元素要指向后面排好序的子链表的头节点。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */classSolution{publicListNodesortList(ListNodehead){if(head==null)returnhead;intlength=getLength(head);ListNodedummy=newListNode(0,head);// 哨兵节点for(intstep=1;step<length;step*=2){// 归并排序次数ListNodepreListTail=dummy;// 前一个已经排好序的尾节点ListNodecur=dummy.next;while(cur!=null){// 拆分，相当于 2->1->3 拆分为了 2, 1, 3ListNodehead1=cur;ListNodehead2=splitList(head1,step);cur=splitList(head2,step);// 下一组需要排序的// 归并，2, 1, 3 变为 1->2, 3ListNode[]headTail=merge(head1,head2);// 一次归并排序，返回头节点尾节点// 变为 1->2->3preListTail.next=headTail[0];preListTail=headTail[1];}}returndummy.next;}ListNodesplitList(ListNodehead,intsize){ListNodecur=head;for(inti=0;i<size-1&&cur!=null;i++){cur=cur.next;}if(cur==null||cur.next==null){returnnull;}ListNodenxt=cur.next;cur.next=null;returnnxt;}intgetLength(ListNodehead){intlength=0;while(head!=null){length++;head=head.next;}returnlength;}ListNode[]merge(ListNodehead1,ListNodehead2){ListNodedummy=newListNode();ListNodecur=dummy;while(head1!=null&&head2!=null){if(head1.val<head2.val){cur.next=newListNode(head1.val);head1=head1.next;}else{cur.next=newListNode(head2.val);head2=head2.next;}cur=cur.next;}cur.next=head1==null?head2:head1;while(cur.next!=null){cur=cur.next;}returnnewListNode[]{dummy.next,cur};}}LRU缓存
第一种方式，也就是直接利用 Java 的库，双向链表LinkedHashMap，它非常适合用来实现 LRU，它是一个双向链表，并且在构造方法中指定accessOrder为 true 的话，会在访问元素的时候把元素移动到链表尾部，这样链表首元素就是最近最少被访问的元素，它还提供一个方法removeEldestEntry，它会返回一个返回值，告诉LinkedHashMap是否需要移除链表首元素。
classLRUCacheextendsLinkedHashMap<Integer,Integer>{privatefinalintcapacity;publicLRUCache(intcapacity){super(capacity,0.75f,true);// 第二个参数用默认值 0.75f 就行，第三个即 accessOrderthis.capacity=capacity;}publicintget(intkey){returnsuper.getOrDefault(key,-1);}@OverrideprotectedbooleanremoveEldestEntry(Map.Entry<Integer,Integer>eldest){returnsize()>capacity;}}也可以我们自己手写 LRU，利用 HashMap + 循环链表，也就是仿照LinkedHashMap的实现。这里我们链表末尾表示最近最少访问的
- 因为我们对每个节点都有
pre，有next，所以我们只需要一个哨兵节点
classLRUCache{// 节点staticclassNode{intkey,val;Nodepre,next;Node(intkey,intval){this.key=key;this.val=val;}}privatefinalMap<Integer,Node>keyToNode=newHashMap<>();privatefinalintcapacity;privatefinalNodedummy=newNode(0,0);// 哨兵节点publicLRUCache(intcapacity){this.capacity=capacity;dummy.pre=dummy;dummy.next=dummy;// 自己指向自己}publicintget(intkey){if(!keyToNode.containsKey(key)){return-1;}Nodex=keyToNode.get(key);remove(x);// 放到链表表头pushFront(x);returnx.val;}privatevoidremove(Nodex){x.pre.next=x.next;x.next.pre=x.pre;}publicvoidput(intkey,intvalue){// 已经包含，则更新值并放入尾部if(keyToNode.containsKey(key)){Nodecur=keyToNode.get(key);cur.val=value;remove(cur);pushFront(cur);}else{// 未包含则放入头部NodenewNode=newNode(key,value);pushFront(newNode);keyToNode.put(key,newNode);if(keyToNode.size()>capacity){// 大于容量之后需要移除头节点keyToNode.remove(dummy.pre.key);remove(dummy.pre);}}}privatevoidpushFront(Nodenode){node.next=dummy.next;node.pre=dummy;dummy.next.pre=node;dummy.next=node;}}