浙江网站设计 site,cp网站开发搭建,wordpress是静态页面,云服务器优惠活动力扣爆刷第89天之hot100五连刷31-35 文章目录 力扣爆刷第89天之hot100五连刷31-35一、25. K 个一组翻转链表二、138. 随机链表的复制三、148. 排序链表四、23. 合并 K 个升序链表五、146. LRU 缓存 一、25. K 个一组翻转链表
题目链接#xff1a;https://leetcode.cn/problem…力扣爆刷第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/?envTypestudy-plan-v2envIdtop-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/?envTypestudy-plan-v2envIdtop-100-liked 思路使用map做一个映射记录key为旧节点value为新节点然后遍历复制新链表random值也复制过去然后再遍历一遍新链表 根据key去找value即可。 class Solution {public Node copyRandomList(Node head) {// key-旧节点 value-新节点MapNode, 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/?envTypestudy-plan-v2envIdtop-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/?envTypestudy-plan-v2envIdtop-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;PriorityQueueListNode 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/?envTypestudy-plan-v2envIdtop-100-liked 思路最近最少使用get或put都会是得该元素优先级最高容量满了就要把最久未使用的给去掉那么可以利用LinkedHashMap的特性底层采用哈希表和双向链表put方法加入的元素永远在链表的最后最先添加进来的在头结点所以可以使用Integer first map.keySet().iterator().next();获取头结点然后把头结点给去掉。
class LRUCache {LinkedHashMapInteger, 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);}
}
