面试碰到的一个算法问题，懂的请指教

shayy

micfox001 发表于 2022-2-17 21:04
我不肯定你的nTemp是指参照节点的id还是邻居列表的id。

如果是参照节点的id，那就和找出有多少行输入一 ...

每行这么处理，只用一遍loop就完事了，不用知道最大值，每读入一行扩到最大可能值，把数一填就好了
一遍下来，行也记完了，数也填好了
不然的话，找出最大size就要loop一遍，然后要把数据重读一遍再往矩阵里填吗？感觉有点绕

peacefulme

这个题目不规范
第一行应该是N

Grange

不是n*n吗？有多少column就有多少row， 不对吗？

micfox001

Grange 发表于 2022-2-22 14:16
不是n*n吗？有多少column就有多少row， 不对吗？

是啊。 那是结果的矩阵。

输入的是每个节点的邻居列表。 那个列表的行数就是输出矩阵的N， 列数则不等，每个节点的邻居数不一样。

Grange

micfox001 发表于 2022-2-22 13:20
是啊。 那是结果的矩阵。

输入的是每个节点的邻居列表。 那个列表的行数就是输出矩阵的N， 列数则不等， ...

用最长的那行算n?

楼上已经说了，一直读到EOF，input的row count就是n。

不会Java，用python试了一下：

1. [root@ryzen ~]# cat vertices.py
   
2. #!/usr/bin/env python3
   
3. 
   
4. import sys
   
5. 
   
6. def main():
   
7. 
   
8.     filename = sys.argv[1]
   
9.     n = 0
   
10.     vertices = []
    
11.     with open(filename) as f:
    
12.         for r in f:
    
13.             l = r[:-1].split(' ')
    
14.             for i in l[1:]:
    
15.                 vertices.append((int(l[0]), int(i)))
    
16.             n += 1
    
17. 
    
18.     matrix = [[0] * n for i in range(n)]
    
19. 
    
20.     for r,c in vertices:
    
21.         matrix[r][c] = 1
    
22. 
    
23.     for r in matrix:
    
24.         print(r)
    
25. 
    
26. if __name__ == "__main__":
    
27.     main()
    

复制代码

1. [root@ryzen ~]# cat test1
   
2. 0 1 2 3 4
   
3. 1 0 3
   
4. 2 0 3 4
   
5. 3 0 1 2
   
6. 4 0 2
   
7. [root@ryzen ~]# ./vertices.py test1
   
8. [0, 1, 1, 1, 1]
   
9. [1, 0, 0, 1, 0]
   
10. [1, 0, 0, 1, 1]
    
11. [1, 1, 1, 0, 0]
    
12. [1, 0, 1, 0, 0]
    
13. [root@ryzen ~]# cat test2
    
14. 0 1 2
    
15. 1 0 2
    
16. 2 0 1
    
17. [root@ryzen ~]# ./vertices.py test2
    
18. [0, 1, 1]
    
19. [1, 0, 1]
    
20. [1, 1, 0]

复制代码

Grange

这个solution可以吗？

micfox001

Grange 发表于 2022-2-22 14:26
用最长的那行算n?

楼上已经说了，一直读到EOF，input的row count就是n。

最长的那行邻居列表不一定就是N。

因为ID为N-1的节点可以是一个孤点， 任何一个节点都与它没联系。那么N-1就不会出现在任何节点的邻居列表里。而且最长的邻居列表其数字不一定就是N。因为没规定总有一个节点是和其他任何节点都是邻居啊。

Grange

micfox001 发表于 2022-2-22 21:04
最长的那行邻居列表不一定就是N。

因为ID为N-1的节点可以是一个孤点， 任何一个节点都与它没联系。那么N ...

是的，我本来想把那句话划掉的。用row count就可以。我上边用python做出来了但不见得是最优。

hciyang

不是非得用数组吧？ 用List<List<Integer>>，发现新节点加上不就完了？ 反正怎么都是O(N^2)

churq

python

def f(line):
    tokens = line.split(" ")
    highest_bit = 1 if token[0] else 0
    row = [2**i for i in token[1:] if i]
    binary_format = format(sum(row), "b")
    result = binary_format [::-1]
    result[0] = higest_bit
    return result
max_len= 0
while true:
      line = input()
      if not line:
          break
      parsed_row = f(line)
      max_len = max([max_len, len(parsed_row)])
      matrix_str.append(parsed_row)

result_matrix = [ s.zfill(max_len, "0") for s in matrix_str]
result_matrix = [ list(i) for i in result_matrix]