Re: [閒聊] leetcode 大師請進已回收

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間1年前 (2024/05/06 22:16)推噓10(10推 0噓 3→)

留言13則, 9人參與討論串2/8 (看更多)

※ 引述《ZooseWu (動物園公告)》之銘言： : 幫我解題 : 我有一組不重複的正整數一維陣列 : 每次行動可以將某個數字插入另一個數字的後面 : 行動以一個長度為二的陣列[a, b]表示 a 插入 b 後面 : 如果元素要放到開頭就以插入 0 表示 : 求最小行動數的二維陣列 : ex: : 題目: [1, 3, 7, 9, 5, 2] : 答: [[2, 1], [5, 3]] : 題目: [9, 7, 5, 3, 1] : 答: [[1, 0], [3, 1], [5, 3], [7, 5]] : 或是 [[7, 0], [5, 0], [3, 0], [1, 0]] : 題目的陣列長度是三位數 : 元素都是正整數(其實沒差，不過限定正整數比較好設定排頭) 1.先把陣列分成兩堆，遞增的記住他們的索引變一個單調堆疊，非遞增的記住他們的值。 2.把非遞增的值排序。 3.從最大數字x開始處理非遞增的值，如果stack頂端大於x就把頂端元素pop，如果比較小就表示要插到頂端的右邊，如果單調堆疊已經空就插到0，因為是從大的元素開始插入所以右邊的索引變怎樣就不用管了。 py code ------------------------------------------- def min_actions(arr): res = [] s = [] ls = [] for i in range(len(arr)): if not s or arr[s[-1]] < arr[i]: s.append(i) else: ls.append(arr[i]) ls.sort() while ls: while s and arr[s[-1]] > ls[-1]: s.pop() x = ls.pop() if not s: res.append((0, x)) else: res.append((s[-1] + 1, x)) return res ------------------------------------------- 我亂寫的那兩個測資有過複雜度是O(nlogn) 可能有bug 對不起 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715004991.A.6C8.html ※ 編輯: Rushia (122.100.73.13 臺灣), 05/06/2024 22:17:19

推

wu10200512

05/06 22:17, 1年前 , 1^F

05/06 22:17, 1^F

推

sustainer123

05/06 22:18, 1年前 , 2^F

05/06 22:18, 2^F

推

JerryChungYC

05/06 22:18, 1年前 , 3^F

05/06 22:18, 3^F