【字节企业题库】链表之合并两个有序链表、LRU缓存机制、反转链表II【一日三题】

【字节企业题库】链表之合并两个有序链表、LRU缓存机制、反转链表II【一日三题】

字节跳动企业题库，链表系列，因为有leetcode会员能看到企业出题频率，那我们从出题频率最高刷到最低，题目有21. 合并两个有序链表 、146. LRU缓存机制、92. 反转链表II

21. 合并两个有序链表

【简单】【题目描述】将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1：输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]示例 2：输入：l1 = [], l2 = [] 输出：[]示例 3：输入：l1 = [], l2 = [0] 输出：[0]

这道题是一到老生常谈的题目，对于熟悉链表的同学来说是秒杀的，我们分递归和迭代两种方法解题【迭代、递归】图解：

/** * 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 { /* 递归法：O(m+n)，空间复杂度O(m+n) */ public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 如果两个链表有一个为空，递归结束。 if (l1 == null) { return l2; } if (l2 == null) { return l1; } // 判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。 if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }}

23. 合并K个有序链表

【困难】【题目描述】给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [   1->4->5,   1->3->4,   2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：输入：lists = [[]] 输出：[]

【暴力、递归、迭代】图解：

/** * 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 { /*K 指针：K 个指针分别指向K条链表;每次O(K)比较K个指针min, 时间复杂度O(NK)*/ public ListNode mergeKLists(ListNode[] lists) { int k = lists.length; ListNode dummyHead = new ListNode(0); ListNode tail = dummyHead; while (true) { ListNode minNode = null; int minPointer = -1; for (int i = 0; i < k; i++) { if (lists[i] == null) { continue; } if (minNode == null || lists[i].val < minNode.val) { minNode = lists[i]; minPointer = i; } } if (minPointer == -1) { break; } tail.next = minNode; tail = tail.next; lists[minPointer] = lists[minPointer].next; } return dummyHead.next; }}

class Solution { /*两两合并 - 迭代*/ public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) { return null; } int k = lists.length; while (k > 1) { int idx = 0; for (int i = 0; i < k; i += 2) { if (i == k - 1) { lists[idx++] = lists[i]; } else { lists[idx++] = merge2Lists(lists[i], lists[i + 1]); } } k = idx; } return lists[0]; }}class Solution { /*两两合并 - 递归*/ public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) { return null; } return merge(lists, 0, lists.length - 1); } private ListNode merge(ListNode[] lists, int lo, int hi) { if (lo == hi) { return lists[lo]; } int mid = lo + (hi - lo) / 2; ListNode l1 = merge(lists, lo, mid); ListNode l2 = merge(lists, mid + 1, hi); return merge2Lists(l1, l2); }}

146. LRU缓存机制

【中等】【题目描述】运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用) 缓存机制  实现 LRUCache 类： LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？示例：输入： ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出：[null, null, null, 1, null, -1, null, -1, 3, 4]解释： LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1);    // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2);    // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1);    // 返回 -1 (未找到) lRUCache.get(3);    // 返回 3 lRUCache.get(4);    // 返回 4

【模拟法】图解：

public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key = _key; value = _value;} } private Map cache = new HashMap(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 如果 key 存在，先通过哈希表定位，再移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // 如果 key 不存在，创建一个新的节点 DLinkedNode newNode = new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); ++size; if (size > capacity) { // 如果超出容量，删除双向链表的尾部节点 DLinkedNode tail = removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } } else { // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部 node.value = value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; }}/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。