力扣爆刷第89天之hot100五连刷31-35

力扣爆刷第89天之hot100五连刷31-35

文章目录

• • • 力扣爆刷第89天之hot100五连刷31-35
    • 一、25. K 个一组翻转链表
    • 二、138. 随机链表的复制
    • 三、148. 排序链表
    • 四、23. 合并 K 个升序链表
    • 五、146. LRU ���存

      一、25. K 个一组翻转链表

      题目链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked

      （）

      思路：k个一组翻转，写好一个单独的翻转方法，然后外部控制好每次翻转的头和尾。

      class Solution {    public ListNode reverseKGroup(ListNode head, int k) {        ListNode root = new ListNode(-1, head);        ListNode p = root, fast = head;        int i = 0;        while(fast != null) {            i++;            fast = fast.next;            if(i % k == 0) {                p = reverse(p, fast);            }        }        return root.next;    }    ListNode reverse(ListNode start, ListNode end) {        ListNode p1 = start, p2 = start.next, p3 = p2;        start.next = null;        while(p2 != end) {            ListNode t = p2.next;            p2.next = p1.next;            p1.next = p2;            p2 = t;        }        p3.next = end;        return p3;    }   }

      二、138. 随机链表的复制

      题目链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked

      （）

      思路：使用map做一个映射记录，key为旧节点，value为新节点，然后遍历复制新链表，random值也复制过去，然后再遍历一遍新链表，

      根据key去找value，即可。

      class Solution {    public Node copyRandomList(Node head) {        // key-旧节点 value-新节点        Map map = new HashMap();        Node root = new Node(-1);        Node p1 = head, p2 = root;        while(p1 != null) {            Node n = new Node(p1.val);            n.random = p1.random;            map.put(p1, n);            p2.next = n;            p2 = n;            p1 = p1.next;        }        p2 = root.next;        while(p2 != null) {            if(p2.random != null) {                p2.random = map.get(p2.random);            }            p2 = p2.next;        }        return root.next;    }}

      三、148. 排序链表

      题目链接：https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked

      思路：采用归并排序，递归划分链表，直到划分到单个元素，然后再排序。

      class Solution {    public ListNode sortList(ListNode head) {        return sortList(head, null);    }    public ListNode sortList(ListNode head, ListNode tail) {        if (head == null) {            return head;        }        if (head.next == tail) {            head.next = null;            return head;        }        ListNode slow = head, fast = head;        while (fast != tail) {            slow = slow.next;            fast = fast.next;            if (fast != tail) {                fast = fast.next;            }        }        ListNode mid = slow;        ListNode list1 = sortList(head, mid);        ListNode list2 = sortList(mid, tail);        ListNode sorted = merge(list1, list2);        return sorted;    }    public ListNode merge(ListNode head1, ListNode head2) {        ListNode dummyHead = new ListNode(0);        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;        while (temp1 != null && temp2 != null) {            if (temp1.val                 temp.next = temp1;                temp1 = temp1.next;            } else {                temp.next = temp2;                temp2 = temp2.next;            }            temp = temp.next;        }        if (temp1 != null) {            temp.next = temp1;        } else if (temp2 != null) {            temp.next = temp2;        }        return dummyHead.next;    }}public ListNode mergeKLists(ListNode[] lists) {        if(lists.length == 0) return null;        PriorityQueue a.val - b.val);        for(ListNode list : lists) {            if(list != null) {                queue.add(list);            }        }        ListNode root = new ListNode();        ListNode p = root;        while(!queue.isEmpty()) {            ListNode min = queue.poll();            p.next = min;            p = min;            if(min.next != null) {                queue.add(min.next);            }        }        return root.next;    }}

      五、146. LRU 缓存

      题目链接：https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked

      思路：最近最少使用，get或put都会是得该元素优先级最高，容量满了就要把最久未使用的给去掉，那么可以利用LinkedHashMap的特性，底层采用哈希表和双向链表，put方法加入的元素永远在链表的最后，最先添加进来的在头结点，所以可以使用Integer first = map.keySet().iterator().next();获取头结点然后把头结点给去掉。

      class LRUCache {    LinkedHashMap map;    int cap = 0;    public LRUCache(int capacity) {        map = new LinkedHashMap();        cap = capacity;    }    public int get(int key) {        if (!map.containsKey(key)) {            return -1;        }        Integer val = map.remove(key);        map.put(key, val);        return val;    }    public void put(int key, int value) {        if (map.containsKey(key)) {            map.remove(key);            map.put(key, value);            return;        }        if (cap             Integer first = map.keySet().iterator().next();            map.remove(first);        }        map.put(key, value);    }}