前言

先說在前面，一開始是筆者的閒聊，如果不想看閒聊 part 可以下滑到 『正文』

大家好，我是 Emily，距離上次參加鐵人賽已經是三年前了，其實參加過一次之後就大概知道什麼樣類型題目比較適合這樣每天發文，首先如果是學新技術肯定不適合，因為學習曲線並不是穩定成長，每天都有進度的，即便你自制力超強可以每天都學習，真的要輸出成文章的時候你會發現分段上沒那麼容易，要嘛是一篇文章很長，一篇文章有點水。因此，會發現，每篇都平均分配的文章甚至是得獎的文章，其實大多數都是在一開始就規劃好內容了，用以終為始的方式把整個大綱定出來，除非你是大神，下筆如有神(?)

好，這是上述筆者的觀察，也因此我這兩三年來一直有想學的新技術，但是卻沒有把它作為寫文的目標，而是直接就去學去用了。不過呢？養成習慣這件事，其實就非常適合拿來作為每日一文這種模式，剛好每次想養成刷題習慣，都一直宣告失敗，很討厭，乾脆給自己一個不得不寫題的動力，也就讓這個系列文誕生了 ～

這次我打算採用 Leetcode面试高频题分类刷题总结這個系列文開始，平日寫一題，假日寫一到三題，並且有把格式都整理好了，讓自己每天只要專注在解題，把思路寫下來就好

正文要開始嘍，今天要寫的題目有兩題 148. Sort List 與 56. Merge Intervals

正文

148. Sort List

題目說明

題目敘述很直接，就是把一個 linked list 依照升冪排序

解題思路

這題會使用到 Merge Sort，步驟如下：

1. 使用快慢指針，將 list 中點找到
2. 透過中點將 list 分成左半與右半
3. 左半與右半再分別呼叫主函式 sortList
4. 之後在撰寫一個 merge function ，將兩個排序好的 list 合併

程式碼

# 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: Optional[ListNode]) -> Optional[ListNode]:
        
        # 判斷 head 存在否以及判斷 表裡是不是只有一個截點
        if not head or not head.next:
            return head
        
        # 用快慢指針找中點
        slow, fast = head, head.next
        
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        
        # 將 linkedlist 分成兩半
        mid, slow.next = slow.next, None
        
        left = self.sortList(head)
        right = self.sortList(mid)
        
        return self.merge(left, right)
        
    def merge(self, left, right):
        dummy = ListNode()
        curr = dummy
        
        while left and right:
            if left.val < right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next
            curr = curr.next
            
        if left:
            curr.next = left
        if right:
            curr.next = right
            
        return dummy.next

其他討論

• Merge function 在做的事，就是 21. Merge Two Sorted Lists 在做的事，一模一樣
• Merge Sort 的概念通常會跟 divide and conquer 有關

參考資料

1. ChatGPT(2023-09-10)。ChatGPT。摘自 來源 (2023-09-10)

56. Merge Intervals

題目說明

給定一個 array intervals，
裡面每個元素為一個區間 = [start, end]
將這些區間 merge 後，回傳所有 無交集的區間

解題思路

這題參考 guan 大的解題方法，用差分投影的方式

• 令每一個時間點是 start or end ，給予 1 或 -1
• 將這些時間點全部投影到一條時間軸上
• 投影之後，依照 +1/-1 將 sum 累加起來
  
• 當 sum 從正數變成 0 的過程，就是一個 merge 後的區間，如圖中橘色線
  

當有遇到一個時間點同時是 start 或 end 時，以這題來說，要優先考慮 start ，也就是在計算 sum 的時候要先加 1(有的時候會遇到先考慮 end 的部分，則代表需要視為兩個區間)

程式碼

此版本在 space 部分還有許多可優化的空間，例如 diff 內放的結構可以不要是 list

class Solution:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        diff = []
        for interval in intervals:
            diff.append([interval[0], 1])
            diff.append([interval[1], -1])
        diff = sorted(diff, key = lambda x: (x[0], -x[1]))

        res = []
        sum, start, end = 0, 0, 0
        for interval in diff:
            if sum == 0 and interval[1] == 1:
                start = interval[0]
            elif sum + interval[1] == 0:
                end = interval[0]
                res.append([start, end])
            sum += interval[1]
        return res

語法說明

1. lambda 排序

   sorted(diff, key = lambda x: (x[0], -x[1]))
   

   • x : diff 內的一個元素 也就是 [timestamp, 1 or -1]
   • (x[0], -x[1]) : 優先以 x[0] 升冪排序，遇到 x[0] 相同者再以 x[1] 排序，-x[1] 代表以 x[1] 降冪排序

相關題目

meeting rooms, events
Guan 大 github(扫描线 / 差分数组)

參考資料

1. Huifeng Guan（2022-05-14）。【每日一题】LeetCode 56. Merge Intervals。摘自 Youtube (2023-01-08)
2. Albert Mathews（2022-03-02）。how-to-sort-with-lambda-in-python。摘自 stackoverflow (2023-01-08)
3. Emily Wang（2023-01-08）。自製圖片 in Canva。摘自 Canva (2023-01-08)