写在前面的话:
看了看自己的博客,从一月底开始就没怎么更新过,我也确实将近5个月没怎么写代码了。今天突然觉得有些心慌,感觉手都已经生疏了。果然,随便找了道题就卡住了。隐约感觉要用map但又不太记得用法了,知道可以用DFS或BFS却又理不清思路。费了两个小时,结果写了一个shit一样的代码才通过。唉好忧伤啊。
Clone an undirected graph. Each node in the graph contains a label
and a list of its neighbors
.
OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use#
as a separator for each node, and ,
as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}
.
The graph has a total of three nodes, and therefore contains three parts as separated by #
.
- First node is labeled as
0
. Connect node0
to both nodes1
and2
. - Second node is labeled as
1
. Connect node1
to node2
. - Third node is labeled as
2
. Connect node2
to node2
(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / / 0 --- 2 / \_/
我的解法:
反应了好久,才发现题目的难点是防止结点的重复建立。我的方法没有用map,很繁琐。
#include<iostream> #include<vector> #include<algorithm> #include<stdlib.h> using namespace std; struct UndirectedGraphNode { int label; vector<UndirectedGraphNode *> neighbors; UndirectedGraphNode(int x) : label(x) {}; }; class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { //获取所有独立的结点 vector<UndirectedGraphNode *> UniqueNodes; getUniqueNodes(node, UniqueNodes); return findNode(node, UniqueNodes); } //查找指定结点并返回 UndirectedGraphNode * findNode(UndirectedGraphNode * node, vector<UndirectedGraphNode *> UniqueNodes) { if(NULL == node) return NULL; for(int i = 0; i < UniqueNodes.size(); i++) { if(node->label == UniqueNodes[i]->label) { return UniqueNodes[i]; } } return NULL; } //获取图中所有的结点和连接信息 void getUniqueNodes(UndirectedGraphNode *node, vector<UndirectedGraphNode *>& UniqueNodes) { //结点空或已存在时直接返回 if(NULL == node || NULL != findNode(node, UniqueNodes)) return; //存储新出现的结点 UndirectedGraphNode * newNode = new UndirectedGraphNode(node->label); UniqueNodes.push_back(newNode); for(int i = 0; i < node->neighbors.size(); i++) { getUniqueNodes(node->neighbors[i], UniqueNodes); newNode->neighbors.push_back(findNode(node->neighbors[i], UniqueNodes)); } } }; int main() { Solution s; UndirectedGraphNode * node0 = new UndirectedGraphNode(0); UndirectedGraphNode * node1 = new UndirectedGraphNode(1); UndirectedGraphNode * node2 = new UndirectedGraphNode(2); node0->neighbors.push_back(node1); node0->neighbors.push_back(node2); node1->neighbors.push_back(node2); node2->neighbors.push_back(node2); UndirectedGraphNode * newNode = s.cloneGraph(node0); return 0; }
网上大神解法
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { private: unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> hash; public: //BFS UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(!node) return NULL; queue<UndirectedGraphNode*> Qu; Qu.push(node); hash[node] = new UndirectedGraphNode(node->label); while(!Qu.empty()){ UndirectedGraphNode * tmp = Qu.front(); Qu.pop(); for(UndirectedGraphNode * neighbor : tmp->neighbors){ if(hash.find(neighbor) == hash.end()){ hash[neighbor] = new UndirectedGraphNode(neighbor->label); Qu.push(neighbor); } hash[tmp]->neighbors.push_back(hash[neighbor]); } } return hash[node]; } //DFS UndirectedGraphNode *cloneGraph1(UndirectedGraphNode *node) { if(!node) return NULL; if(hash.find(node) == hash.end()){ hash[node] = new UndirectedGraphNode(node->label); for(UndirectedGraphNode* neighbor : node->neighbors){ hash[node]->neighbors.push_back(cloneGraph1(neighbor)); } } return hash[node]; } };