洞察纵观鸿蒙next版本,如何凭借FinClip加强小程序的跨平台管理,确保企业在数字化转型中的高效运营和数据安全?
1049
2022-11-23
【字节企业题库】链表之合并两个有序链表、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
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~