33、排序鏈表

給你鏈表的頭結點 head ，請將其按 升序 排列并返回 排序后的鏈表 。

示例 1：

輸入：head = [4,2,1,3]
輸出：[1,2,3,4]

示例 2：

輸入：head = [-1,5,3,4,0]
輸出：[-1,0,3,4,5]

示例 3：

輸入：head = []
輸出：[]

提示：

• 鏈表中節點的數目在范圍 [0, 5 * 104] 內
• -105 <= Node.val <= 105

思路解答：

1. 使用快慢指針找到鏈表的中點，將鏈表分為兩部分。
2. 遞歸地對左右兩部分鏈表進行排序。
3. 合并兩個已排序的鏈表。

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return headdef getMiddle(head):slow = headfast = headwhile fast.next and fast.next.next:slow = slow.nextfast = fast.next.nextreturn slowdef merge(left, right):dummy = ListNode(0)current = dummywhile left and right:if left.val < right.val:current.next = leftleft = left.nextelse:current.next = rightright = right.nextcurrent = current.nextcurrent.next = left if left else rightreturn dummy.next# 獲取鏈表中點，將鏈表分為兩部分mid = getMiddle(head)left = headright = mid.nextmid.next = None# 遞歸地對左右兩部分鏈表進行排序left_sorted = sortList(left)right_sorted = sortList(right)# 合并兩個已排序的鏈表return merge(left_sorted, right_sorted)

34、合并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 = []
輸出：[]

示例 3：

輸入：lists = [[]]
輸出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的總和不超過 10^4

思路解答：

1. 初始化一個優先隊列（heap）：首先，創建一個空的優先隊列（heap），用于存儲鏈表的頭部節點。將每個鏈表的頭部節點（值和節點本身的元組）加入到優先隊列中，并根據節點的值進行排序。
2. 創建一個虛擬頭節點和當前節點：創建一個虛擬頭節點dummy和一個指向當前節點的指針curr，初始時它們都指向虛擬頭節點。
3. 循環處理優先隊列：在一個循環中，不斷從優先隊列中彈出最小的節點。將該節點接入到合并后的鏈表中，更新當前節點指針curr。如果被彈出的節點有下一個節點，則將下一個節點（值和節點本身的元組）重新加入到優先隊列中。
4. 返回合并后的鏈表：最終，返回虛擬頭節點的下一個節點，即為合并后的鏈表的頭節點。

def mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]:setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)heap = []for l in lists:if l:heapq.heappush(heap, (l.val, l))  # 將節點的值和節點本身存入堆中dummy = ListNode(0)current = dummywhile heap:val, node = heapq.heappop(heap)  # 從堆中取出節點的值和節點本身current.next = nodecurrent = current.nextif node.next:heapq.heappush(heap, (node.next.val, node.next))  # 將下一個節點的值和節點本身存入堆中return dummy.next

35、LRU緩存

請你設計并實現一個滿足 LRU (最近最少使用) 緩存 約束的數據結構。

實現 LRUCache 類：

• LRUCache(int capacity) 以 正整數 作為容量 capacity 初始化 LRU 緩存
• int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
• void put(int key, int value) 如果關鍵字 key 已經存在，則變更其數據值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該 逐出 最久未使用的關鍵字。

函數 get 和 put 必須以 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

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多調用 2 * 105 次 get 和 put

思路解答：

1. 使用一個哈希表（dictionary）來存儲key和對應的節點。
2. 使用一個雙向鏈表來維護節點的訪問順序，鏈表頭部表示最久未使用的節點，鏈表尾部表示最近訪問的節點。
3. LRUCache類中包含get和put方法：
   • get(key)方法：
     • 如果key存在于緩存中，從哈希表中獲取對應的節點，并將該節點移動到鏈表尾部表示最近訪問。
     • 如果key不存在于緩存中，返回-1。
   • put(key, value)方法：
     • 如果key已存在于緩存中，更新對應節點的值，并將其移動到鏈表尾部表示最近訪問。
     • 如果key不存在于緩存中：
       • 創建一個新節點，插入到鏈表尾部表示最近訪問。
       • 將key和對應節點存入哈希表。
       • 如果插入操作導致緩存容量超過限制，移除鏈表頭部節點，同時從哈希表中刪除對應的鍵值對。

class ListNode:def __init__(self, key=0, val=0):self.key = keyself.val = valself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity):self.capacity = capacityself.cache = {}self.head = ListNode()self.tail = ListNode()self.head.next = self.tailself.tail.prev = self.headdef get(self, key):if key in self.cache:node = self.cache[key]self._remove(node)self._add(node)return node.valreturn -1def put(self, key, value):if key in self.cache:self._remove(self.cache[key])node = ListNode(key, value)self.cache[key] = nodeself._add(node)if len(self.cache) > self.capacity:node_to_remove = self.head.nextself._remove(node_to_remove)del self.cache[node_to_remove.key]def _add(self, node):prev_node = self.tail.prevprev_node.next = nodenode.prev = prev_nodenode.next = self.tailself.tail.prev = nodedef _remove(self, node):prev_node = node.prevnext_node = node.nextprev_node.next = next_nodenext_node.prev = prev_node