讨论/求职面试/求3.13美团笔试最后一题解法(题目我也每完全记下)/
求3.13美团笔试最后一题解法(题目我也每完全记下)

有做了今天美团笔试的同学吗?可以讨论下最后一题重庆道路那个怎么写吗?题目我也记不得了,希望有大佬记得,或者也许是LC的原题?

1
共 6 个回复

双哈希表, 一个存数字和出现次数, 一个存出现次数和对应的数字(Set), 还有, 暴力法没有超时, 通过率 91%

1

类似于上周周赛倒数第二题,不过此题求的是最大值。
1、考虑从高度大的节点向高度小的节点的边建图。
2、由节点的高度从小到大排序后进行dp。
3、类似于LIS朴素做法, 状态转移方程:f[i] = max(f[i], f[j] + 1)(j为i可到达的点,总边数最大只有1e5因此不会超时)。
时间复杂度O(NlogN + N + M)。

1

按照高度差可以构造一张有向图。

然后进行拓扑排序,在拓扑排序过程中维护最大距离。

大哥,你说的是第三题

用大小是k的滑动窗口,把每次滑动窗口里的数字都放到一个hashmap里,hashmap装的是每个数字和其对应的出现次数,然后每个滑动窗口求众数。。。我是这么写的

n个节点,m条无向边,每个节点有对应高度,求从某一节点出发到其他节点能够形成的最大距离,要求路径各点高度严格单调递减。

顺便问下同学第三题求众数的怎么做的,我的解法超时了。