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

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

一、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<Node, Node> 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 <= temp2.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;
    }
}

四、23. 合并 K 个升序链表

题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked
思路：使用优先级队列存放链表，出队后拼接链表，然后在把下一个节点入队。

/**
 * 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; }
 * }
 */
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> 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<Integer, Integer> 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 <= map.size()) {
            Integer first = map.keySet().iterator().next();
            map.remove(first);
        }
        map.put(key, value);
    }
}