【力扣hot100】刷题笔记Day10

前言

一鼓作气把链表给刷完！！中等题困难题冲冲冲啊啊啊！

25. K 个一组翻转链表 - 力扣（LeetCode）

模拟

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 翻转链表前k项
        def reverse(head, k):
            pre, cur = None, head
            while cur and k:
                temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
                k -= 1
            return pre, head  # pre为头，head为尾
        dummy = ListNode(0, head)
        pre = cur = dummy
        count = k  # 用于重复计数
        while cur.next and count:
            count -= 1
            cur = cur.next
            if count == 0:
                temp = cur.next  # 存一下段后节点
                pre.next, cur = reverse(pre.next, k)  # 连接段前+翻转
                cur.next = temp  # 连上段后节点
                pre = cur  # 更新pre指针
                count = k  # 恢复count继续遍历
        return dummy.next

138. 随机链表的复制 - 力扣（LeetCode）

路飞的题解真是太强啦！！优雅清晰简洁

哈希表

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        dic = {}
        # 1. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        cur = head
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        # 2. 构建新节点的 next 和 random 指向
        cur = head
        while cur:
            dic[cur].next = dic.get(cur.next)
            dic[cur].random = dic.get(cur.random)
            cur = cur.next
        # 3. 返回新链表的头节点    
        return dic[head]

拼接 + 拆分

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        dic = {}
        # 1. 复制各节点，并构建拼接链表
        cur = head
        while cur:
            temp = Node(cur.val)
            temp.next = cur.next
            cur.next = temp
            cur = temp.next
        # 2. 构建各新节点的 random 指向
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3. 拆分两链表
        cur = newhead = head.next
        pre = head
        while cur.next:
            pre.next = pre.next.next
            cur.next = cur.next.next
            pre = pre.next
            cur = cur.next
        pre.next = None  # 单独处理原链表尾节点
        return newhead  # 返回新链表头节点

148. 排序链表 - 力扣（LeetCode）

归并排序（顶到底递归）

参考路飞题解

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        # 快慢指针分割链表
        slow, fast = head, head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid = slow.next  # 右半部分的头节点
        slow.next = None  # 断开两部分
        # 递归进行归并排序
        left = self.sortList(head)
        right = self.sortList(mid)
        # 合并左右两个链表
        dummy = cur = ListNode(0)
        while left and right:  # 根据大小依次插入新链表
            if left.val < right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left if left else right  # 接上剩下的
        return dummy.next

归并排序（底到顶合并）

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # 合并两个有序链表
        def merge(head1, head2):
            dummy = cur = ListNode(0)
            while head1 and head2:
                if head1.val < head2.val:
                    cur.next = head1
                    head1 = head1.next
                else:
                    cur.next = head2
                    head2 = head2.next
                cur = cur.next
            cur.next = head1 if head1 else head2
            return dummy.next
        # 如果只有一个节点直接返回head
        if not head: return head
        # 统计链表长度
        lenth = 0
        cur = head
        while cur:
            cur = cur.next
            lenth += 1
        # 开始循环合并
        dummy = ListNode(0, head)
        sublenth = 1
        while sublenth < lenth:
            pre, cur = dummy, dummy.next
            while cur:
                head1 = cur
                for i in range(1, sublenth):
                    if cur.next:
                        cur = cur.next
                    else:
                        break  # 如果还没找到head2说明不用合并，下一轮
                head2 = cur.next
                if not head2: break  # 空就不合并了
                cur.next = None  # 断开第一段后
                cur = head2
                for i in range(1, sublenth):
                    if cur.next:
                        cur = cur.next
                    else:
                        break
                temp = cur.next  
                cur.next = None  # 断开第二段后
                cur = temp
                merged = merge(head1, head2)  # 合并
                pre.next = merged
                while pre.next:
                    pre = pre.next  # pre更新到合并后链表的最后
                pre.next = temp  # 重新连接第二段后
            # 下一轮合并
            sublenth *= 2
        return dummy.next

23. 合并 K 个升序链表 - 力扣（LeetCode）

依次合并

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 合并两个有序链表
        def merge(head1, head2):
            dummy = cur = ListNode(0)
            while head1 and head2:
                if head1.val < head2.val:
                    cur.next = head1
                    head1 = head1.next
                else:
                    cur.next = head2
                    head2 = head2.next
                cur = cur.next
            cur.next = head1 if head1 else head2
            return dummy.next
        lenth = len(lists)
        if lenth == 0:
            return None
        # 每遍历一个链表就合并掉
        dummyhead = ListNode(0)
        for i in range(0, len(lists)):
            dummyhead.next = merge(dummyhead.next, lists[i])
        return dummyhead.next

分治合并

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 如果输入为空，直接返回空
        if not lists:
            return 
        # 获取链表列表的长度
        n = len(lists)
        # 调用递归函数进行合并
        return self.merge(lists, 0, n-1)
    
    def merge(self, lists, left, right):
        # 当左右指针相等时，表示只有一个链表，直接返回该链表
        if left == right:
            return lists[left]
        # 计算中间位置
        mid = left + (right - left) // 2
        # 递归地合并左半部分和右半部分的链表
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)
        # 调用合并两个有序链表的函数
        return self.mergeTwoLists(l1, l2)
    
    def mergeTwoLists(self, l1, l2):
        # 若其中一个链表为空，则直接返回另一个链表
        if not l1:
            return l2
        if not l2:
            return l1
        # 比较两个链表头结点的大小，选择较小的作为新链表的头结点
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

最小堆

"""
假设有3个有序链表分别是：1->4->5, 1->3->4, 2->6。
初始时，最小堆为空。我们依次将(1,0),(1,1),(2,2)加入最小堆。
然后不断弹出最小值(1,0),(1,1),(2,2)，加入到结果链表中，
并将对应链表的下一个节点值和索引加入最小堆，直到最小堆为空。
最终得到的合并后的链表为1->1->2->3->4->4->5->6
"""
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        # 创建虚拟节点
        dummy = ListNode(0)
        p = dummy
        head = []
        # 遍历链表数组
        for i in range(len(lists)):
            if lists[i] :
                # 将每个链表的头结点值和索引加入到最小堆中
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next
        while head:
            # 弹出最小堆中的值和对应的索引
            val, idx = heapq.heappop(head)
            # 创建新节点并连接到结果链表上
            p.next = ListNode(val)
            p = p.next
            # 如果该链表还有剩余节点，则将下一个节点的值和索引加入到最小堆中
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        # 返回合并后的链表
        return dummy.next

146. LRU 缓存 - 力扣（LeetCode）

哈希 + 双向链表

借用灵神题解的图，really good

class Node:
    # 提高访问属性的速度，并节省内存
    __slots__ = 'prev', 'next', 'key', 'value'
    def __init__(self, key=0, value=0):
        # self.prev = None
        # self.next = None
        self.key = key
        self.value = value

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dummy = Node()  # 哨兵节点
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy
        self.key_to_node = dict()

    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.key_to_node:  # 没有这本书
            return None
        node = self.key_to_node[key]  # 有这本书
        self.remove(node)  # 把这本书抽出来
        self.push_front(node)  # 放在最上面
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:  # 有这本书
            node.value = value  # 更新 value
            return
        self.key_to_node[key] = node = Node(key, value)  # 新书
        self.push_front(node)  # 放在最上面
        if len(self.key_to_node) > self.capacity:  # 书太多了
            back_node = self.dummy.prev
            del self.key_to_node[back_node.key]
            self.remove(back_node)  # 去掉最后一本书

    # 删除一个节点（抽出一本书）
    def remove(self, x: Node) -> None:
        x.prev.next = x.next
        x.next.prev = x.prev

    # 在链表头添加一个节点（把一本书放在最上面）
    def push_front(self, x: Node) -> None:
        x.prev = self.dummy
        x.next = self.dummy.next
        x.prev.next = x
        x.next.prev = x

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