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)
                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

1,2,3 #2,3#3
访问2:队列3,3 <------队列中有重复节点,而且都会再访问一次。

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

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

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

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

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.

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