讨论/技术交流/求助|第133题目疑似运行bug,队列长度为0后莫名又进队一个元素/
求助|第133题目疑似运行bug,队列长度为0后莫名又进队一个元素

代码如下:
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/

class Solution {
public:
Node* cloneGraph(Node* node) {
if(node == nullptr)
return nullptr;

    Node* ans = new Node(node->val);
    ans->neighbors.reserve(node->neighbors.size());

    queue<Node*> origin;    origin.push(node);
    queue<Node*> cloned;    cloned.push(ans);
    
    Node* tempOrigin = node;
    Node* tempCloned = node;
    Node* tempClonedNext = node;

    unordered_set<Node*> usedOriginNodes;
    usedOriginNodes.insert(node);
    unordered_map<int,Node*> usedClonedNodes;
    usedClonedNodes[node->val] = ans;

    while(origin.size() != 0){//循环开始
        cout << "new layer" << endl;
        cout << "origin size in start: " << origin.size() << endl;
        cout << "cloned size in start: " << cloned.size() << endl;
        int n = origin.size();
        unordered_set<Node*> sameLayerOrigin;
        unordered_map<int,Node*> sameLayerCloned;
        while(!origin.empty()){
            sameLayerOrigin.insert(origin.front());
            cout << "pop queue: " << origin.front()->val << endl;
            origin.pop();//出队列
            sameLayerCloned[cloned.front()->val] = cloned.front();
            cloned.pop();//出队列
        }
        for(int k = 0;k < n;k++){
            tempOrigin = *sameLayerOrigin.begin();
            tempCloned = sameLayerCloned[tempOrigin->val];
            for(int i = 0;i < tempOrigin->neighbors.size();i++){
                int thisVal = tempOrigin->neighbors[i]->val;
                if(sameLayerOrigin.count(tempOrigin->neighbors[i])){
                    tempClonedNext = sameLayerCloned[thisVal];
                    tempClonedNext->neighbors.push_back(tempCloned);
                    tempCloned->neighbors.push_back(tempClonedNext);
                }
                else if(!usedOriginNodes.count(tempOrigin->neighbors[i])){
                    if(!usedClonedNodes.count(thisVal)){
                        tempClonedNext = new Node(thisVal);
                        tempClonedNext->neighbors.reserve(tempOrigin->neighbors.size());
                        usedClonedNodes[thisVal] = tempClonedNext;
                        cout << "in queue " << thisVal << endl;
                        if(thisVal == 1)
                            cout << "in queue!!!! 1" << endl;
                        origin.push(tempOrigin->neighbors[i]);//入队列
                        cloned.push(tempClonedNext);//入队列
                    }
                    else
                        tempClonedNext = usedClonedNodes[thisVal];
                    tempCloned->neighbors.push_back(tempClonedNext);
                    tempClonedNext->neighbors.push_back(tempCloned);
                }
            }
            tempOrigin++;
        }
        for(auto it : sameLayerOrigin)
            usedOriginNodes.insert(it);
        cout << "queue size : " << origin.size() << endl;//循环最后输出队列长度
        cout << "cloned size : " << cloned.size() << endl;//循环最后输出队列长度
    }
    return ans;
}

};
这段代码本身有问题不能运行出正确的结果,本人已换用递归的方式ac,但是这段代码在调试的时候发生了奇怪的bug,测试数据为[[2,4],[1,3],[2,4],[1,3]],即初始事例,stdout输出如下:

new layer
origin size in start: 1
cloned size in start: 1
pop queue: 1
in queue 2
in queue 4
queue size : 2
cloned size : 2

new layer
origin size in start: 2
cloned size in start: 2
pop queue: 2
pop queue: 4
in queue 3
queue size : 1
cloned size : 1

new layer
origin size in start: 1
cloned size in start: 1
pop queue: 3
queue size : 0
cloned size : 0

new layer
origin size in start: 1
cloned size in start: 1
pop queue: 1
queue size : 0
cloned size : 0

简单来说基本想法是利用层序遍历,每一次循环先清空队列,然后判断这一层节点的子节点是否进入队列,队列长度为0结束循环。然而现在问题是在第三轮循环末尾队列长度已经是0了,还是进行了一次循环,然后才正常结束,进队列只在一个地方进行,不知道队列长度是怎么突然增加1的。

共 1 个回复

可能是运行时出了什么未知的操作,我这边测试了一下运行结果没有你给出的第四轮结果:

new layer
origin size in start: 1
cloned size in start: 1
pop queue: 1
in queue 2
in queue 4
queue size : 2
cloned size : 2
new layer
origin size in start: 2
cloned size in start: 2
pop queue: 2
pop queue: 4
in queue 3
queue size : 1
cloned size : 1
new layer
origin size in start: 1
cloned size in start: 1
pop queue: 3
queue size : 0
cloned size : 0

可以看到为0之后就没有继续执行了