Clone Graph @ LeetCode (Python)
kitt
posted @ 2014年3月15日 16:36
in LeetCode
, 2777 阅读
BFS和DFS应该都可以, 我用了BFS。根据一楼评论, 用了一个dictionary来记录所有新生成的node, 并且测试数据中有...#3,4,4#...的情况, 所以只要node一入队，就认为是visited. 而不是node出队时才认为是visited (这种情况下node 4会被访问两次)。
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if node == None: return None
newNodes = {node.label : UndirectedGraphNode(node.label)}
q = collections.deque(); q.append(node)
newQ = collections.deque(); newQ.append(newNodes[node.label])
visited = set([node]) # A node will be visited as long as it's enqueued
while q:
currNode = q.popleft(); newCurrNode = newQ.popleft()
for n in currNode.neighbors:
if n.label not in newNodes:
newNodes[n.label] = UndirectedGraphNode(n.label)
newCurrNode.neighbors.append(newNodes[n.label])
if n not in visited:
q.append(n); newQ.append(newNodes[n.label])
visited.add(n) # A node will be visited as long as it's enqueued
return newNodes[node.label]
2014年3月31日 17:18
请问queue里面会有重复的节点出现吗？感觉复制邻居的时候都是创建新节点，没有使用之前创建的新节点。
举例子：这里有123三个节点
1,2,3 #2,3#3
访问1的时候会把2，3入队；队列2,3
访问2：队列3,3 <------队列中有重复节点，而且都会再访问一次。
访问3：队列3
2014年4月01日 14:19
@有问题: 已更新，多谢提醒～
2014年4月01日 14:23
@有问题: 速度确实快了, 原来要640ms, 现在440ms
2019年9月11日 06:42
To get heard? SpringMAids Steam Cleaning restores together with cleans stonework! Any specially experienced team will pull yrs of dirt and grime and engine oil from porous travertine, record, granite, Saltillo together with other stone tiles. Smart Impression Steam Maintenance offers personal assessments together with cleanings using an unmatched personal awareness of detail. Any stonework squad will re-establish any piece of rock surface that will its all natural, polished status.
2021年9月01日 04:00
Various say of the fact that cleaning home business is immune : to recession this kind of is true in some degree and in the most market sectors that include office housecleaning. While a lot of consumers on the residential markets may limit cleaning big butter jesus started downturn, a large part of the clientele really are affluent and that can afford to with most of the service big butter jesus started recession. Cleaning may be amongst the least altered industries at the time of an downturn in the economy anyway.
2023年8月15日 03:17
Before you decide to risk poisoning your head with trash from those who have no experience owning a paint company, and will let you know all their applying for grants this topic, take a while to decelerate and perform little investigation. Only absorb the info from somebody who has succeeded for a lot more than ten many years. Why decade you request; because nearly all paint companies fail within the first decade.