Gas Station @ LeetCode (Python)
Distinct Subsequences @ LeetCode (Python)

Clone Graph @ LeetCode (Python)

kitt posted @ 2014年3月15日 16:36 in LeetCode , 2660 阅读

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]
Avatar_small
有问题 说:
2014年3月31日 17:18

请问queue里面会有重复的节点出现吗?感觉复制邻居的时候都是创建新节点,没有使用之前创建的新节点。
举例子:这里有123三个节点
1,2,3 #2,3#3
访问1的时候会把2,3入队;队列2,3
访问2:队列3,3 <------队列中有重复节点,而且都会再访问一次。
访问3:队列3

Avatar_small
kitt 说:
2014年4月01日 14:19

@有问题: 已更新,多谢提醒~

Avatar_small
kitt 说:
2014年4月01日 14:23

@有问题: 速度确实快了, 原来要640ms, 现在440ms

Avatar_small
babysitting services 说:
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.

Avatar_small
maids in dubai 说:
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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter