狗家新鮮VO

只有一場VO補面之前取消的
encode/decode graph with integer list, 是我從來都沒有看過, graph本身是directed, 有可能存在環,
原本以為是297. Serialize and Deserialize Binary

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

    1
b.  0  0    0
c.  0  0   0
data 2  5   9
return [0 1 1 0 0 0 0 0 0 2 5 9]

是我的問題，還是這題真的是特別難?

adjacency matrix根本不需要。只需要dfs找到 node的个数，每个node的value，还有边的关系，然后放进一个list里， list[0]是node的个数，list[1]-list[n+1]是每个node的data，后面全记录边。

liye198995 发表于 2021-11-26 03:52
lintcode encode and decode graph.

没找到诶。。

采用了zec的解法，下面是code，如有误，请求指正。 求加米，谢谢！

1. from collections import deque
   
2. class Node:
   
3.         def __init__(self, data=None, neighbors=list([])):
   
4.                 self.data=data
   
5.                 self.neighbors=neighbors
   
6. 
   
7.         def equal(self, other, visited=set([])):
   
8.                 if self in visited:
   
9.                         return True
   
10.                 res = True
    
11.                 visited.add(self)
    
12.                 if self.data == other.data and len(self.neighbors) == len(other.neighbors):
    
13.                         for i in range(len(self.neighbors)):
    
14.                                 res = res and (self.neighbors[i].equal(other.neighbors[i], visited))
    
15.                 else:
    
16.                         return False
    
17.                 return res
    
18. 
    
19. 
    
20. def encode(root):
    
21.         idx_d = {0: root}
    
22.         node_d = {root: 0}
    
23.         idx = 1
    
24.         edges = []
    
25.         q = deque([root])
    
26.         first_visited = set([root])
    
27.         second_visited = set([])
    
28.         while q:
    
29.                 node = q.popleft()
    
30.                 if node not in second_visited:
    
31.                         second_visited.add(node)                       
    
32.                 else:
    
33.                         continue
    
34.                 for nei in node.neighbors:
    
35.                         if nei not in first_visited:
    
36.                                 idx_d[idx] = nei
    
37.                                 node_d[nei] = idx
    
38.                                 idx += 1
    
39.                                 first_visited.add(nei)
    
40.                         edges.append((node_d[node], node_d[nei]))
    
41.                         q.append(nei)
    
42. 
    
43.         n = len(idx_d)
    
44.         nodes = [idx_d[i].data for i in range(n)]
    
45.         return [n] + nodes + edges
    
46. 
    
47. def decode(encoded):
    
48.         n = encoded[0]
    
49.         node_data = encoded[1:1+n]
    
50.         edges  = encoded[n+1:]
    
51.         idx_d = {i: Node(node_data[i], []) for i in range(n)}
    
52.         for left, right in edges:
    
53.                 idx_d[left].neighbors.append(idx_d[right])
    
54.         return idx_d[0]
    
55. 
    
56. 
    
57. def edges_to_matrix(n, edges):
    
58.         matrix = [[0] * n for _ in range(n)]
    
59.         for left, right in edges:
    
60.                 matrix[left][right] = 1
    
61.         return matrix
    
62. 
    
63. 
    
64. if __name__ == '__main__':
    
65.         root = Node(3)
    
66.         left = Node(4)
    
67.         right = Node(5)
    
68.         root.neighbors = [left, right]
    
69.         left.neighbors = [right]
    
70.         right.neighbors = [root]
    
71.         encoded = encode(root)
    
72.         print(edges_to_matrix(3, encoded[4:]))
    
73.         root2 = decode(encoded)
    
74.         encoded_2 = encode(root2)
    
75.         assert encoded_2 == encoded
    
76. 
    
77. 
    
78.         fake_root = Node(3)
    
79.         left = Node(4)
    
80.         right = Node(5)
    
81.         root.neighbors = [left, right]
    
82.        
    
83.         assert root.equal(fake_root) == False
    
84.         assert root.equal(root2)
    
85. 
    
86.         idx_d = {}
    
87.         for i in range(10):
    
88.                 idx_d[i] = Node(i, [])
    
89.         for i in range(10):
    
90.                 for j in range(10):
    
91.                         if i != j:
    
92.                                 idx_d[i].neighbors.append(idx_d[j])
    
93.         encoded_3 = encode(idx_d[0])
    
94.         print(edges_to_matrix(10, encoded_3[11:]))
    

复制代码

直觉告诉我拓扑排序，但我不确定哦

匿名者 发表于 2021-11-25 10:50
直觉告诉我拓扑排序，但我不确定哦

拓扑排序怎么做？求指教

做过则简单，没做过则难

楼主思路很好啊 我觉得这应该就是最优解了…

91codege 发表于 2021-11-25 10:16
拓扑排序怎么做？求指教

有环也一样要encode和decode，拓扑排序没意义吧。如果图只有几十个node的话，直接把每个node的邻接表弄成bitmask（类似状态压缩DP）就可以了，如果是十几万个node的话那有点难。

lintcode encode and decode graph.