由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G家一道面试题求问
相关主题
G家面试题,怎样答面试官才能满意?刚开始找工作,算法要看什么书啊?
请教一道面试题,判断迷宫有没有解graph如何找最短路径?
请问一道google面试题赞人品,也发Twitter 电面面经,又挂了!!(add Amazon 1st phone interview 面经)
G家面试题请教带限制条件的最短路径题怎么做?
问个面试题A家电面被拒贡献个题攒人品吧
菜鸟用careercup书和leetcode准备的一点体会word ladder II 找所有而不是第一个的最短路径一般咋做的?
感慨下找工作中的运气成分问一个word ladder的题目
[算法] word ladder problemRocket Fuel面经
相关话题的讨论汇总
话题: 桌子话题: 个点话题: bfs话题: 距离话题: 最短
进入JobHunting版参与讨论
1 (共1页)
l**g
发帖数: 133
1
N*N的格子中有k个点,代表桌子,并且有障碍物,求一点到达各个k点的距离最短。只
可以四个方向前进。
另外这种图论的算法LC和面筋上面很少,哪里有比较全的资料可以复习?
G****n
发帖数: 618
2
感觉是walls and gates的变形。要找一个到所有k点的总和最短的点,就求枚举每一个
点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。

【在 l**g 的大作中提到】
: N*N的格子中有k个点,代表桌子,并且有障碍物,求一点到达各个k点的距离最短。只
: 可以四个方向前进。
: 另外这种图论的算法LC和面筋上面很少,哪里有比较全的资料可以复习?

l**g
发帖数: 133
3
[在 Gallen (Gallen) 的大作中提到:]
:感觉是walls and gates的变形。要找一个到所有k点的总和最短的点,就求枚举每一
个点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。
还有没有其他的优化思路?除了prune以外。
r*******e
发帖数: 7583
4
从k个点出发BFS,记录k点到任意一点的距离,然后求和的最小值。不需要从每一个点
出发BFS。

【在 G****n 的大作中提到】
: 感觉是walls and gates的变形。要找一个到所有k点的总和最短的点,就求枚举每一个
: 点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。

g*********e
发帖数: 14401
5
从每个桌子bfs 把距离算出来,然后把距离加起来,找最小的距离和

【在 l**g 的大作中提到】
: N*N的格子中有k个点,代表桌子,并且有障碍物,求一点到达各个k点的距离最短。只
: 可以四个方向前进。
: 另外这种图论的算法LC和面筋上面很少,哪里有比较全的资料可以复习?

l**g
发帖数: 133
6
所以距离之和最小一定是在几个k点之中,那这个是为什么呢?
e***a
发帖数: 150
7
就是这个,没啥变形

【在 G****n 的大作中提到】
: 感觉是walls and gates的变形。要找一个到所有k点的总和最短的点,就求枚举每一个
: 点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。

w*******d
发帖数: 59
8
求这K个桌子的横纵坐标的median就好了?
a****x
发帖数: 93
9
只看第一步:
“从k个点到任意一点的最短距离”和“从任意一点到k个点的最短距离”有什么区别吗?
完全是一样的啊,没有任何优化

一个

【在 r*******e 的大作中提到】
: 从k个点出发BFS,记录k点到任意一点的距离,然后求和的最小值。不需要从每一个点
: 出发BFS。

l**g
发帖数: 133
10
哦,理解错了。所以一种类似dp的方法:
从第一个桌子出发,计算到各个点的距离,存在N*N里,然后从下一个桌子出发,更新
每个点算出来每个点到两个桌子的距离,依此类推直到k个桌子,找到距离里最小值就
可以
memory:N*N, 包括BFS开销
time: N*N*k, 每个桌子要遍历所有点
相关主题
菜鸟用careercup书和leetcode准备的一点体会刚开始找工作,算法要看什么书啊?
感慨下找工作中的运气成分graph如何找最短路径?
[算法] word ladder problem赞人品,也发Twitter 电面面经,又挂了!!(add Amazon 1st phone interview 面经)
进入JobHunting版参与讨论
w******h
发帖数: 20
11
有个corner case是如果有一个桌子到不了某个点,那么这个点的距离不能用来更新结
果的最小值,面试的时候也碰到这题了,这个corner case没想到,面试官提示了半天
才想出来。google就要求一次啥都写对所有的corner case都考虑到嘛..错一点都不行.
.是gg要求略苛刻还是我太弱了...

【在 l**g 的大作中提到】
: 哦,理解错了。所以一种类似dp的方法:
: 从第一个桌子出发,计算到各个点的距离,存在N*N里,然后从下一个桌子出发,更新
: 每个点算出来每个点到两个桌子的距离,依此类推直到k个桌子,找到距离里最小值就
: 可以
: memory:N*N, 包括BFS开销
: time: N*N*k, 每个桌子要遍历所有点

a*******g
发帖数: 1221
12
这不就是这道题吗?
https://leetcode.com/problems/shortest-distance-from-all-buildings/
大家得刷题啊。
l**g
发帖数: 133
13
我擦。。多谢!
s***c
发帖数: 639
14
这道是收费题,新一些的面筋现在大都是收费的了

【在 a*******g 的大作中提到】
: 这不就是这道题吗?
: https://leetcode.com/problems/shortest-distance-from-all-buildings/
: 大家得刷题啊。

i******t
发帖数: 22541
15
这个用最短路径计算不就完了dijkstra shortest path
作 k 次 不久完了?
l**g
发帖数: 133
16
带锁的题不能做,但还是能搜到的
1 (共1页)
进入JobHunting版参与讨论
相关主题
Rocket Fuel面经问个面试题
热腾腾g电面 已挂菜鸟用careercup书和leetcode准备的一点体会
这题怎么做?感慨下找工作中的运气成分
G题求解迷津[算法] word ladder problem
G家面试题,怎样答面试官才能满意?刚开始找工作,算法要看什么书啊?
请教一道面试题,判断迷宫有没有解graph如何找最短路径?
请问一道google面试题赞人品,也发Twitter 电面面经,又挂了!!(add Amazon 1st phone interview 面经)
G家面试题请教带限制条件的最短路径题怎么做?
相关话题的讨论汇总
话题: 桌子话题: 个点话题: bfs话题: 距离话题: 最短