作者handofn0xus (你真是糟糕的小焰)
看板C_and_CPP
標題[問題] find vector內元素 卻完全沒作用
時間Mon Mar 17 23:57:35 2025
開發平台(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);
}
所以確定數值是一樣的
感謝各位！
--
作者 finzaghi (琴之森) 看板 C_Chat
標題 [閒聊] 果青 立體歐派抱枕
時間 Fri Apr 14 17:19:51 2017
1F：推 sthho: 想看二小姐立體抱枕04/14 17:20
2F：推 hachiman: 那不就是一般抱枕04/14 17:21
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.232.193 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1742227061.A.964.html
※ 編輯: handofn0xus (106.1.232.193 臺灣), 03/18/2025 00:47:07
3F：推 LPH66: 你的遞迴呼叫使用了 idx 變數，但你沒給值 03/18 00:59
4F：→ LPH66: 水晶球猜測這是 for(Node *n) 這個迴圈改寫過的遺跡 03/18 01:03
喔幹 對欸 完全沒注意到
但是即使如此 他看到同樣的數值 find那邊應該就會擋下來不再進下一層遞迴了？
但實際上他還是繼續走下去
5F：推 lycantrope: 不是要not find 才遞回? 03/18 11:23
6F：推 harryooooooo: 因為idx沒被改 n->val 找到沒出現過的值之後你還是 03/18 15:30
7F：→ harryooooooo: 會重複遞迴進去同一個 neighbor[idx] 03/18 15:30
8F：→ simon1203: 你這個到底是在寫c還是c++= = 03/19 07:16
9F：推 LPH66: 樓上上正解, 你加入 notfound 的東西是 ans->val 03/20 04:36
10F：→ LPH66: *加入tfound // 但是你傳入下層的 ans 值是爛掉的 03/20 04:37
11F：→ LPH66: 爛掉的原因是上一層取用了沒有初始化的 idx 求取的關係 03/20 04:38
12F：→ LPH66: 也就是你所加入的值已經不是你在上一層找的 n->val 了 03/20 04:38
13F：→ LPH66: 照水晶球顯示你的 and->neighbors[idx] 想求得的應該是 03/20 04:40
14F：→ LPH66: 剛 push_back 進去的 tn, 那你就直接傳這個值進去就好 03/20 04:41
了解 感謝各位 耍笨了！
※ 編輯: handofn0xus (220.130.45.59 臺灣), 04/02/2025 14:55:43
※ 編輯: handofn0xus (220.130.45.59 臺灣), 04/02/2025 15:12:24