CodingTour —

ARTS #89

Algorithm

本周选择的算法题是：Merge k Sorted Lists。

规则

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won’t exceed 10^4.

Solution

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dummy = tail = ListNode(0)
        while lists:
            min_index = 0
            for i in range(1, len(lists)):
                if lists[i] and (not lists[min_index] or lists[i].val < lists[min_index].val):
                    min_index = i
            if lists[min_index] == None: break
            else:
                tail.next = lists[min_index]
                tail = tail.next
                lists[min_index] = tail.next
                if not tail.next: del lists[min_index]
        return dummy.next

基于归并排序的版本：

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return None
        half = len(lists) // 2
        if half:
            left, right = self.mergeKLists(lists[:half]), self.mergeKLists(lists[half:])
            dummy = tail = ListNode(0)
            while left and right:
                if left.val < right.val:
                    tail.next = left
                    left = left.next
                else:
                    tail.next = right
                    right = right.next
                tail = tail.next
            tail.next = left or right
            return dummy.next
        else:
            return lists[0]

Review

Mono- or Multi-repo?

一遍对比 Monorepo 和 Multirepo 各自优缺点的文章，观点很客观、公正，对于想要从 Multirepo 切换到 Monorepo 的团队来说很有借鉴价值。

Tip

Python 不仅可以这样合并字典：

dict1 = { 'a': 1, 'b': 2 }
dict2 = { 'b': 3, 'c': 4 }
merged = { **dict1, **dict2 }
print (merged)
# {'a': 1, 'b': 3, 'c': 4}

还在这样合并：

dict1 = { 'a': 1, 'b': 2 }
dict2 = { 'b': 3, 'c': 4 }
merged = dict1 | dict2
print (merged)
# {'a': 1, 'b': 3, 'c': 4}

Share

CPython 中的超级大锁。