亚麻的OA

上周做的亚麻oa，两道题目。都是高频！但是到现在也木有消息。估计凉凉了。以下为题目和分析，自己凉凉了，估计也是水平有限

看官也给点儿鼓励的大米（不会消耗你的米哈），非常感谢。

题目是 K nearest和 矩阵有坑，找最短path。我用python写的…

[hide=26]

亚麻python是2.7，所以大家要注意一下，比如xrange这种在2.7比range 更好用；但是3.x就没有xrange了！！

1. 亚麻的fresh deliver。我有一个delivery truck，为 [0,0]。还有delivery locations，list = [ [x,y],... ]，长度为N。求最近的K个店。
解题注意，需要import heapq，不然不运行。
def

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

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

er of rows, N = number of columns

For our grid: V= number of vertices = M*N; for each vertex, there are at most 4 edges, so we have E =  4M*N
In total, the time complexity is: O(MN)


[\hide]

lz别担心哈，最近可能处理的慢了点，说不定下礼拜就来vo了。你是上周几做的oa2哇？我也是上周做的还没反应

LalalaX 发表于 2019-3-3 02:05
lz别担心哈，最近可能处理的慢了点，说不定下礼拜就来vo了。你是上周几做的oa2哇？我也是上周做的还没反应

周末，所以其实应该是上上周。
我只有这一次OA，是叫oa 2吗？因为有小伙伴已经拿到onsite了……所以我很打鼓

sanmi0814 发表于 2019/03/03 03:23:52


周末，所以其实应该是上上周。
我只有这一次OA，是叫oa 2吗？因为有小伙伴已经拿到onsite了……所以我很打鼓

哦～～那你是社招，完了就是onsite。再慢慢等等，会来的

请问什么是update grid ，意思是把走过的点mark一下吗

hxthit 发表于 2019-3-3 07:48
请问什么是update grid ，意思是把走过的点mark一下吗

我现在在visit bfs里的(x0,y0)为起点，
往下走一次到(x,y)（不是墙）

if grid[x][y]==0 or grid[x][y]>grid[x0][y0]+1: grid[x][y] = grid[x0][y0]+1
else: continue ##表示已经有更短路径到当前的x,y。



补充内容 (2019-3-3 08:08):
就跟定义一个visited一样的，没啥区别

嗯嗯多谢多谢