狗家onsite

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

cherie_0921 发表于 2016-8-26 03:55
没有特别的trick，就是要写BFS和DFS两种，然后比较tradeoff

想不出这个题怎么BSF。。

族谱有parent指针么？

cherie_0921 发表于 2016-8-26 03:52
不是的，
For example, given n = 12, return {4, 4 , 4} because 12 = 4 + 4 + 4; given n = 13, retur ...

还是没看懂这个例子，12为啥就return 4,4,4，他还等于8+4, 9+3呢，是所有组合都要return 吗

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

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

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

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