狗家虚拟现场

设S[-1] = H[0] = x,把S数组前面延申两个dummy，就好理解一些了，然后就要求每个3i + k都满足那两个不等式。可能还需要reverse S[] 然后再跑一遍算法取最小值。

"3. 一个 tree, 返回每个 key 之间的路径."

这个题我认为应该是先遍历一遍树，取出来所有的节点值放到一个数组里面，然后对数组做任意两个节点的combination，然后问题就转化为求两个确定的节点之间的路径.
这个代码可以run

1. # Python3 program to print path between any
   
2. # two nodes in a Binary Tree
   
3. 
   
4. import sys
   
5. import math
   
6. 
   
7. 
   
8. # structure of a node of binary tree
   
9. class Node:
   
10.     def __init__(self, data):
    
11.         self.data = data
    
12.         self.left = None
    
13.         self.right = None
    
14. 
    
15. 
    
16. # Helper function that allocates a new node with the
    
17. # given data and NULL left and right pointers.
    
18. def getNode(data):
    
19.     return Node(data)
    
20. 
    
21. 
    
22. # Function to check if there is a path from root
    
23. # to the given node. It also populates
    
24. # 'arr' with the given path
    
25. 
    
26. def _get_path(res, _path, _root, target):
    
27.     print("In my get_path")
    
28.     if not _root:
    
29.         return
    
30.     _path.append(_root.data)
    
31.     if _root.data == target:
    
32.         res.append(_path[:])
    
33.         return
    
34.     _get_path(res, _path, _root.left, target)
    
35.     _get_path(res, _path, _root.right, target)
    
36.     _path.pop()
    
37. 
    
38. # Function to print the path between
    
39. # any two nodes in a binary tree
    
40. def printPathBetweenNodes(root, n1, n2):
    
41.     #         # vector to store the path of
    
42.     #         # first node n1 from root
    
43.     #         path1 = []
    
44. 
    
45.     #         # vector to store the path of
    
46.     #         # second node n2 from root
    
47.     #         path2 = []
    
48.     #         getPath(root, path1, n1)
    
49.     #         getPath(root, path2, n2)
    
50. 
    
51.     my_path1 = []
    
52.     my_path2 = []
    
53. 
    
54.     _get_path(my_path1, [], root, n1)
    
55.     _get_path(my_path2, [], root, n2)
    
56. 
    
57.     path1 = my_path1[0]
    
58.     path2 = my_path2[0]
    
59. 
    
60.     # Get intersection point
    
61.     i, j = 0, 0
    
62.     intersection = -1
    
63.     while (i != len(path1) or j != len(path2)):
    
64. 
    
65.         # Keep moving forward until no intersection
    
66.         # is found
    
67.         if (i == j and path1[i] == path2[j]):
    
68.             i += 1
    
69.             j += 1
    
70.         else:
    
71.             intersection = j - 1
    
72.             break
    
73. 
    
74.     # Print the required path
    
75.     for i in range(len(path1) - 1, intersection - 1, -1):
    
76.         print("{} ".format(path1[i]), end="")
    
77.     for j in range(intersection + 1, len(path2)):
    
78.         print("{} ".format(path2[j]), end="")
    
79. 
    
80.     # Driver program
    
81. 
    
82. 
    
83. if __name__ == '__main__':
    
84.     # binary tree formation
    
85.     root = getNode(0)
    
86.     root.left = getNode(1)
    
87.     root.left.left = getNode(3)
    
88.     root.left.left.left = getNode(7)
    
89.     root.left.right = getNode(4)
    
90.     root.left.right.left = getNode(8)
    
91.     root.left.right.right = getNode(9)
    
92.     root.right = getNode(2)
    
93.     root.right.left = getNode(5)
    
94.     root.right.right = getNode(6)
    
95.     node1 = 7
    
96.     node2 = 6
    
97.     printPathBetweenNodes(root, node1, node2)
    

复制代码

"第二题 手机基站定位, inpu 是多个基站的位置坐标, 以及手机到基站的信号强度, 求具体手机的坐标. 强度信号不能直接转化成距离." 这个题看起来像是BFS？从每个基站开始遍历所有的位置，计算到该位置的强度做累加。然后再遍历一遍所有的位置如果累加的强度和等于手机的信号强度，那就返回该位置的坐标。

lch04 发表于 2020-7-8 01:53
"第二题 手机基站定位, inpu 是多个基站的位置坐标, 以及手机到基站的信号强度, 求具体手机的坐标. 强度信 ...

数学题, 不涉及图论

amgfan 发表于 2020-7-8 04:08
数学题, 不涉及图论

那就不知道了，感觉题意说的也不是特别清楚，还请赐教啊

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

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

lch04 发表于 2020-7-8 01:48
"3. 一个 tree, 返回每个 key 之间的路径."

这个题我认为应该是先遍历一遍树，取出来所有的节点值放到一 ...

第三题 可以求出Lowest Common Ancestor 然后再结合path

木华黎_Reid 发表于 2020-7-9 06:39
非常赞同。具体一些： 由于n是奇数，所以可以分为
1. n = 6k+1, mid = 3k
可以从2 和 n-3出发， 注意到 ...

层主的分析好。我之前只想到了大概方向，再像你这样动笔细算一下就会发现其实都是确定了的。。。

木华黎_Reid 发表于 2020-7-9 06:39
非常赞同。具体一些： 由于n是奇数，所以可以分为
1. n = 6k+1, mid = 3k
可以从2 和 n-3出发， 注意到 ...

所以根据你的意思 最中间那个永远是个定值？

楼主这是踩到雷了...