Re: [閒聊] 每日LeetCode
看板Marginalman作者Neuenmuller (蘇菲・諾伊恩謬拉)時間2年前 (2023/11/11 07:40)推噓0(0推 0噓 0→)留言0則, 0人參與討論串505/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 在陣列裡面相鄰，求出原本的陣列長什麼樣子
: ，如果有多種結果返回任意一種即可。
: 思路：
: 1.陣列的數字相鄰關係我們可以把他看成一個邊，這個問題就變成一個圖形問題，我們先
: 把所有的邊轉換成一個無向圖，因為數字不連續所以要用 Map 保存。
: 2.陣列的第一個元素或最後一個元素只可能和一個數字相鄰，我們要從其中一個位置做
: 遍歷才可以走訪到所有元素找到原本的陣列，我這邊是用一個二維陣列記錄相連邊，
: 如果第二個索引位置為 null 就表示這個點只有一個相鄰數字，他必定是起點或終點
: ，從這個點開始遍歷所有相鄰的未走訪點就可以找到原本的陣列。
: 3.遍歷的時候用一個 prev 記錄上一個點避免往回走，遍歷的過程不斷的把數字
: 填充進 res 裡即可。
我的作法八成像，只是我在避免回頭走的時候沒想太多
另外用一個unordered_set來存所有走過的數字，多花了一坨空間
嗚嗚
# CPP Solution
class Solution {
public:
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
vector<int> output;
unordered_map<int, vector<int>> adj;
unordered_set<int> visited;
for (auto p: adjacentPairs) {
adj[p[0]].push_back(p[1]);
adj[p[1]].push_back(p[0]);
}
int cur;
for (auto p: adj) {
if (p.second.size() == 1) {
cur = p.first;
output.push_back(cur);
visited.insert(cur);
cur = adj[cur][0];
break;
}
}
while (adj[cur].size() > 1) {
output.push_back(cur);
visited.insert(cur);
if (visited.find(adj[cur][0]) != visited.end()) {
cur = adj[cur][1];
}
else {
cur = adj[cur][0];
}
}
output.push_back(cur);
return output;
}
};
--
neuenmuller@atelier:home$ touch plachta
touch: cannot touch 'plachta': Permission denied
neuenmuller@atelier:home$ sudo touch plachta
[sudo] password for neuenmuller:
neuenmuller is not in the sudoers file. This incident will be reported.
neuenmuller@atelier:home$
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 97.99.29.95 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699659615.A.4E9.html
討論串 (同標題文章)