咕果昂赛

binsheadongank 发表于 2018/10/23 14:57:47
请问楼主是年底毕业嘛，为什么现在就teammatch了

因为有别的offer deadline

多谢分享。
第一题见过几次了，我理解是记录每个点的neighbours(水平，垂直),放到heap里面，每次拿出最小的那个，更新自己，同时更新neighbour。如果neighbour为0就扔掉。这样是o(n^3)的时间复杂度。
第三题的followup是可以自己修改tree的结构？比如我可以加每个node每层的next,然后一个个遍历?

补充内容 (2018-10-23 23:05):
时间复杂度写错了，但是没法改了。

补充内容 (2018-10-23 23:54):
我想错了，就是楼主的做法，只要找到connected group的数量就是结果了，因为每个group最终都可以删到只剩一个。

恭喜恭喜！不刷题都能这样，牛

楼主team match 上了吗 ? 是product area match 吧

第一题没明白，应该根据什么去掉点？如果点是（1，2）（2，2），（2，1），（3，1）。如果先去掉（2，2）和（2，1）就会剩两个点，如果按顺序去掉（1，2）（2，2），（2，1），（3，1）就一个点都不剩。是剩下的点越少越好嘛？

还是不明白人车匹配为什么要用pq，如果所有人的车都唯一确定的话，各算各的不就可以了吗

nhqgoal 发表于 2018-10-24 15:25
还是不明白人车匹配为什么要用pq，如果所有人的车都唯一确定的话，各算各的不就可以了吗

你的意思是bfs吗？（还是啥？怎么样各算各的？

如果bfs的话，复杂度和地图尺度有关，但是这个题的地图大小可能会很大。

确认一下第一题，对于每一个点，所有水平线上的点+所有垂线上的点都是同一个联通块是吧？

请问第四轮的followup 3, 按顺序经过y coordinate。 意思就是向下顺序经过某些高度的平面，这个是要怎么算？把每个点的total按照高度分，最后返回结果中高度最高的那部分？

audrey_horne 发表于 2018-10-24 16:18
你的意思是bfs吗？（还是啥？怎么样各算各的？

如果bfs的话，复杂度和地图尺度有关，但是这个题的地图 ...

人和车坐标给定了的话，题意是不是没有任何冲突？ 那么对于每个人都计算离他最近的车，这样就可以确定一个人车匹配关系了吧？