🐶VO面经

匿名者 发表于 2021-12-10 01:36
谢谢分享 请问为何distance是5的话是1

只要有node，distance至少为1。

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

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

第四题比1027难不少？是不是要针对每一个node算left subtree length sequence and right subtree length sequence, 然后看能不能concat起来？

Q1 follow up, dfs solution

1. def compress_matrix_ii(matrix: List[List[int]]) -> None:
   
2.     # dfs
   
3.     adj = defaultdict(set)  # dependency
   
4.    
   
5.     ROWS, COLS = len(matrix), len(matrix[0])
   
6. 
   
7.     d = {matrix[i][j]: (i, j) for i in range(ROWS) for j in range(COLS)} # mapping from cell value to cell coordinates
   
8.    
   
9.     for i in range(ROWS):
   
10.         nums = matrix[i]
    
11.         prev_num = None
    
12.         for k, num in enumerate(sorted(nums)):
    
13.             if k != 0:
    
14.                 adj[num].add(prev_num)
    
15.             prev_num = num
    
16. 
    
17.     for j in range(COLS):
    
18.         nums = [matrix[i][j] for i in range(ROWS)]
    
19.         prev_num = None
    
20.         for k, num in enumerate(sorted(nums)):
    
21.             if k != 0:
    
22.                 adj[num].add(prev_num)
    
23.             prev_num = num
    
24. 
    
25.     visited = {}
    
26.    
    
27.     def dfs(i, j):
    
28.         if (i, j) in visited:
    
29.             return visited[(i, j)]
    
30.         res = 1
    
31.         num = matrix[i][j]
    
32.         for nei in adj[num]:
    
33.             res = max(res, dfs(*d[nei]) + 1)
    
34.         matrix[i][j] = visited[(i, j)] = res
    
35. 
    
36.         return res
    
37. 
    
38.     for i in range(ROWS):
    
39.         for j in range(COLS):
    
40.             dfs(i, j)
    

复制代码

匿名者 发表于 2021-12-11 09:02
多谢楼主分享，已加米。Q4没有什么好的思路，能麻烦下楼主分享下自己的思路吗？
    2
  /   \

thanks for sharing, 我也感觉这题思路其实跟124. Binary Tree Maximum Path Sum更像？

maorq08 发表于 2021-12-11 15:11
第四题比1027难不少？是不是要针对每一个node算left subtree length sequence and right subtree length se ...

第四题是利口 无私就 啊。。小变种一下。

没看懂第三题。楼主能稍微讲一下吗？已加米

Q1貌似幺散散幺 + 幺溜散而， follow up那个union find没见过确实不好想。。。

SoWhat0309 发表于 2021-12-14 15:07
Q1貌似幺散散幺 + 幺溜散而， follow up那个union find没见过确实不好想。。。

就是那一题，第二问的做法我感觉很丧心病狂

第一题有不sort的解法吗？不然是为了考啥？