这应该是这个系列最耗时间的三题了。xdm，我们坚持下去就好了。今天我们一起掌握 leetocode 的 146,148,155 题。

1. lc 146 - LRU 缓存机制

  • 题目来源
  • 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
  • 实现 LRUCache 类：
    • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
    • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
  • 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
  • 难度：中等

1.1 解题思路 - 哈希表 + 双向链表

键值对可以用哈希表储存，由当缓存容量达到上限时和最久未操作便要删除数据可知，当前操作的数据要与之前数据判重，若重复应该将其变换在数据结构中的位置。我们能想到将其放在头部，要删除的数据放置在尾部，因此可用双向链表。

从而，LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

这个官方解答很详细：

官方解答

在 Python 语言中，有一种结合了哈希表与双向链表的数据结构 OrderedDict；在 Java 语言中，同样有类似的数据结构 LinkedHashMap 。但在面试中，面试官一般会期望读者能够自己实现一个简单的双向链表。

1.2 复杂度

  • 时间复杂度：O(1)。对于 put 和 get 都是 O(1)，因为对链表的插入删除操作都是O(1)。
  • 空间复杂度：O(1)。O(capacity)，因为哈希表和双向链表最多存储 capacity + 1 个元素。

1.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class DoubleLinkedList:
    def __init__(self, key = 0, val = 0):
        self.key = key
        self.val = val
        self.pre = None
        self.next = None # DoubleLinkedList(0)

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = dict()
        # 使用伪头部和伪尾部节点 
        self.head, self.tail = DoubleLinkedList(), DoubleLinkedList()
        self.head.next, self.tail.pre = self.tail, self.head
        

    def get(self, key: int) -> int: 
        # 如果 key 存在，先通过哈希表定位，再移到头部
        if key in self.cache.keys():
            node = self.cache[key] # 字典的value值是 DoubleLinkedList 对象
            self.move2Head(node)
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None: 
        if key in self.cache.keys():
            node = self.cache[key]
            node.val = value # 变更其数据值
            self.move2Head(node)
        else: # 如果 key 不存在，创建一个新的节点
            new_node = DoubleLinkedList(key,value)
            self.cache[key] = new_node 
            self.add2Head(new_node) # 不要忘记添加 node至链表头部

            if len(self.cache.keys()) > self.capacity: 
                removed_node = self.removeFromTail()
                # 不要忘记 删除哈希表中对应项
                del self.cache[removed_node.key] 

    def move2Head(self, node):
        self.removeNode(node)
        self.add2Head(node)
    
    def removeNode(self, node):
        node.pre.next = node.next
        node.next.pre = node.pre

    def add2Head(self, node):
        # 安排好self.head, self.head 和 node 的 next 和 pre
        tmp = self.head.next
        node.pre = self.head
        node.next = tmp
        tmp.pre = node
        self.head.next = node

    def removeFromTail(self):
        removed_node = self.tail.pre
        self.removeNode(removed_node)
        return removed_node


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

2. lc 148 - 排序链表

  • 题目来源
  • 给你链表的头结点 head ，请将其按 升序 排列并返回排序后的链表 。
  • 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
  • 难度：中等

题目要求时间空间复杂度分别为 O(nlogn) 和 O(1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序；对数组做归并排序的空间复杂度为 O(n)，分别由新开辟数组 O(n)和递归函数调用 O(logn)组成。

而根据链表特性，空间复杂度可以降低至 O(1)：

  • 数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；
  • 递归额外空间：递归调用函数将带来 O(logn)的空间复杂度，因此若希望达到 O(1)空间复杂度，则不能使用递归[1]。

此外，此题和lc 23 类似：它的输入是数组储存着多个链表，而此题输入是链表储存着多个链表。此题难点在于，lc 23 可以索引到两个链表的头尾节点，而此题需要遍历，而遍历通过 sublength 和 tail 和 cur 指针来寻找链表边界。

2.1 解题思路 - 归并排序（从底至顶直接合并）

⚠ 注意几点：

  1. tail 和 cur 指针的作用值得思考，一个用于链接归并后的子链表，一个用于遍历长链表。
  2. 合并完的head1和head2的尾结点都应该指向None，否则报错；
  3. 存在合并中发现没有head2的情况，以及head1为头节点，但sublength小于前面合并的链表的sublength的情况，统一在遍历长链表时，用break退出即可。

2.2 时间复杂度

  • 时间复杂度： O(nlogn)。 其中 N 是链表中的节点数。
  • 空间复杂度： O(1)。

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head: return head
        sublength = 1 # 初始化合并子链表长度
        # 计算链表的总长度
        list_length = 0
        cur = head
        while cur:
            cur = cur.next
            list_length += 1
        
        dummy_node = ListNode(10086)
        dummy_node.next = head

        while sublength < list_length:
            # 设定 tail 便于连接合并好两两子链表，cur 用来遍历链表
            tail, cur = dummy_node, dummy_node.next

            # 依次合并连续的两个长度为subLength的潜在链表
            while cur:
                # 获取第一个子链表
                head1 = cur 
                for _ in range(1, sublength):
                    if cur.next:
                        cur = cur.next
                    else:
                        break 
                # 获取第二个子链表
                head2 = cur.next
                cur.next = None # 第一个子链表尾节点指向 None
                
                cur = head2
                for _ in range(1, sublength): 
                    if cur and cur.next: # 在 head2 = None时，cur 可能为 None，head1 将直接加入下一层的合并
                        cur = cur.next
                    else:
                        break 
                
                # 临时储存 下一个 head1 链表的头节点
                tmp = None
                if cur: # 走到尾节点
                    tmp = cur.next 
                    cur.next = None # 第二个子链表尾节点指向 None

                merged_node = self.merge(head1, head2)
                tail.next = merged_node # 将新合并的子链表链接到原来前节点之后
                while tail.next: 
                    tail = tail.next  # tail 最终处于当前合并完链表的最后一个元素
                cur = tmp # 更新 cur 以便下次遍历 

            sublength *= 2 # 合并前子链表长度增倍

        return dummy_node.next

    def merge(self, l1:ListNode, l2:ListNode):
        '''
        两个有序链表的合并
        '''
        move = dummy_node = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                move.next = l1
                l1 = l1.next
            else:
                move.next = l2
                l2 = l2.next
            move = move.next

        # 剩下的链表直接合并到尾部
        if l1:
            move.next = l1
        elif l2:
            move.next = l2

        return dummy_node.next

3. lc 155 - 最小栈

  • 题目来源
  • 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。
  • 提示：pop、top 和 getMin 操作总是在 非空栈 上调用。
  • 难度：简单

3.1 解题思路 - 辅助栈

常数时间内检索到最小元素可知不能遍历这个栈来检索最小元素。所以，我们需要一个可以访问首位元素的辅助栈，来解决检索问题。

非空栈说明存在一个栈，它的内部是一开始一定有元素的。第一个进入栈的元素可以与这个元素相比，从而确保在这个数据结构中，进入元素时，我们一定能检索到最小值。

因此，我们可以借用一个辅助栈min_stack，用于存获取stack中最小值。

那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。

3.2 时间复杂度

  • 时间复杂度：时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。
  • 空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们已经插入 n 个元素，此时两个栈占用的空间为 O(n)。

3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = [float('inf')]


    def push(self, x: int) -> None:
        self.stack.append(x)
        min_value = self.getMin()
        self.min_stack.append(min(min_value, x))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

参考

[1] jyd. Sort List （归并排序链表）. https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/

[2] LeetCode-Solution. 最小栈. https://leetcode-cn.com/problems/min-stack/solution/zui-xiao-zhan-by-leetcode-solution/