Re: [閒聊] 每日LeetCode

看板Marginalman作者ZooseWu (動物園公告)時間2年前 (2023/11/11 00:34)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串503/719 (看更多)

※ 引述《Rushia (みけねこ的鼻屎)》之銘言： : https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/description : 1743. Restore the Array From Adjacent Pairs : 有一堆整數儲存在一個陣列包含了 n 個不相同元素，你忘記陣列長什麼樣子了但是 : 你記得所有數字的旁邊有哪些數字，給你一個二維陣列adjacentPairs ，adjacentPairs : [i] = [ui, vi] 表示兩個數字 ui 和 vi 在陣列裡面相鄰，求出原本的陣列長什麼樣子 : ，如果有多種結果返回任意一種即可。基本思路差不多 Intuition 定義一個類似double link list結構的類別然後把每個邊雙方連起來從頭找到尾 Approach 我們知道每個元素相鄰的元素而且每個元素最多只會有兩個相鄰的元素頭尾則各只有一個所以我們定義下面這個類別 interface DoubleLinkList { value: number prevNode?: DoubleLinkList nextNode?: DoubleLinkList } 就可以把所有元素的相鄰狀況記錄下來但是單純紀錄完去找會遇到兩個問題： 1.我們只知道相鄰狀況，但是不知道頭尾 2.每個元素的next不一定是下一個，有可能會跑回來，例如下面的狀況： { value: 1, prevNode: undefined, nextNode: 2} { value: 2, prevNode: 3, nextNode: 1} 1找到2之後又找回1，然後就會陷入無限迴圈。對於上面的第一個問題的解法我們可以透過元素出現的次數去找頭尾如果只有出現一次的就是頭尾原本我用陣列去紀錄後來發現元素可能是負數所以改成用Map去紀錄至於第二個問題的解法我們一般會認為可以直接交換prev跟next去保持鏈結的正確性但是這樣太麻煩沒有必要我們的雙向鏈結用完一次就會丟掉所以我們採用第二個方法就是記錄他的前一個元素如果prev就是前一個元素我們就用next 反之我們就用prev 最後從頭到尾跑一次輸出答案完工 TS Code: interface DoubleLinkList { value: number prevNode?: DoubleLinkList nextNode?: DoubleLinkList } function restoreArray (adjacentPairs: number[][]): number[] { const count = new Map<number, number>() const map = new Map<number, DoubleLinkList>() const GetNode = (index: number): DoubleLinkList => { if (map.has(index)) return map.get(index) const node: DoubleLinkList = { value: index } map.set(index, node) return node } const ConnectTo = (node1: DoubleLinkList, node2: DoubleLinkList): void => { if (node1.prevNode === undefined) node1.prevNode = node2 else node1.nextNode = node2 } const connectNode = (node1: DoubleLinkList, node2: DoubleLinkList): void => { ConnectTo(node1, node2) ConnectTo(node2, node1) } const addCount = (index: number): void => { count.set(index, (count.get(index) ?? 0) + 1) } for (let i = 0; i < adjacentPairs.length; i++) { const index0 = adjacentPairs[i][0] const index1 = adjacentPairs[i][1] connectNode(GetNode(index0), GetNode(index1)) addCount(index0) addCount(index1) } let head: number = -1 for (const key of count.keys()) { if (count.get(key) === 1) { head = key break } } const answer: number[] = [] let lastNumber = 0.1 let node = map.get(head) const getNextNode = (node: DoubleLinkList, lastNumber): DoubleLinkList => { if (node.prevNode?.value === lastNumber) return node.nextNode return node.prevNode } while (node !== undefined) { answer.push(node.value) const tNumber = node.value node = getNextNode(node, lastNumber) lastNumber = tNumber } return answer } -- Zoosewu Yoututbe顯示PTT推文可以在各個網站追實況或Live時使用預覽圖: https://i.imgur.com/ZhtXdAJ.png