狗家onsite

Leetcode 原题 perfec

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

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

terger

第二题 平均数的话只能全加起来再除吧？ O(N) 然后中位数就是quick select第k/2大的元素也是O(N)
第三题 楼主BFS的思路能说下嘛？
第四题 矩阵只有0和1，走到海洋就是走到矩阵的边界么？可不可以这么做看到陆地的点就DFS下，看有没有一条全是1的路径走到边界？
第五题 是LC346吗？
祝楼主好运

haoshenxiong 发表于 2016-8-26 11:49
想不出这个题怎么BSF。。

我也觉得很奇怪，这个题抽象出来应该是找数的公共祖先，不知道怎么BFS，有一个可能性是有PARENT指针，这样可以把树节点看成一个无向图，然后BFS，看他们最先在哪里相遇

南慕伦 发表于 2016-8-26 01:25
1. BFS?
2.中位数是线性时间选择？
3. 如果只有一个查询DFS BFS都可以吧，不过感觉后序遍历是最好的…… ...

4题应该是在边界先找河流的点（1），然后BFS把所有的可以到达的河流的点都标记为可以到海洋吧

find median and average of an array

给两个人的族谱，查找 两个人 最 近的共同祖先。 比较 DFS 和 BFS

给一个矩阵，0 代表 陆地，1代表河流，周围是海洋，求那些点可以通向海洋。

算 一个 input stream 的moving average。

1. BFS?
2.中位数是线性时间选择？
3. 如果只有一个查询DFS BFS都可以吧，不过感觉后序遍历是最好的……静态树的多查询可以用Tarjan，动态的只能线段树了……
4. floodfill?
5. 双端队列+定期更新修正精度差？

给两个人的族谱，查找 两个人 最 近的共同祖先。 比较 DFS 和 BFS？

这个是普通的least common ancestor 题吗？有什么trick吗

"输出要求输出所有组成结果的list的interger"

请问楼主这题是combination sum?

edyyy 发表于 2016-8-26 03:18
"输出要求输出所有组成结果的list的interger"

请问楼主这题是combination sum?

不是的，
For example, given n = 12, return {4, 4 , 4} because 12 = 4 + 4 + 4; given n = 13, return {4, 9} because 13 = 4 + 9.

南慕伦 发表于 2016-8-26 01:25
1. BFS?
2.中位数是线性时间选择？
3. 如果只有一个查询DFS BFS都可以吧，不过感觉后序遍历是最好的…… ...

第一题是DP
第三题要写both DFS 和BFS，然后比较
第五题也是leetcode类似题

南慕伦 发表于 2016-8-26 01:25
1. BFS?
2.中位数是线性时间选择？
3. 如果只有一个查询DFS BFS都可以吧，不过感觉后序遍历是最好的…… ...

第一题是DP
第三题要写both DFS 和BFS，然后比较
第五题也是leetcode类似题

sarah617 发表于 2016-8-26 02:38
给两个人的族谱，查找 两个人 最 近的共同祖先。 比较 DFS 和 BFS？

这个是普通的least common ancestor ...

没有特别的trick，就是要写BFS和DFS两种，然后比较tradeoff