合并K个升序链表
解法一
仿照两个升序链表合并一直循环
使用一个新节点res保存最终链表的头节点
然后循环遍历ListNode数组来与res来进行合并
时间复杂度
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) return null; ListNode res = null; for(ListNode t : lists){ // 遍历 ListNode newHead = new ListNode(); ListNode temp = newHead; while(res != null && t !=null){ //合并 if(res.val < t.val){ temp.next = res; res = res.next; }else{ temp.next = t; t = t.next; } temp = temp.next; } if(res != null) temp.next = res; if(t != null)temp.next = t; res = newHead.next; } return res; } }
解法二
使用归并排序
每两个链表进行合并后返回新链表的头节点
时间复杂度
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) return null; return div_list(lists,0,lists.length-1); } public ListNode div_list(ListNode[] lists,int left,int right){ if(left > right) return null; if(left == right) return lists[left]; int mid = (right + left) / 2; ListNode l = div_list(lists,left,mid); ListNode r = div_list(lists,mid+1,right); ListNode res = new ListNode(); ListNode t = res; while(l != null && r != null){ if(l.val < r.val){ t.next = l; l = l.next; }else{ t.next = r; r = r.next; } t =t.next; } if(l != null)t.next = l; if(r != null)t.next = r; return res.next; } }
二叉树展开为链表
解法一
先进行前序遍历保存节点
然后再重构
class Solution { public void flatten(TreeNode root) { if(root == null) return; ArrayList<TreeNode> list = new ArrayList<TreeNode>(); pre(root,list); TreeNode r = list.get(0); // 获得第一个节点 for(TreeNode t:list){ if(t == r)continue; r.left = null; r.right = t; r = t; } } // 前序遍历结果 public void pre(TreeNode root,List<TreeNode> list){ if(root == null) return; list.add(root); pre(root.left,list); pre(root.right,list); } }
解法二
将前序遍历与重构一起进行运行
注意：由于递归的前序遍历不会保存孩子的信息，而我们修改过后会使树的结构混乱，所有我们需要提前保存孩子节点
class Solution { TreeNode pre; public void flatten(TreeNode root) { if(root == null) return; pre(root); } // 前序遍历结果 public void pre(TreeNode root){ if(root == null) return; TreeNode l = root.left; TreeNode r = root.right; if(pre == null) pre = root; // 起始位置 else { pre.left = null; pre.right = root; pre = root; } pre(l); pre(r); } }
解法三
寻找前趋节点
我也是第一次见这个做法
首先这个节点如果没有左孩子，那么就只需要看右孩子
如果存在左孩子，就把右子树挂在左子树的最右边孩子的右边
然后把当前节点的右孩子设置为左孩子
当前节点的左孩子设置为null
class Solution { public void flatten(TreeNode root) { if(root == null) return; TreeNode cur = root; while(cur != null){ if(cur.left != null){ TreeNode left = cur.left; // 左子树的头节点 TreeNode t =left; while(t.right != null){ t = t.right; } // 循环过后 t 就是前序遍历左子树的最后一个遍历到的节点 t.right = cur.right; cur.left = null; cur.right = left; } cur = cur.right; } } }
LRU缓存
解法一
HashMap+双指针
因为get与put操作都要o(1)
所有使用HashMap来存储(key,node)
class LRUCache { private Map<Integer,Node> cache = new HashMap<Integer,Node>(); private int size; //实际存放的大小 private int capacity; //最大存放大小 private Node tail,head; //头尾指针 public LRUCache(int capacity) { this.capacity = capacity==0?16:capacity; this.size = 0; this.head = new Node(); this.tail = new Node(); head.ne = tail; tail.pre = head; } public int get(int key) { Node node = cache.get(key); if(node == null) return -1; deleteNode(node); addToHead(node); return node.value; } public void put(int key, int value) { Node node = cache.get(key); if(node == null){ // 说明是新加入的节点 node = new Node(key,value); if(size < capacity){ //说明是直接加入就行 addToHead(node); size++; }else if(size == capacity){ cache.remove(tail.pre.key); deleteNode(tail.pre); addToHead(node); } cache.put(key,node); }else{ //说明key存在，需要修改value deleteNode(node); node.value = value; addToHead(node); } } public void addToHead(Node node){ Node ne = head.ne; head.ne = node; node.pre = head; node.ne = ne; ne.pre = node; } public void deleteNode(Node node){ node.pre.ne = node.ne; node.ne.pre = node.pre; // 垃圾回收 node.ne = null; node.pre = null; } } class Node{ int key; // key int value; //value Node pre; // 前一个节点 Node ne; // 后一个节点 public Node(){ } public Node(int key,int value){ this.key = key; this.value = value; } }
