起床時間:0800
今天居然抽到Hard...again
給你一個陣列 lists,裡面有 k 條 已經排好序 的 鏈結串列(linked list)。
請你把這 k 條串列合併成一條新的排序串列,並回傳它的頭節點。
📌 例子:
輸入:
lists = [[1,2,4],[1,3,5],[3,6]]
合併後的排序結果:
1 → 1 → 2 → 3 → 3 → 4 → 5 → 6
輸出:
[1,1,2,3,3,4,5,6]
寫了個暴力解,完全寫錯方向
盲點:
把 t 當成「有順序的子序列」在找
用 target_idx_in_t 表示要按 t 的順序配對,但題目是「最小覆蓋子字串」(minimum window),不要求順序,只要多重集合(multiset)涵蓋即可。例:t="XYZ",在 s 裡可以是 Y...X...Z。
忽略「數量」要求(重複字元)
t 可能有重複(如 "AABC" 需要兩個 A),你的做法只在意是否看過某個字,而不是每個字需要幾次。
只會「擴展」窗口,沒有「收縮」
最小視窗的關鍵是雙指針:右指針擴張、左指針在條件滿足時盡量收縮,你的程式沒有收縮步驟,因此得不到最短答案。
沒有維護「當前最佳解」
找到了覆蓋後,應該記錄最短長度並嘗試繼續縮小;你的程式沒有這個機制。
變數/流程設計導致無法正確重置狀態
實務上要用「需要表(need)」來統一管理每個字元還差幾個,而不是依賴線性前進的索引。
用一個字典紀錄 t 每個字元需要的「剩餘數量」(need)。右指針往右走、把字元扣進 need;當所有需求都滿足(missing == 0),就從左邊收縮,盡量丟掉多餘字元,同時維護目前最短答案。
坦白說,卡關。
我目前感想是刷題真的要先寫出暴力解再想哪裡重複了,怎麼優化,這樣才能真正理解題意。
這題,繼續看...