开发平台(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);
}
所以确定数值是一样的
感谢各位！
作者:
LPH66 (-6.2598534e+18f)
2025-03-20 04:36:00楼上上正解, 你加入 notfound 的东西是 ans->val*加入tfound // 但是你传入下层的 ans 值是烂掉的烂掉的原因是上一层取用了没有初始化的 idx 求取的关系也就是你所加入的值已经不是你在上一层找的 n->val 了照水晶球显示你的 and->neighbors[idx] 想求得的应该是刚 push_back 进去的 tn, 那你就直接传这个值进去就好