苏淳这个倒霉蛋！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

苏淳这个倒霉蛋！

苏淳这个倒霉蛋！# Stock

h*g2010-01-10 08:01

1 楼

刚做了下 Graph Clone, Output Limit Exceeded. 查了半天也没看出来哪里有问题，
附上代码，请大牛门挑挑毛病，谢拉！
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if (!node) return NULL;
UndirectedGraphNode * nodecopy;
queue que;
unordered_map map;
nodecopy=new UndirectedGraphNode(node->label);

que.push(node);
map[node]=nodecopy;
while(!que.empty()){
UndirectedGraphNode* current=que.front();
que.pop();
int nsz=current->neighbors.size();
for(int i=0;iUndirectedGraphNode* neighbor=new UndirectedGraphNode(
current->neighbors[i]->label);
if(map.find(current->neighbors[i])==map.end()){
map[current]->neighbors.push_back(neighbor);
map[current->neighbors[i]]=neighbor;
que.push(current->neighbors[i]);

}
else{
map[current]->neighbors.push_back(neighbor);
}
}
}
return nodecopy;

}

b*y2010-01-10 08:01

2 楼

【以下文字转载自 Military 讨论区】
发信人: edn (我叫nde), 信区: Military
标题: 【转载】这就是体制限制经济发展的例子。跟200年前不许卖私盐一
发信站: BBS 未名空间站 (Sun Jan 10 13:00:00 2010, 美东)
政府经营的企业正试图与民营企业争抢生意，它们手中拥有一个无人能比拟的武器——
制定游戏规则。去年10月1日实施的新《邮政法》，明确规定禁止民营企业涉足的邮政
局专营范围，因为民营快递公司威胁到了邮政局的利润；现在网上书店的繁荣也让新华
书店等传统国营图书销售商寝食难安，于是所谓的《图书公平交易规则》出台了。新的
《规则》可笑的规定：不得低价倾销新书，不得进行任何形式的低价（低于图书正常出
版成本价）竞争和竞标。对出版一年内的新书（以版权页出版时间为准），进入零售市
场时，须按图书标定实价销售，网上书店或会员制销售时，最多享受不低于8.5折的优
惠幅度。新规则的制定者是：中国出版工作者协会、中国书刊发行业协会、新华书店协会
今年10月1日正式实施的新《邮政法》，明确规定禁止民营企业涉足的邮政局专营范围
，一些人

l*n2010-01-10 08:01

3 楼

呃，感觉思路超混乱啊。话说先遍历一遍建好新节点，再遍历一遍建立邻接关系，不是
很直观的吗？试图把二者搞在一起总觉得十分绕，难写更难懂。

P*r2010-01-10 08:01

4 楼

用DFS 和HashMap, 但是Time Limit Exceeded. 有什么改进的方法吗？
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(node == null)
return null;
Map hMap = new HashMap<
UndirectedGraphNode,UndirectedGraphNode>();
UndirectedGraphNode root = new UndirectedGraphNode(node.label);
hMap.put(node,root);
for(UndirectedGraphNode child : node.neighbors){
if(!hMap.containsKey(child)){
UndirectedGraphNode newNode = cloneGraph(child);
hMap.put(child,newNode);
root.neighbors.add(newNode);
}else{
root.neighbors.add(hMap.get(child));
}
}
return root;
}

l*n2010-01-10 08:01

5 楼

这种情况的TLE肯定是死循环了。话说，已经要dfs的时候为什么不用递归呢？
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if (node == null) return null;
return dfs(node, new HashMapUndirectedGraphNode>());
}

UndirectedGraphNode dfs(UndirectedGraphNode node,
Map map) {
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node, copy);
for (UndirectedGraphNode n:node.neighbors) {
if (!map.containsKey(n)) {
copy.neighbors.add(dfs(n, map));
} else {
copy.neighbors.add(map.get(n));
}
}

return copy;
}
}

reused

【在 P*******r 的大作中提到】

: 用DFS 和HashMap, 但是Time Limit Exceeded. 有什么改进的方法吗？
: public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: if(node == null)
: return null;
: Map hMap = new HashMap<
: UndirectedGraphNode,UndirectedGraphNode>();
: UndirectedGraphNode root = new UndirectedGraphNode(node.label);
: hMap.put(node,root);

P*r2010-01-10 08:01

6 楼

用错递归了，还以为是没有优化。
多谢！

reused

【在 l*n 的大作中提到】

: 这种情况的TLE肯定是死循环了。话说，已经要dfs的时候为什么不用递归呢？
: public class Solution {
: public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: if (node == null) return null;
: return dfs(node, new HashMap: UndirectedGraphNode>());
: }
:

c*p2010-01-10 08:01

7 楼

这个题以前首页有discussion呀

c*p2010-01-10 08:01

8 楼

求java版的！

D*d2010-01-10 08:01

9 楼

我提交的程序，在本地编译运行没有问题，但是 OJ 老出错。
我的思路是遍历三次：
1. 第一次建立节点 new_node
new_node->val = old_node->val;
old_node->val = -1; // a visited label
old_node->neighbor.push_back(new_node);
2. 第二次 copy old_node->neighbor[k]->neighbor.back()
到 new_node->neighor[k] except last one.
3. 第三次 restore old_node: old_node->val = old_node->neighbor.back()->val;
old_node->neighbor.pop_back();

h*g2010-01-10 08:01

10 楼

对这里是用了map来同时做这两件事。先遍历一遍建好新节点存在哪里呢？一个数组中
？然后再链接邻接关系么？如果有代码可以学习一下就更好了

【在 l*n 的大作中提到】

: 呃，感觉思路超混乱啊。话说先遍历一遍建好新节点，再遍历一遍建立邻接关系，不是
: 很直观的吗？试图把二者搞在一起总觉得十分绕，难写更难懂。

l*o2010-01-10 08:01

11 楼

DFS 和 BSF 的都写了，已过OJ
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<
UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if (node == null) return null;
HashMap created = new HashMapUndirectedGraphNode>();
dfs(node, new HashSet(), created);
return created.get(node.label);
}

private void dfs(UndirectedGraphNode node, HashSet visited,
HashMap created) {
if (node == null) return;
if (visited.contains(node.label)) return;
visited.add(node.label);
UndirectedGraphNode tmpCloneNode;
if (!created.containsKey(node.label)) {
tmpCloneNode = new UndirectedGraphNode(node.label);
created.put(node.label, tmpCloneNode);
} else {
tmpCloneNode = created.get(node.label);
}
for (UndirectedGraphNode e : node.neighbors) {
UndirectedGraphNode newNode;
if (!created.containsKey(e.label)) {
newNode = new UndirectedGraphNode(e.label);
created.put(e.label, newNode);
} else {
newNode = created.get(e.label);
}
tmpCloneNode.neighbors.add(newNode);
dfs(e, visited, created);
}
}
}

/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<
UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if (node == null) return null;
HashMap created = new HashMapUndirectedGraphNode>();
HashSet visited = new HashSet();
Queue queue = new LinkedList<
UndirectedGraphNode>();
queue.offer(node);
int open = 1;
while (!queue.isEmpty()) {
UndirectedGraphNode tmpNode = queue.poll();
int closed = open; open = 0;
while (closed >= 0) {
if (!visited.contains(tmpNode.label)) {
UndirectedGraphNode tmpCloneNode;
if (!created.containsKey(tmpNode.label)) {
tmpCloneNode = new UndirectedGraphNode(tmpNode.label
);
created.put(tmpNode.label, tmpCloneNode);
} else {
tmpCloneNode = created.get(tmpNode.label);
}
for (UndirectedGraphNode e : tmpNode.neighbors) {
queue.add(e);
UndirectedGraphNode newNode;
if (!created.containsKey(e.label)) {
newNode = new UndirectedGraphNode(e.label);
created.put(e.label, newNode);
} else {
newNode = created.get(e.label);
}
tmpCloneNode.neighbors.add(newNode);
open++;
}
visited.add(tmpNode.label);
}
closed--;
}
}
return created.get(node.label);
}
}

l*n2010-01-10 08:01

12 楼

呃，我说的遍历两遍是在bfs里面。
dfs涉及到需要标记visited的时候，写代码比bfs要做更多的逻辑考虑，更容易出错。
我比较懒，所以在复杂度没有本质差别的时候喜欢用分块的步骤。

【在 h****g 的大作中提到】

: 对这里是用了map来同时做这两件事。先遍历一遍建好新节点存在哪里呢？一个数组中
: ？然后再链接邻接关系么？如果有代码可以学习一下就更好了

l*n2010-01-10 08:01

13 楼

你这个dfs不够彻底啊。真dfs的话，调用它的函数基本只做最少的事情。

【在 l****o 的大作中提到】

: DFS 和 BSF 的都写了，已过OJ
: /**
: * Definition for undirected graph.
: * class UndirectedGraphNode {
: * int label;
: * ArrayList neighbors;
: * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<
: UndirectedGraphNode>(); }
: * };
: */

l*o2010-01-10 08:01

14 楼

.那我可以怎么改进？

【在 l*n 的大作中提到】

: 你这个dfs不够彻底啊。真dfs的话，调用它的函数基本只做最少的事情。

z*82010-01-10 08:01

15 楼

没办法，大家刷题把门槛都搞的很高，两次遍历的人offer就被一次遍历的人给抢了
。。。

【在 l*n 的大作中提到】

t*n2010-01-10 08:01

16 楼

贴一个我的BFS版本, 通过OJ了.
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(!node) return NULL;
unordered_map valMap;

queue Q1;
queue Q2;
Q1.push(node);

UndirectedGraphNode *p_dup = new UndirectedGraphNode(node->label);
UndirectedGraphNode *root = p_dup;
Q2.push(p_dup);
valMap[p_dup->label] = p_dup;

UndirectedGraphNode *p_tmp = NULL;
unordered_set isVisited;
isVisited.insert(node);

UndirectedGraphNode *p_cur = NULL;
UndirectedGraphNode *p_old = NULL;
while(!Q1.empty()) {
p_tmp = Q1.front();
p_dup = Q2.front();

for(int i=0; ineighbors.size(); ++i) {
if(isVisited.find(p_tmp->neighbors[i])!=isVisited.end()) { /
/dups
p_old = valMap[p_tmp->neighbors[i]->label];
p_dup->neighbors.push_back(p_old);
} else {
Q1.push(p_tmp->neighbors[i]);
isVisited.insert(p_tmp->neighbors[i]);

p_cur = new UndirectedGraphNode(p_tmp->neighbors[i]->
label);
p_dup->neighbors.push_back(p_cur);
Q2.push(p_cur);
valMap[p_cur->label] = p_cur;
}
}
Q1.pop();
Q2.pop();
}
return root;
}
};

a*e2010-01-10 08:01

17 楼

我改了一下你的代码，看一下注释
class Solution{
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (!node) return NULL;
UndirectedGraphNode * nodecopy;
queue que;
unordered_map map;
nodecopy=new UndirectedGraphNode(node->label);

que.push(node);
map[node]=nodecopy;
while(!que.empty()){
UndirectedGraphNode* current=que.front();
que.pop();
for(int i=0;ineighbors.size();i++){
if(map.find(current->neighbors[i])==map.end()){
UndirectedGraphNode* neighbor=new UndirectedGraphNode(
current->neighbors[i]->label); //new 新节点应该放在这里
map[current->neighbors[i]]=neighbor; //这句应该提前，
建立新旧节点之间的关系
map[current]->neighbors.push_back(neighbor);
que.push(current->neighbors[i]);

}
else{
map[current]->neighbors.push_back(map[current->
neighbors[i]]); //这句也要改一下
}
}
}
return nodecopy;
}
};

reused

【在 h****g 的大作中提到】

: 刚做了下 Graph Clone, Output Limit Exceeded. 查了半天也没看出来哪里有问题，
: 附上代码，请大牛门挑挑毛病，谢拉！
: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: if (!node) return NULL;
: UndirectedGraphNode * nodecopy;
: queue que;
: unordered_map map;
: nodecopy=new UndirectedGraphNode(node->label);

a*e2010-01-10 08:01

18 楼

弱问TLE啥意思？

reused

【在 l*n 的大作中提到】

s*u2010-01-10 08:01

19 楼

话说，这个题用bfs比dfs有什么优势么？感觉不是最短路径之类问题的话，差不多吧？
dfs思路清晰，代码精简。其实就是D&C，假定subgraph已经建立好，那么如何求解
graph
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node,unordered_map<
UndirectedGraphNode *,UndirectedGraphNode *>& nodeMap ){

if(!node) return NULL;

if(nodeMap.count(node) > 0)
return nodeMap[node];

UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);

nodeMap[node] = newNode;

vector newNeighbors;

for(auto it = (node->neighbors).begin(); it != (node->neighbors).end
(); ++it){
(newNode->neighbors).push_back( cloneGraph(*it,nodeMap) );
}

return newNode;
}