狗狗onsite 面经

年初面了狗家，深知今年秋季找工作不易，分享一波面经，希望能帮到大家共4轮
1. 给一个m*n 的网格， 0表示海，1表示陆地， 相邻格子高度差最大为1，所有海洋对应的格子的高度为0，求给定网格的最大陆地高度

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

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

移动最多k个位置，要求用m次操作将序列排得尽可能有序。hints是sliding window.

最后求米！

第一题同意为bfs。n*m的复杂度。

bfs的第一级为所有为0的点以及右边四周外的一圈。height在level 1时为0。每到下一个level，height加一。最后返回height。

求讨论，求米

pengtsen 发表于 2019-11-4 11:59
楼主，第一题没看明白，你说1表示陆地，那最大陆地高度不就只能是1吗？是不是应该是“正整数代表陆地”？

格子里的1，0和高度没有关系，只是用来标注该格子是陆地还是海洋，换成圈叉也是一样的。每个格子的高度是要自己根据规则填的，所有海洋的格子高度只能是0

请问楼主，第二轮给你有向边，然后如果是树的情况下，只要找入度为0 的点返回就可以对吧还是找到这个点了开始建树，可能是二叉树也可能多叉树，最后返回root. 然后不是树的情况下，有可能是森林，也有可能是树有叶子连接到祖先。是这样吗？然后第四题楼主能描述下吗？没想太明白。

最后一题用size 为k的min heap辅助就行吧？

wtcupup 发表于 2019/11/01 15:38:10
最后一题用size 为k的min heap辅助就行吧？

对的就是这个思路

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

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

wtcupup 发表于 2019-11-1 15:38
最后一题用size 为k的min heap辅助就行吧？

求解释？ 用heap跟移动数字有什么关系呢？

谢谢分享 啊

楼主，第一题没看明白，你说1表示陆地，那最大陆地高度不就只能是1吗？是不是应该是“正整数代表陆地”？