meta vo

Patrickcy 发表于 2024-5-15 17:09
做一个column_node hashmap之后
一般来说sort下column （比如-2 到2 ）logn

c++ hashmap是红黑树。因此严格意义上这样做也不是O(N)的。在你每轮遍历的时候，落到叶子节点都是log(N)
如果要深抠，可以跟面试官提到，然后换成两个vector<vector<int>>。一个是根左边的，一个是根右边的。左边的最后在返回的时候从back开始往begin走，右边的从begin往back走。

patpat 拍拍楼主 谢谢分享 ， 面试真的就是碰运气 遇到**没辙 祝那个烙印也能被咱们同胞给干下去

第一題要 O(n) 就必須要掃兩遍
第一遍找出column 的範圍
第二遍才是正常bfs/dfs操作

还有硬挂这种操作，脸家面试能不能complain的

谢谢楼主分享，可以分享一下timeline吗？

匿名用户 发表于 2024-05-15 23:07:01
第一題要 O(n) 就必須要掃兩遍
第一遍找出column 的範圍
第二遍才是正常bfs/dfs操作

第一遍的时候纪录最小值，不用两遍

我理解O(n) 也是可以sort的，只要sort的列表长度在一个常数值之内就行了

Mr_Chew112 发表于 2024-05-16 01:33:09
我理解O(n) 也是可以sort的，只要sort的列表长度在一个常数值之内就行了

如果tree是zigzag 的，就两列，每一列n/2。

都最优解被挂确实太恶心了 > < 跟hr complain一下可能会有用？

第二题是遍历第二个array，然后第一个array 看 第二个array 的index - 1 然后 只需keep min， 然后用第一个array的min + 第二个的current value 看最小sum就行 ？

你们都有积分能看到题 好好奇第一题在说什么题 …