Indeed OA 18

Indeed OA 18
题目：

Test case:
关于最后两个test case 过去不：
DFS和BFS都过不去，然后用DFS 的时候，每个点先上下左右四个方向i

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

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

y/QQ/em34.gif" smilieid="112" border="0" alt="" />

我test case过了，是用priority queue 做bfs，每次只dequeue 目前扩散的ink value最大那个queue，这样可以避免重复计算grid cell的值

gaoh 发表于 2017-11-13 13:58
请教下您，这个公式是什么啊？多想多谢！！

你可以找一下题目截图，公式就是用来计算那个滴了墨水的格子周围的格子最终会有多少墨水的一个公式，自己也可以推理出来，祝你好运

sarahzjn 发表于 2017-11-2 11:52
这个公式在点x和新的点不在一条线上也可以用。。。（对角线也可以）。我不用queue和递归直接做楼主觉得行嘛 ...

请教下您，这个公式是什么啊？多想多谢！！

楼主请问您是内推还是海投呀？投的什么职位呢？

Dream2333 发表于 2017-10-22 01:56
楼主请问您是内推还是海投呀？投的什么职位呢？

内推SDE new grad

扩散规则又是怎么样的……四个方向还是八个方向……每次扩散减少多少？同一滴墨水会扩散两次到同一个位置么？也是按哪次深算哪个？

yudingsun 发表于 2017-10-29 03:15
扩散规则又是怎么样的……四个方向还是八个方向……每次扩散减少多少？同一滴墨水会扩散两次到同一个位置么 ...

三个帖子你都读一读就出来了。。。。。。。。
四个方向扩散，取最深
当x,y 是darkness的时候， 位置col, row 的对应染色值应该是darkness - abs(x - col) - abs(y - row).

楼主你好，我想问问 “每个点先上下左右四个方向iteration染色，然后四个对角线点再recursion竟然过了”这个能展开说说嘛？还有那个公式没感觉很有用呀

sarahzjn 发表于 2017-11-2 08:15
楼主你好，我想问问 “每个点先上下左右四个方向iteration染色，然后四个对角线点再recursion竟然过了”这 ...

x, y 位置：
iteration 对 x-1,y; x-2,y; .... x+1,y; x+2,y...
x,y-1; x,y-2.... x,y+1; x,y+2....
用公式染色

然后在(x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)位置分别调用本函数

小小彼得 发表于 2017-11-2 08:41
x, y 位置：
iteration 对 x-1,y; x-2,y; .... x+1,y; x+2,y...
x,y-1; x,y-2.... x,y+1; x,y+2....

我感觉这样的话干嘛不全都用公式了呢

这个公式在点x和新的点不在一条线上也可以用。。。（对角线也可以）。我不用queue和递归直接做楼主觉得行嘛

sarahzjn 发表于 2017-11-2 11:52
这个公式在点x和新的点不在一条线上也可以用。。。（对角线也可以）。我不用queue和递归直接做楼主觉得行嘛 ...

好像可以诶。。。。。。。。时间复杂度是MN*MN * #drops, 能不能过，我没试过~