開發平台(Platform): Win11
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
Leetcode C++
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
non
問題(Question)：
目前在寫Leetcode 的 133. Clone Graph
https://leetcode.com/problems/clone-graph/description/
(Node的結構是
int val;
vector<Node*> neighbors;)
我是用DFS方法跑每個點
用vector<int>記錄跑過點的數值(因為數值是唯一的不會重複)
但是 當我用find去看我有沒有記錄到這個數值
卻會發生明明有記錄到 iterator卻還是跑到vector.end() 造成不斷重複而TLE
用printf去印就發現一堆重複的數字被放入vector<int>
我知道可以用set 但是這個詭異的情況我想搞清楚到底是出了甚麼錯
錯誤結果(Wrong Output)：
https://i.imgur.com/Vakk1Co.png
下面就是無線增長直到爆掉
程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
void dfs(Node *ans, Node *ori, vector<int> *tfound)
{
int idx,temp;
printf("%d\n",ans->val);
tfound->push_back(ans->val);
for(int a : *tfound)
{
printf("found %d ", a);
}
printf("\n");
for(Node *n : ori->neighbors)
{
if(find(tfound->begin(), tfound->end(), n->val) == tfound->end())
{
Node *tn = new Node(n->val);
ans->neighbors.push_back(tn);
tn->neighbors.push_back(ans);
dfs(ans->neighbors[idx], ori->neighbors[idx], tfound);
}
}
return;
}
補充說明(Supplement)：
ans跟ori兩個指標在主函式裡我是放入原題目給的指標
以及我複製他的val來建的新指標
Node* cloneGraph(Node* node) {
Node *ans;
vector<int> tfound;
if(!node) return nullptr;
ans = new Node(node->val);
dfs(ans, node, &tfound);
}
所以確定數值是一樣的
感謝各位！

你的遞迴呼叫使用了 idx 變數，但你沒給值水晶球猜測這是 for(Node *n) 這個迴圈改寫過的遺跡

想看二小姐立體抱枕

那不就是一般抱枕

不是要not find 才遞回?

因為idx沒被改 n->val 找到沒出現過的值之後你還是會重複遞迴進去同一個 neighbor[idx]

你這個到底是在寫c還是c++= =

樓上上正解, 你加入 notfound 的東西是 ans->val*加入tfound // 但是你傳入下層的 ans 值是爛掉的爛掉的原因是上一層取用了沒有初始化的 idx 求取的關係也就是你所加入的值已經不是你在上一層找的 n->val 了照水晶球顯示你的 and->neighbors[idx] 想求得的應該是剛 push_back 進去的 tn, 那你就直接傳這個值進去就好