作者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/cn.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